5

我刚刚听说过，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。（这里的 ^ 不是 XOR）。当 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”。那么什么是“简单调整”呢？

4

4 回答 4

7

（这个答案只处理这种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

我们可以x以 2^32 为底，用数字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子句以避免在 .EDIT2 上出现无限循环mod_2to32sub1(2**32-1)：替换^为**... 哎呀。）

于 2012-03-25T01:27:57.510 回答
2

因此，您使用“规则”计算 2 32 = 1。通常，2 32+x = 2 x。您可以通过取指数模 32来简化 2 a 。示例：2 66 = 2 2。

您可以用二进制表示任何数字，然后降低指数。示例：数字 2 40 + 2 38 + 2 20 + 2 + 1 可以简化为 2 8 + 2 6 + 2 20 + 2 + 1。

通常，您可以每 2 的 32 次幂对指数进行分组，并以 32 为模“降级”所有指数。

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

2 32 A + B

其中 0 <= A,B <= 2 32 -1。使用按位运算很容易获得 A 和 B。

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

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

于 2012-03-25T01:19:15.010 回答
1

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

要找到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小于_ _移位加后的位可能是位）。因此，如果类型的宽度与 相比较大，则需要多次移位 - 考虑 128 位类型，对于较大的类型，您将需要超过 40 次移位。为了减少所需的班次次数，您可以利用以下事实：2^na + b = 2^n-1nnnn-1k < 2^(2*n-1)2^nnn = 3k

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

其中我们将只对所有人使用该2^n - 1除法。然后，您移动该值的倍数，大约是该值在该步骤中可以具有的最大位长度的一半。对于上面的128位类型和余数模 7（2^(m*n) - 1m > 0n2^3 - 1

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就足够了。要k % (2^n -1)以 b 位类型计算，需要 O(log 2 (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，循环最多运行两次，所以如果分支开销很大，最好展开循环并无条件地执行循环体两次。

于 2012-03-25T13:13:58.033 回答
0

它不是。您一定听说过 x mod 2^n 和 x/2^n 更容易。x/2^n 可以执行为 x>>n，并且 x mod 2^n，做 x&(1<<n-1)

于 2012-03-25T01:10:40.530 回答