从 i 到 0 清除位 - 位操作

Question

我正要去破解编码面试第 5 章位操作 并找到了清除数字 num

中从 i 到 0 的位的方法

int mask = ~(-1 >>> (31 - i));
return num & mask

虽然上面的方法有效

我们可以像

那样简单点吗

int mask = (-1 << (i+1));
return num & mask;

我是否遗漏了任何极端情况？

Answer 1

当然可以。你的掩码 -1 << (i+1) 在逻辑上等同于书本的掩码 ~(-1 >>> (31 - i)).

您的方法 bit-wise 将 -1 向左移动 i + 1 次，用 0.

填充最低的 i + 1 位

本书的方法逻辑上将-1右移31 - i次，用0填充最高的31 - i位。但是，它随后会反转位，这就是使您的等同于它的原因。要针对 int 的所有值验证它，您可以创建一个简单的 for-loop:

for (int i = 0; i < 31; i++) {
    System.out.println(~(-1 >>> (31 - i)) + " " + (-1 << (i+1)));
}

当 运行 时，您会发现两个掩码在每次迭代时都是等效的。

Answer 2

确实存在边缘情况：对于 i = 31、(-1 << (i+1)) = -1 而 ~(-1 >>> (31 - i)) = 0.

发生这种情况是因为移位计数取模类型的大小（以位为单位），在本例中为 32，(31 + 1) mod 32 = 0 因此在两个表达式中有效移位计数为零。由于第二个表达式的反转逻辑，它们的行为有所不同。

然而，~(-1 >>> (31 - i))是等价于更简单的-2 << i。