计算64位整数模的128位整数的最快方法

一尘不染

algorithm

我有一个128位无符号整数A和一个64位无符号整数B。最快的计算方法是A % B-将A除以B的余数（64位）？

我正在寻找使用C或汇编语言进行的操作，但是我需要针对32位x86平台。不幸的是，这意味着我无法利用编译器对128位整数的支持，也无法利用x64体系结构在单个指令中执行所需操作的能力。

编辑：

到目前为止，谢谢您的回答。但是，在我看来，建议的算法会非常慢-
执行128位乘以64位除法的最快方法不是利用处理器对64位乘以32位除法的本机支持吗？有谁知道有没有办法按照几个较小的分区来执行较大的分区？

回复：B多久更换一次？

我主要对通用解决方案感兴趣-如果A和B每次可能不同，您将执行什么计算？

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

阅读 309

2020-07-28

共1个答案

一尘不染

您可以使用俄语农民倍增的除法版本。

要查找其余部分，执行（以伪代码）：

X = B;

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

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

模数留在A中。

您需要实现移位，比较和减法，以对由一对64位数字组成的值进行运算，但这是相当琐碎的（可能您应将left-by-by-1实现为X + X）。

这将最多循环255次（使用128位A）。当然，您需要预先检查零除数。

2020-07-28