理解`(1 << j) - 1`中的算术

Question

希望能帮助解释以下位操作。原谅我对位运算的不了解。

int max = ~0;   
int left = max - ((1 << j) - 1);

这个操作的结果是什么？ (1<<(j-1)) 等同于 ((1 << j) - 1) 吗？

Answer 1

(1 << j) - 1是一个数j右边有位

        j bits
       ┌──────┐
00...0011...111

max是一个全1位

的数字

11...1111...111

max的每一位在减去(1 << j) - 1的一位时变为0，否则保持1。因此 max - ((1 << j) - 1) 将产生一个右边有 j 个零位的值

           j...210 ← bit position
    11...1111...11
 -  00...0011...11
──────────────────
    11...1100...00

这意味着结果是(1 << j) - 1的按位非，即

max - ((1 << j) - 1) == ~((1 << j) - 1)

Is (1<<(j-1)) equivalent to ((1 << j) - 1)?

1 << (j-1) 向左移动 1 j-1 个位置并产生 2^{j - 1}，所以它在右边有 j-1 个零接着是一个 100...00。 (1 << j) - 1 给出一个右边有 j 个零的数字，即 2^j - 1，如上所述。你能猜出它们是否相似吗？

Answer 2

按照下面的公式，

案例：1

(1 << j) - 1) is equal to 2^j-1 [j = 1,2...]

案例：2

(1<<(j-1)) is equal to 2^(j-1) [j = 1,2,3...]

Is (1<<(j-1)) equivalent to ((1 << j) - 1)?

没有，从上面的公式可以看出。

What will be the result of this operation?

对于这个问题，max 将是“-1” [按位 NOT(0) 相当于所有位值的补码共 0]

则公式为

左 = -(2^j)

如果 j = -1 或 j = 0，那么上面的公式将无法按预期工作，因为 1<< -1 是 C 中的未定义行为。更多详细信息可在以下链接中找到。

Understanding the arithmetic in `(1 << j) - 1`