有没有简单的方法来做模数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.(这里的^不是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".那么"简单调整"是什么？

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

我们可以写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之间.获取base 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).EDIT2:替换^为**... oops.)