如何在C语言中使用有限的硬件实现无符号整数的模运算

Question

我有一台只支持32位操作的机器，long long在这台机器上无法使用。 我有一个64位的量，表示为两个无符号int 32。 问题是如何对这个64位的量使用32位除数进行模运算。

r = a mod b

其中： a是64位值，b是32位值

我想通过以下方式表示模部分： 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，如果我进行模运算，将再次得到2 ^ 32 :) 因此，我不确定如何对一个64位值执行无符号模运算和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

- Har

---

您的硬件的C编译器是否已经支持此功能？例如：uint64_t a,b,r; r = a % b; - Jonathon Reinhart

"2 ^ 32 mod b 有时可能等于 2 ^ 32"。但建议不要这样做。因为 b <= (2 ^ 32 - 1)，所以 (2 ^ 32 mod b) < (2 ^ 32)。 - chux - Reinstate Monica

"无法执行 2^32 mod b" --> 是的，但诀窍是 2^32 mod b == (2^32 - b) mod b。我们知道至少可以从2^32中减去1个b而结果不会变成负数。使用一次位移循环，就可以完成所有需要的操作。" - chux - Reinstate Monica

@chux 是的，那是真的很棒的技巧，谢谢 :) - Har

在您的计算机上，2^32 mod b != 2^32，因为b < 2^32。 - Mad Physicist

Answer 1

以和用铅笔和纸做长除法一样的方式来完成它。

#include <stdio.h>

unsigned int numh = 0x12345678;
unsigned int numl = 0x456789AB;
unsigned int denom = 0x17234591;

int main() {
    unsigned int numer, quotient, remain;

    numer = numh >> 16;
    quotient = numer / denom;
    remain = numer - quotient * denom;

    numer = (remain << 16) | (numh & 0xffff);
    quotient = numer / denom;
    remain = numer - quotient * denom;

    numer = (remain << 16) | (numl >> 16);
    quotient = numer / denom;
    remain = numer - quotient * denom;

    numer = (remain << 16) | (numl & 0xffff);
    quotient = numer / denom;
    remain = numer - quotient * denom;

    printf("%X\n", remain);   
    return 0;
}

- Weather Vane

---

顺便说一句：不要得到与 printf("%llX\n", 0x12345678456789ABu % 0x17234591u); 相同的答案。1042DD6 与 DF555C0。 - chux - Reinstate Monica

我认为问题在于如果 “demon” 大于16位，则“remain”可能大于16位。然后，“(remain << 16)”会丢弃位。 - chux - Reinstate Monica

是的，溢出问题是使其最棘手的原因。似乎唯一可靠的方法是忽略数学，采用“位”方式来处理所有数字。 - Har

Answer 2

功能：使用1000M个随机组合测试了64位%。

类似于小学的长除法a/b（但是在二进制中），如果可能，从a中减去b，然后进行移位，循环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;
}

注意：这是进行33位减法的巧妙部分。由于代码知道n具有MSB位设置，2n将大于b，那么n = 2n-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);
}

- chux - Reinstate Monica

---

@crux，请问这个函数会返回 uint32_t 还是 int32_t？ - Har

@Har 是的，谢谢。返回值应该是 uint32_t 而不是 int32_t。回答已更新。 - chux - Reinstate Monica

请问您能否详细说明一下您写的注释，我有点难以理解。如果您有一个十六进制数0x80000000并将其左移1位，则会得到0（在uint32_t上），因此信息会丢失。我知道您可以判断是否会发生这种情况，但我不明白如何修复它。（如果a和b都设置了最高位，但其余位不同，则会出现此情况）这是因为您知道a和b的最高位都被设置了，所以您正在利用这一点吗？ - Har

@Har 对的，当a的最高位被设置时，左移操作会丢失该位，但是代码位于if() { }块内部，这些块“知道”最高位已经被移出。因此，“33位”的a实际上是0x1_0000_0000 + a。由于这个值大于b，代码进行减法运算。在C语言中，无符号整数的数学运算是有明确定义的，会自动“环绕”。所以a -= b;的结果在数学上是正确的，它等同于a = 0x1_0000_0000 + a - b。在我看来，下面的通用代码更好地实现了这一点。 - chux - Reinstate Monica

@Har "涉及无符号操作数的计算永远不会溢出，因为不能由所得到的无符号整数类型表示的结果会被减去一个比该类型能表示的最大值还大的数字后取模。" C11dr §6.2.5 9 换句话说，32位减法的结果是 a-b mod 0x1_0000_0000。 - chux - Reinstate Monica

我仍然觉得这有点像魔法，但是我明白你的意思：（0x180000000 - 0x12345）mod 2 ** 32 和（0x80000000 - 0x12345）mod 2 ** 32 是相同的（模数魔法！）。 - Har