Puzzle 27: Shifty i's

Java位运算的右操作数会被暗中求余

三种位移运算符（Shift operators）：

• << left shift
• >>signed right shift
• >>> unsigned right shift

这里想测试的是-1，-1的二进制补码表示为：11111111111111111111111111111111（32位1），注意下面的代码片段的输出。

for (int i = 0; i < 33; i++) {

System.out.println("-1 >> " + i + ": " + Integer.toBinaryString(-1 >> i));

}

System.out.println();

for (int i = 0; i < 33; i++) {

System.out.println("-1 >>> " + i + ": " + Integer.toBinaryString(-1 >>> i));

}

System.out.println();

for (int i = 0; i < 33; i++) {

System.out.println("-1 << " + i + ": " + Integer.toBinaryString(-1 << i));

}

输出为：

-1 >> 0: 11111111111111111111111111111111

-1 >> 1: 11111111111111111111111111111111

-1 >> 2: 11111111111111111111111111111111

-1 >> 3: 11111111111111111111111111111111

-1 >> 4: 11111111111111111111111111111111

-1 >> 5: 11111111111111111111111111111111

-1 >> 6: 11111111111111111111111111111111

-1 >> 7: 11111111111111111111111111111111

-1 >> 8: 11111111111111111111111111111111

-1 >> 9: 11111111111111111111111111111111

-1 >> 10: 11111111111111111111111111111111

-1 >> 11: 11111111111111111111111111111111

-1 >> 12: 11111111111111111111111111111111

-1 >> 13: 11111111111111111111111111111111

-1 >> 14: 11111111111111111111111111111111

-1 >> 15: 11111111111111111111111111111111

-1 >> 16: 11111111111111111111111111111111

-1 >> 17: 11111111111111111111111111111111

-1 >> 18: 11111111111111111111111111111111

-1 >> 19: 11111111111111111111111111111111

-1 >> 20: 11111111111111111111111111111111

-1 >> 21: 11111111111111111111111111111111

-1 >> 22: 11111111111111111111111111111111

-1 >> 23: 11111111111111111111111111111111

-1 >> 24: 11111111111111111111111111111111

-1 >> 25: 11111111111111111111111111111111

-1 >> 26: 11111111111111111111111111111111

-1 >> 27: 11111111111111111111111111111111

-1 >> 28: 11111111111111111111111111111111

-1 >> 29: 11111111111111111111111111111111

-1 >> 30: 11111111111111111111111111111111

-1 >> 31: 11111111111111111111111111111111

-1 >> 32: 11111111111111111111111111111111

-1 >>> 0: 11111111111111111111111111111111

-1 >>> 1: 1111111111111111111111111111111

-1 >>> 2: 111111111111111111111111111111

-1 >>> 3: 11111111111111111111111111111

-1 >>> 4: 1111111111111111111111111111

-1 >>> 5: 111111111111111111111111111

-1 >>> 6: 11111111111111111111111111

-1 >>> 7: 1111111111111111111111111

-1 >>> 8: 111111111111111111111111

-1 >>> 9: 11111111111111111111111

-1 >>> 10: 1111111111111111111111

-1 >>> 11: 111111111111111111111

-1 >>> 12: 11111111111111111111

-1 >>> 13: 1111111111111111111

-1 >>> 14: 111111111111111111

-1 >>> 15: 11111111111111111

-1 >>> 16: 1111111111111111

-1 >>> 17: 111111111111111

-1 >>> 18: 11111111111111

-1 >>> 19: 1111111111111

-1 >>> 20: 111111111111

-1 >>> 21: 11111111111

-1 >>> 22: 1111111111

-1 >>> 23: 111111111

-1 >>> 24: 11111111

-1 >>> 25: 1111111

-1 >>> 26: 111111

-1 >>> 27: 11111

-1 >>> 28: 1111

-1 >>> 29: 111

-1 >>> 30: 11

-1 >>> 31: 1

-1 >>> 32: 11111111111111111111111111111111

-1 << 0: 11111111111111111111111111111111

-1 << 1: 11111111111111111111111111111110

-1 << 2: 11111111111111111111111111111100

-1 << 3: 11111111111111111111111111111000

-1 << 4: 11111111111111111111111111110000

-1 << 5: 11111111111111111111111111100000

-1 << 6: 11111111111111111111111111000000

-1 << 7: 11111111111111111111111110000000

-1 << 8: 11111111111111111111111100000000

-1 << 9: 11111111111111111111111000000000

-1 << 10: 11111111111111111111110000000000

-1 << 11: 11111111111111111111100000000000

-1 << 12: 11111111111111111111000000000000

-1 << 13: 11111111111111111110000000000000

-1 << 14: 11111111111111111100000000000000

-1 << 15: 11111111111111111000000000000000

-1 << 16: 11111111111111110000000000000000

-1 << 17: 11111111111111100000000000000000

-1 << 18: 11111111111111000000000000000000

-1 << 19: 11111111111110000000000000000000

-1 << 20: 11111111111100000000000000000000

-1 << 21: 11111111111000000000000000000000

-1 << 22: 11111111110000000000000000000000

-1 << 23: 11111111100000000000000000000000

-1 << 24: 11111111000000000000000000000000

-1 << 25: 11111110000000000000000000000000

-1 << 26: 11111100000000000000000000000000

-1 << 27: 11111000000000000000000000000000

-1 << 28: 11110000000000000000000000000000

-1 << 29: 11100000000000000000000000000000

-1 << 30: 11000000000000000000000000000000

-1 << 31: 10000000000000000000000000000000

-1 << 32: 11111111111111111111111111111111

以上移动规律可以描述为：

• 对-1进行signed right shift >>，值不变。
• 对-1进行unsigned right shift >>，二进制表达形式会从32个递变成31, 30, ..., 1个1，再开始循环。
• 对-1进行 left shift <<，天然就是带符号的。
• 以上三组结果都没有一个值为0的。

上面的输出中，最后一行让人困惑：-1 << 32的结果是：11111111111111111111111111111111，而不是0. 这是因为在JLS 15.19中的规定：

• If the promoted type of the left-hand operand is int, only the five lowest-order bits of the right-hand operand are used as the shift distance. （如果左边的操作数为int型，那么位移的举例是右边操作数的低五位。）这等于是说：对于右操作数为int型的，X ~ Y = X ~ (Y %32), ~代表<<, >>, >>>.

这个移动法则对于三个位移操作符都适用。这么做，移动的距离就限制在0~31=2^5-1了。int型数的补码也就32位。回头看，32的低5位是什么？00000. 所以 -1 << 32 == -1 << 0。

同样，对于long，有类似的规定：

• If the promoted type of the left-hand operand is long, then only the six lowest-order bits of the right-hand operand are used as the shift distance. 这等于是说：对于右操作数为long型的，X ~ Y = X ~ (Y %64), ~代表<<, >>, >>>.

按照上面粗体的等价说法，即使右操作数为负数，也不能改变移动的方向。书中的最后一段没怎么搞懂，稍后（TODO）

附

1. Puzzle 26: In the Loop
2. JLS 15.19 Shift Operators
3. TODO 从补码的角度研究Java的模运算是如何定义和运行的。