有什么简单的方法可以执行2 ^ 32-1模的运算？ [英] Is there any easy way to do modulus of 2^32 - 1 operation?

问题描述

我刚刚听说过 x mod（2 ^ 32-1）和 x /（2 ^ 32-1）很容易，但是如何？

I just heard about that x mod (2^32-1) and x / (2^32-1) would be easy, but how?

计算公式：

x _n =（x _n-1 + x _n-1 / b）mod b。

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。

For b = 2^32, its easy, x%(2^32) == x & (2^32-1); and x / (2^32) == x >> 32. (the ^ here is not XOR). How to do that when b = 2^32 - 1.

在页面 https://en.wikipedia.org/wiki/Multiply-with-carry 。他们说模数2 ^ 32 − 1的算术仅需要2 ^ 32 的算术简单调整。那么什么是简单调整？

In the page https://en.wikipedia.org/wiki/Multiply-with-carry. They say "arithmetic for modulus 2^32 − 1 requires only a simple adjustment from that for 2^32". So what is the "simple adjustment"?

推荐答案

（此答案仅处理 mod 情况。）

(This answer only handles the mod case.)

我假设 x 的数据类型大于32位（此答案实际上将与任何正整数一起使用）并且它是正数（负数只是-（-x mod 2 ^ 32-1）），因为如果最多32位，问题可以通过

I'll assume that the datatype of x is more than 32 bits (this answer will actually work with any positive integer) and that it is positive (the negative case is just -(-x mod 2^32-1)), since if it at most 32 bits, the question can be answered by

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 。因此

We can write x in base 2^32, with digits x0, x1, ..., xn. So

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

这使得我们在做模数时答案更加清晰，因为 2 ^ 32 == 1 mod 2 ^ 32-1 。那就是

This makes the answer clearer when we do the modulus, since 2^32 == 1 mod 2^32-1. That is

  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中（这不处理负数）：

x mod 2^32-1 is the same as the sum of the base 2^32 digits! (we can't drop the mod 2^32-1 yet). We have two cases now, either the sum is between 0 and 2^32-1 or it is greater. In the former, we are done; in the later, we can just recur until we get between 0 and 2^32-1. Getting the digits in base 2^32 is fast, since we can use bitwise operations. In Python (this doesn't handle negative numbers):

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 ，实际上您只需在此答案中将任何出现的32替换为 n 。）

(This is extremely easy to generalise to x mod 2^n-1, in fact you just replace any occurance of 32 with n in this answer.)

（编辑：添加了 elif 子句，以避免在 mod_2to32sub1（2 ** 32-1）上进行无限循环。 EDIT2：将 ^ 替换为 ** ... oops。）

( added the elif clause to avoid an infinite loop on mod_2to32sub1(2**32-1). replaced ^ with **... oops.)

这篇关于有什么简单的方法可以执行2 ^ 32-1模的运算？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！