有没有简单的方法可以进行 2^32 - 1 的模运算？

Question

我刚刚听说

x mod (2^32-1)

和

x / (2^32-1)

会很容易，但是如何呢？

计算公式：

x_n = (x_n-1 + x_n-1 / b)mod b。

对于

b = 2^32

来说，很简单，

x%(2^32) == x & (2^32-1)

；和

x / (2^32) == x >> 32

。 （这里的^不是异或）。当 b = 2^32 - 1 时如何做到这一点。

在页面中https://en.wikipedia.org/wiki/Multiply-with-carry。他们说“

arithmetic for modulus 2^32 − 1 requires only a simple adjustment from that for 2^32

”。那么什么是“简单调整”呢？

Answer 1

（此答案仅处理

mod

情况。）

我假设

x

的数据类型超过 32 位（这个答案实际上适用于任何正整数）并且它是正数（负数情况只是

-(-x mod 2^32-1)

），因为如果它最多 32位，这个问题可以通过

来回答

x mod (2^32-1) = 0 if x == 2^32-1, x otherwise
x / (2^32 - 1) = 1 if x == 2^32-1, 0 otherwise

我们可以用 2^32 为基数写出

x

，其中包含数字

x0

、

x1

、...、

xn

。所以

  x = x0 + 2^32 * x1 + (2^32)^2 * x2 + ... + (2^32)^n * xn

这使得我们在计算模数时答案更加清晰，因为

2^32 == 1 mod 2^32-1

。那就是

  x == x0 + 1 * x1 + 1^2 * x2 + ... + 1^n * xn (mod 2^32-1)
    == x0 + x1 + ... + xn (mod 2^32-1)

x mod 2^32-1

与基数 2^32 位的总和相同！ （我们还不能删除 mod 2^32-1）。现在我们有两种情况，要么总和在 0 到 2^32-1 之间，要么更大。对于前者，我们就完成了；对于前者，我们就完成了。在后面，我们可以重复直到我们得到 0 到 2^32-1 之间的值。获取以 2^32 为基数的数字很快，因为我们可以使用按位运算。在 Python 中（不处理负数）：

def mod_2to32sub1(x):
    s = 0 # the sum

    while x > 0: # get the digits
        s += x & (2**32-1)
        x >>= 32

    if s > 2**32-1:
        return mod_2to32sub1(s)
    elif s == 2**32-1:
        return 0
    else:
        return s

（这非常容易推广到

x mod 2^n-1

，事实上，您只需在这个答案中用

n

替换任何出现的 32 即可。）

（编辑：添加了

elif

子句以避免

mod_2to32sub1(2**32-1)

上的无限循环。编辑2：用

^

替换

**

...哎呀。）

Answer 2

因此，您可以使用“规则”2³² = 1 进行计算。一般来说，2^32+x = 2^x。您可以通过取指数模 32 来简化 2^a。示例：2⁶⁶ = 2²。

您可以用二进制表示任何数字，然后降低指数。示例：数字 2⁴⁰ + 2³⁸ + 2²⁰ + 2 + 1 可以简化为 2⁸ + 2⁶ + 2²⁰ + 2 + 1。

一般来说，您可以每 32 个 2 的幂对指数进行分组，并“降级”所有模 32 的指数。

对于64位字，数字可以表示为

2³²A+B

其中 0 <= A,B <= 2³²-1。通过按位运算即可轻松获得 A 和 B。

因此您可以将其简化为 A + B，它要小得多：最多 2³³。然后，检查该数字是否至少为 2³²-1，在这种情况下减去 2³² - 1。

这避免了昂贵的直接除法。

Answer 3

模数已经解释过了，不过，让我们回顾一下。

要求

k

模

2^n-1

的余数，请写

k = a + 2^n*b,  0 <= a < 2^n

然后

k = a + ((2^n-1) + 1) * b
  = (a + b) + (2^n-1)*b
  ≡ (a + b) (mod 2^n-1)

