Java位运算学习

概述

在学习位运算之前，先说下几个概念：

1. 机器数：一个数字在计算机中的二进制表达形式就叫做机器数。机器数是有符号位的，一个数字二进制的最高位用来表示符号位，正数是0，负数是1。
2. 真值：机器数对应的真正数值称为真值。例如：例：0000 1000的真值 = +000 1000 = +8，1000 1000的真值 = –000 1000 = –8
3. 原码：原码就是机器数。我们以一个字节8位数据举例，例如数字8，它的原码就是0000 1000，而对于-8的话，原码就是1000 1000，首位是符号位；
4. 反码：对正数而言，反码等于原码，而对于负数而言，反码是原码的基础上，符号位不变，剩余的按位取反。如我们还拿-8举例，-8的反码是11110111。
5. 补码：对正数而言，同样，补码等于原码，而对于负数而言，就是在原码的基础上，符号位不变，剩余的按位取反再加1，即在反码的基础上加1。如-8，反码是11110111，补码是11111000。

  在Java中，由于没有无符号位，所以拿int来说，4个字节，占32位，最高位是符号位，0代表是正数，1代表是负数。

// 最小值是 -2的31次方
public static final int MIN_VALUE = 0x80000000;
10000000 00000000 00000000 00000000 => -2147483648;

//最大值是 2的31次方-1
public static final int MAX_VALUE = 0x7fffffff;
01111111 11111111 11111111 11111111 => 2147483647;

这里比较有意思的就是MAX_VALUE + 1 = MIN_VALUE。

  我们在学习计算机组成原理的时候知道，计算机中位运算是通过补码进行的。那现在，我们就可以来看位运算了。

  首先，我们要先了解下，Java都是提供了哪些位运算符，通过JDK官方文档，我们可以知道，Java中有以下为运算符：左位移（<<），右位移（>>），无符号右位移（>>），按位与（&），按位或（|），按位非（～），按位异或（^） ，共七种位运算符，除了按位非是一元运算符，其他的都是二元运算符。

  对于位移运算符来说，有一点需要注意，就是如果操作符左边是int类型，则操作数右边的数将只会在小于2的5次方以下，就是32以下才有效。因为Java中int类型是4个字节，也就是32位，左移超过32，其实等同于左移的减去32。比如数字2左移2位，和左移34位的结果是一致的。对长整型long来说，其实也是类似的，不过不是32，是64而已。
  为了便于测试，我们下面的例子全都是使用8位来进行测试。

左移（<<）

例如将数字2左移2位（以下首位是符号位）：

2的二进制表示为：[0] 0000 0010 十进制：2
左移2位后的结果：[0] 0000 1000 十进制：8

-2的二进制表示为：
原码： [1] 0000 0010    补码：[1] 1111 1110
左移2位后的结果：
补码：[1] 1111 1000    原码：[1] 0000 1000
最终结果是：-8

  这里简单说一点：正数的话，原码，反码，补码是一样的，而负数的话，从补码求原码和从原码求补码是一样的，也就是说补码的补码还是原码。

右移（>>）

同样，使用数字2来测试：

2的二进制表示为：[0] 0000 0010 十进制：2
右移2位后的结果：[0] 0000 0000 十进制：+0

-2的二进制表示为：
原码： [1] 0000 0010    补码：[1] 1111 1110
右移2位后的结果：
补码：[1] 1111 1111    原码：[1] 0000 0001
最终结果是：-1

这里也说一点，右移过程，首位补符号位，而左移，则是低位全部补0。

无符号右移（>>>）

同样，使用数字2来测试：

2的二进制表示为：    [0] 0000 0010 十进制：2
无符号右移2位后的结果：   0000 0000 十进制：0

-2的二进制表示为：
原码： [1] 0000 0010    补码：[1] 1111 1110
无符号右移2位后的结果（这里因为int是32位，所以使用省略号了）：
补码： 0011 .... 1111    原码： 0011 .... 1111
最终结果是：2的30次方-1，使用Windows计算器得出：1073741823

这里其实还要说一点，无符号右移，忽略符号位，首位补0。

按位与（&）

这次我们使用数字3和5，-3和-5，-3和5来测试：

3的二进制表示为：    [0] 0000 0011
5的二进制表示为：    [0] 0000 0101
进行逻辑与之后：    [0]0000 0001 十进制：1

-3的二进制表示为：
原码： [1] 0000 0011    补码：[1] 1111 1101
-5的二进制表示为：
原码：[1] 0000 0101    补码： [1] 1111 1011
补码按位与的结果是：
补码：[1] 1111 1001    原码：[1] 0000 0111 十进制：-7

-3的二进制表示为：
原码： [1] 0000 0011    补码：[1] 1111 1101
5的二进制表示为：    [0] 0000 0101
补码按位与计算的结果是：
补码：[0] 0000 0101    原码：[0] 0000 0101 十进制：5

这里还要说一点，符号位参与位运算。

按位或（|）

这次我们还是使用数字3和5来测试：

3的二进制表示为：    [0] 0000 0011
5的二进制表示为：    [0] 0000 0101
进行按位或之后：    [0]0000 0111 十进制：7

按位非

将操作数的每一位都取反，包括符号位。

这次我们还是使用数字3来测试：

3的二进制表示为：    [0] 0000 0011
进行按位非之后：
补码 [1]1111 1100    原码：[1]0000 0100
十进制：-4

按位异或（^）

这个简单来说，就是相同的为0，不同的为1，包括符号位。

这次我们使用数字-3和5来测试：

-3的二进制表示为：
原码： [1] 0000 0011    补码：[1] 1111 1101
5的二进制补码表示为：    [0] 0000 0101
补码按位异或计算的结果是：
补码：[1] 1111 1000    原码：[1] 0000 1000 十进制：-8

以上测试我们都可以使用Integer.toBinaryString方法来查看元素的二进制形式，注：该方法返回的是元素的补码。

RegularEnumSet的addAll方法

现在我们可以来说一下RegularEnumSet类中addAll的实现了：elements = -1L >>> -universe.length;
比如说，universe数组的长度是5，那么 elements = -1L >>> -5;
在JDK文档中有说明：

  If the promoted type of the left-hand operand is int, then only the five lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & (§15.22.1) with the mask value 0x1f (0b11111). The shift distance actually used is therefore always in the range 0 to 31, inclusive.
  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. It is as if the right-hand operand were subjected to a bitwise logical AND operator & (§15.22.1) with the mask value 0x3f (0b111111). The shift distance actually used is therefore always in the range 0 to 63, inclusive.
以上文档位于：https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.22.1

  所以，如果是位移左侧是int类型，-1 >>> -5 就相当于 -1 >>> (-5 & 0x1f ) ，也就是 -1 >>> (-5 & 11111)，也就是 -1 >>> 27。
  同样，如果左侧是long类型，那么 -1L >>> -5，也就相当于 -1L >>> (-5 & 0x3f) ，也就是 -1L >>> (-5 & 111111)，也就是 -1L >>> 59 。
  对int而言，无论位移多少，最终位移的范围都在0到31之间，或者说，最终位移的距离与32进行多次加减，最终落在0到31之间的值就是真正的位移。而同样，对于long来说，最终位移的范围也会在0到63之间。

本文参考自：

原码, 反码, 补码 详解
https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.19