位移以获得余数

java bit-manipulation number-theory

2022-09-04 23:33:52

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

例如，当除数为形式时获取余数，以下运算将产生余数。2^k

m = Remainder

n = The number

d = The divisor

m = n & ( d - 1 )

但是，此方法仅在形式为 .我想知道非幂的类似方法。我目前正在研究一个问题，并希望采用这种方法来减少程序执行时间d2^k2programming challenges

答案 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

答案 2