如何在C中使用有限硬件对无符号整数执行模运算

Question

我有一台只支持32位操作的机器,很长时间不能在这台机器上工作.我有一个64位数量表示为两个unsigned int 32s.问题是如何使用32位除数对64位数量执行mod.

r = a mod b

哪里:

a是64位值,b是32位值

我以为我可以通过这样做来表示mod部分:a = a1*(2 ^ 32)+ a2(其中a1是顶部位,a2是底部位)

(a1*(2 ^ 32)+ a2)mod b =((a1*2 ^ 32)mod b + a2 mod b)mod b

((a1*2 ^ 32)mod b + a2 mod b)mod b =(a1 mod b*2 ^ 32 mod b + a2 mod b)mod b

但问题是2 ^ 32 mod b有时可能等于2 ^ 32,因此乘法会溢出.我已经看过尝试将乘法转换为加法,但这也需要我使用2 ^ 32,如果我mod将再次给我2 ^ 32 :)所以我不知道如何执行64位的无符号mod值为32位.

我想这个简单的解决方案是执行以下操作:

1. a/b = c

2. a = a - floor(c)*b

3. 执行1直到c等于0并使用a作为答案.

但我不知道如何将这两个整数组合在一起形成64位值

在这里完成的是二进制除法和减法的一些链接:http: //www.exploringbinary.com/binary-division/

和二进制除法算法的描述:http: //en.wikipedia.org/wiki/Division_algorithm

Answer 1

有效：使用 1000M 随机组合针对 64 位%.

就像小学长除法a/b（但以 2 为基数）一样，如果可能的话，减去b，a然后移位，循环 64 次。返回剩余部分。

#define MSBit 0x80000000L
uint32_t mod32(uint32_t a1 /* MSHalf */, uint32_t a2 /* LSHalf */, uint32_t b) {
  uint32_t a = 0;
  for (int i = 31+32; i >= 0; i--) {
    if (a & MSBit) {  // Note 1
      a <<= 1;
      a -= b;
    } else {
      a <<= 1;
    }
    if (a1 & MSBit) a++;
    a1 <<= 1;
    if (a2 & MSBit) a1++;
    a2 <<= 1;
    if (a >= b)
      a -= b;
  }
  return a;
}

注 1：这是进行 33 位减法的巧妙部分。由于代码知道n已设置 MSBit，2*n因此将大于b，然后n = 2*n - b。这依赖于无符号环绕。

[编辑]

下面是一个modu()适用于任何数组大小a和任何大小的无符号整数的泛型。

#include <stdint.h>
#include <limits.h>

// Use any unpadded unsigned integer type
#define UINT uint32_t
#define BitSize (sizeof(UINT) * CHAR_BIT)
#define MSBit ((UINT)1 << (BitSize - 1))

UINT modu(const UINT *aarray, size_t alen, UINT b) {
  UINT r = 0;
  while (alen-- > 0) {
    UINT a = aarray[alen];
    for (int i = BitSize; i > 0; i--) {
      UINT previous = r;
      r <<= 1;
      if (a & MSBit) {
        r++;
      }
      a <<= 1;
      if ((previous & MSBit) || (r >= b)) {
        r -= b;
      }
    }
  }
  return r;
}

UINT modu2(UINT a1 /* MSHalf */, UINT a2 /* LSHalf */, UINT b) {
  UINT a[] = { a2, a1 };  // Least significant at index 0
  return modu(a, sizeof a / sizeof a[0], b);
}