13

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

例如，为了在除数为以下形式时获得余数，2^k以下操作产生余数。

m = Remainder

n = The number

d = The divisor

m = n & ( d - 1 )

然而，这种方法只有在d是 形式时才有效2^k。我想知道一种类似的方法来处理非2. 我目前正在解决一个问题，programming challenges并希望采用这种方法来减少程序执行时间

4

1 回答 1

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.

于 2012-11-25T23:08:29.360 回答