使用位移操作获取余数

Question

我想知道如何仅使用位移或按位运算符（仅限两个正整数）来获得整数除以另一个整数的余数。不应使用/ 运算符或 % 运算符。

例如，当除数为2^k形式时，可以使用以下操作获得余数。

m = 余数

n = 数字

d = 除数

m = n & ( d - 1 )

但是，此方法仅适用于d为2^k形式的情况。我想知道一种类似的非2次幂的方法。我目前正在解决编程挑战问题，并希望使用这种方法来减少程序执行时间。

- Extreme Coders

---

位表示仅在基数为2的情况下，这不是一种限制吗？考虑值43/7 - 实际值为6.142857...。您是否考虑过用高于2的基数来表示值的通用方法？ - Makoto

没有通用的方法。但是，如果你知道被除数，可以用乘法、移位和加减法来替换除法。向任何一位称职的C编译器询问，它会为任何编译时常量提供魔术值。 - Daniel Fischer

如果您在代码中硬编码魔数乘法器和移位距离，它应该可以在大多数CPU上击败除法。但这当然仅限于您在编译时知道的除数。 - Daniel Fischer

我找到了这个链接。它本身不足以作为一个答案，但可能已经足够让你开始着手解决问题了。 - Makoto

模数运算已经非常快了（在x86或amd64的IDIV操作码中已经计算了模数；它只需要大约30个时钟周期）。我真的怀疑慢除法是问题所在——可能有一种需要更少操作（不一定更快）的算法作为答案。 - tucuxi

Answer 1

任何不使用运算符%的答案都会是一个效率较低的答案，但是如果您绝对不能使用该运算符，则可以使用循环反复从n中减去d来解决问题：

m = n;
while (m >= d)
{
  m -= d;
}

假设您的整数为32位，则可以考虑一种优化版本，其中我们从n中删除d的倍数：

m = n;
for (i = 31; i >= 0; i--)
{
  di = d << i;
  if (di > 0 && m >= di) m -= di;
}

这个例子假设整数是有符号的，并且会检测溢出，即测试 di > 0。

- Stephen Quan

---

不幸的是，即使您假设一个正常的2s补码机器，溢出移位也不一定会导致负数。 - Chris Dodd