变换以获得剩余

Question

我想知道如何通过仅使用bitshift或bitwise运算符将整数与另一个整数(均为正)相除来获得余数.该/经营者或%经营者不得使用.

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

m = Remainder

n = The number

d = The divisor

m = n & ( d - 1 )

但是,此方法仅在d表单形式时有效2^k.我想知道类似的非权力方法2.我目前正在研究一个问题,programming challenges并希望采用这种方法来减少程序执行时间

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。