如何使用按位运算符求余数？

Question

我们看下面的代码。

int x = 5>>1;

它的作用是将给定值除以 1 的 2 次方（即 2）并返回商。按位运算可以求余数吗？

Answer 1

按位移位返回一个值，因此“丢失”任何余数。

对于二的幂，它可以与一个位掩码配对，该位掩码计算先前应用的移位中“丢失的内容”。

int quotient = 5 >> 1;
int remainder = 5 & 0x01;

上面的掩码值可以通过以下方式计算：

~((~(int)0) << 1)

；对于 32 位 int，

~0 == 0xFFFF

、

0xFFFF << 1 == 0xFFFE

和

~0xFFFE == 0x01

。

因此，用变量替换：

int n = ..;
int z = ..;
int quotient = n >> z;
int remainder = n & ~((~(int)0) << z);

同样，在更一般的情况下，整数除法 (

/

) 与模运算符 (

%

) 配对。每个运算符仅返回一个值。

int n = ..;
int z = ..;
int p = 1 << z;
int quotient = n / p;
int remainder = n % p;

Answer 2

a % b 等价于 (b - 1) & a