有没有一种简单的方法来执行2^32 - 1的模运算操作？

16 浏览
0 Comments

有没有一种简单的方法来执行2^32 - 1的模运算操作？

我刚刚听说对于x mod (2^32-1)和x / (2^32-1)会很简单，但是怎样计算呢？

计算公式如下：

xn = (xn-1 + xn-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页面上，他们说"modulus 2^32 − 1的算术运算只需要对2^32进行简单调整"。那么这个"简单调整"是什么？

0

3 答案

0 Comments

有没有一种简便的方法来执行2^32 - 1的求模运算？

出现的原因：

在计算中使用了规则2^32 = 1。一般来说，2^32+x = 2^x。可以通过对指数取模32来简化2^a的计算。

解决方法：

1. 可以将任意数字转换为二进制，然后降低指数。例如，数字2^40 + 2^38 + 2^20 + 2 + 1可以简化为2^8 + 2^6 + 2^20 + 2 + 1。

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

3. 对于64位字，数字可以表示为2^32 A + B，其中0 <= A,B <= 2^32-1。可以通过位运算轻松获取A和B。

4. 可以将其简化为A + B，这个数字要小得多：最多为2^33。然后，检查这个数字是否至少为2^32-1，如果是，就减去2^32 - 1。

5. 这样可以避免昂贵的直接除法运算。

以下是一个示例代码：

def modulus_operation(num):
    A = num >> 32
    B = num % (2 ** 32)
    result = A + B
    if result >= 2 ** 32 - 1:
        result -= 2 ** 32 - 1
    return result

以上就是解决"有没有一种简便的方法来执行2^32 - 1的求模运算？"问题的原因和解决方法。通过对指数取模32和位运算，可以避免昂贵的直接除法运算，从而更高效地执行求模运算。

0
0 Comments

有没有一种简单的方法来执行2^32 - 1的模运算？

问题出现的原因是作者想要找到一种简单的方法来执行2^32 - 1的模运算。作者首先假设x的数据类型大于32位，并且是正数。然后作者通过将x转换为以2^32为基数的形式，来对x进行模运算。作者提供了一个Python的示例代码来实现这个操作。

解决方法是将x转换为以2^32为基数的形式，然后将各个位上的数字相加。如果相加的结果在0和2^32-1之间，则返回该结果；如果结果大于2^32-1，则递归调用该方法直到结果在0和2^32-1之间。

还有如果x是64位的情况下，可以使用硬件指令来执行模运算，这可能比任何微观优化都要快。

总结起来，作者提供了一种将整数转换为以2^32为基数的形式，并对其进行模运算的方法。这种方法适用于任何正整数，并提供了一个Python的示例代码来实现该操作。还有在64位情况下可以使用硬件指令来执行模运算。

0
0 Comments

有没有一种简单的方法来执行2^32 - 1的模运算？

问题的原因：

这个问题的原因是，对于给定的一个数k，需要找到k除以2^32 - 1的余数。虽然已经给出了一种计算方法，但是如果k的位数很大，需要进行很多次移位操作，效率较低。

解决方法：

为了提高计算效率，可以利用以下性质进行计算：

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

根据这个性质，可以通过多次移位和相加操作来计算k除以2^32 - 1的余数。具体步骤如下：

1. 将k的位数减半，找到最接近k位数一半的倍数的数，记为m。

2. 将k右移m位，并将右移后的结果与2^m - 1相加，得到r1。

3. 重复步骤2，直到得到的结果位数小于等于32。

4. 如果最终得到的结果大于等于2^32 - 1，则减去2^32 - 1。

这种方法可以通过O(log2(b/n))次移位操作来计算k % (2^n - 1)，其中b是数的位数，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是类型宽度的一半时，循环最多执行两次。因此，如果分支开销较大，可以取消循环并无条件地执行循环体两次。

0