如果

a + b >= 2^n

，则重复直到余数小于

2^n

，如果这导致您得到

a + b = 2^n-1

，则将其替换为 0。每个“右移

n

并添加到最后

n

位”将第一个设置位向右移动

n

或

n-1

位置（除非

k < 2^(2*n-1)

，当移位加法之后的第一个设置位可能是

2^n

位时）。因此，如果类型的宽度与

n

相比较大，则需要多次移位 - 考虑 128 位类型和

n = 3

，对于较大的

k

，您将需要超过 40 次移位。为了减少所需的轮班次数，您可以利用以下事实：

2^(m*n) - 1 = (2^n - 1) * (2^((m-1)*n) + 2^((m-2)*n) + ... + 2^(2*n) + 2^n + 1),

其中我们只会使用

2^n - 1

除

2^(m*n) - 1

来得到所有

m > 0

。然后，您将移动

n

的倍数，这大约是该步骤中该值可以具有的最大位长度的一半。对于上面的 128 位类型和模 7 余数 (

2^3 - 1

) 的示例，3 到 128/2 最接近的倍数是 63 和 66，首先移位 63 位

r_1 = (k & (2^63 - 1)) + (k >> 63) // r_1 < 2^63 + 2^(128-63) < 2^66

得到最多 66 位的数字，然后移位 66/2 = 33 位

r_2 = (r_1 & (2^33 - 1)) + (r_1 >> 33) // r_2 < 2^33 + 2^(66-33) = 2^34

最多达到 34 位。接下来移位 18 位，然后是 9、6、3

r_3 = (r_2 & (2^18 - 1)) + (r_2 >> 18) // r_3 < 2^18 + 2^(34-18) < 2^19
r_4 = (r_3 & (2^9 - 1)) + (r_3 >> 9)   // r_4 < 2^9 + 2^(19-9) < 2^11
r_5 = (r_4 & (2^6 - 1)) + (r_4 >> 6)   // r_5 < 2^6 + 2^(11-6) < 2^7
r_6 = (r_5 & (2^3 - 1)) + (r_5 >> 3)   // r_6 < 2^3 + 2^(7-3) < 2^5
r_7 = (r_6 & (2^3 - 1)) + (r_6 >> 3)   // r_7 < 2^3 + 2^(5-3) < 2^4

如果

r_7 >= 2^3 - 1

就足够了，现在只需进行一次减法即可。要计算 b 位类型中的

k % (2^n -1)

，需要 O(log₂ (b/n)) 次移位。

商同样得到，我们再写

k = a + 2^n*b,  0 <= a < 2^n
  = a + ((2^n-1) + 1)*b
  = (2^n-1)*b + (a+b),

所以

k/(2^n-1) = b + (a+b)/(2^n-1)

，我们继续

a+b > 2^n-1

。遗憾的是，我们无法通过移动和屏蔽大约一半宽度来减少工作量，因此该方法仅在

n

不比类型宽度小很多时才有效。

n

不太小的快速情况的代码：

unsigned long long modulus_2n1(unsigned n, unsigned long long k) {
    unsigned long long mask = (1ULL << n) - 1ULL;
    while(k > mask) {
        k = (k & mask) + (k >> n);
    }
    return k == mask ? 0 : k;
}

unsigned long long quotient_2n1(unsigned n, unsigned long long k) {
    unsigned long long mask = (1ULL << n) - 1ULL, quotient = 0;
    while(k > mask) {
        quotient += k >> n;
        k = (k & mask) + (k >> n);
    }
    return k == mask ? quotient + 1 : quotient;
}

对于

n

是类型宽度一半的特殊情况，循环最多运行两次，因此如果分支成本很高，最好展开循环并无条件执行循环体两次。

Answer 4

事实并非如此。您一定听说过

x mod 2^n

和

x/2^n

更容易。

x/2^n

可以执行为

x>>n

，并且

x mod 2^n

，执行

x&(1<<n-1)