无涯教程网

C++ 以 64 位整数为模计算 128 位整数的最快方法

发布于04月02日

我有一个128位无符号整数a和一个64位无符号整数B.计算A % B的最快方法是什么——即a除以B的(64位)余数？

我希望用C或汇编语言来实现这一点，但我需要针对32位x86平台.不幸的是，这意味着我不能利用编译器对128位整数的支持，也不能利用x64体系 struct 在一条指令中执行所需操作的能力.

Edit:

谢谢你迄今为止的回答.然而，在我看来，建议的算法会非常慢——执行128位乘64位除法的最快方法不是利用处理器对64位乘32位除法的本机支持吗？有人知道有没有一种方法可以用几个较小的分区来执行较大的分区？

Re: How often does B change?个

我主要感兴趣的是一个通用的解决方案——如果a和B每次都可能不同，你会进行什么计算？

然而，第二种可能的情况是，B的变化不像A那么频繁-可能有多达200个B除以每个B，在这种情况下，您的答案会有什么不同？

推荐答案

你可以使用Russian Peasant Multiplication的除法版本.

要查找余数，请执行(在伪代码中):

X = B;

while (X <= A/2)
{
    X <<= 1;
}

while (A >= B)
{
    if (A >= X)
        A -= X;
    X >>= 1;
}

模数留在A中.

您将需要实现移位、比较和减法来对由一对64位数字组成的值进行操作，但这相当简单(很可能您应该将左移1实现为X + X).

这将最多循环255次(使用128位a).当然，你需要预先判断零除数.

C++相关问答推荐

Pure Win32 C(++)-除了替换控件的窗口程序之外，还有其他方法可以在输入时禁用按钮吗？

为什么已经设置的值在C中被重置为for循环条件中的新值？

Mise()在虚拟内存中做什么？

单指针和空参数列表之间的函数指针兼容性

正在try 将文件/文件夹名从目录 struct 存储到链接列表

创建一个fork导致fget无限地重新读取文件

如何调试LD_PRELOAD库中的构造函数？

使用C时，Windows CMD中的argc参数是否包含重定向命令？

为什么即使在强制转换时，此代码也会溢出？

当输入负数时，排序算法存在问题

如何只获取字符串的第一个单词，然后将其与c中的另一个单词进行比较？

在vfork()之后，链接器如何在不 destruct 父内存的情况下解析execve()？

在C++中允许使用字符作为宏参数

将回调/基于事件的C API转换为非回调API

通过k&；r语法的c声明无效

在运行时判断C/C++指针是否指向只读内存(在Linux操作系统中)

计算SIZE_MAX元素的长数组的大小

按字典顺序打印具有给定字符的所有可能字符串

"；错误：寄存器的使用无效；当使用-masm＝intel；在gcc中，但在AT&；T模式

使用 _Atomic float 时，MSVC 编译的代码会命中调试断言

实用课程推荐

相关教程推荐