Java 位运算
日常开发中我们使用位运算用的很少，主要是其可读性较差。
但是在计算密集型操作，比如一致性哈希计算、hashmap 扩容、取数据的交集、差集、并集、权限开关位、位操作、移位运算时，位操作的应用就非常广泛了。
1、基础概念
先了解几个基础的概念：机器数、真值、原码、反码、补码。
（1）机器数
无论是代码还是数值，在计算机中都是以二进制的形式存储，而一个数值在计算机中的二进制表示形式就是这个数的机器数。
机器数是有符号位的，在计算机中用一个二进制数的最高位存放符号。正数为 0，负数为 1。
例如 5：
- +5 ：计算机字长为 8 位，它的二进制就是 0000 0101
- -5：计算机字长为 8 位，它的二进制是 1000 0101（原码）
上面两个二进制表示形式就是机器数。
（2）真值
由于机器数的第一位是符号位，所以其形式值就不等于其真值的数值，也就是说 1000 0101 表示的是－5 而不是 133（1000 0101 的十进制是 131，前提是不算最高位为符号位），因此 -5 才是机器数的真值。
（3）原码
原码是一种计算机中对数字的二进制定点表示方法。原码表示法在数值前面增加了一位符号位（即最高位为符号位）：正数该位为 0，负数该位为 1，其余位表示数值的大小。
[ + 5 ] = [0000 0101]（原码）
[ -5 ］= [1000 0101]（原码）
因为第一位是符号位，因此 8 位二进制的取值范围就是［1111 1111，0111 1111］也就是［-127,127］
- 正数的原码是其本身
- 负数的原码是其正数的原码符号位变为 1
注意：0
- 0 的原码是 00000000
- -0 的原码是 10000000
（4）反码
反码是数值存储的一种，但是由于补码更能有效表现数字在计算机中的形式，所以多数计算机一般都不采用反码表示数，反码的表示方法如下:
- 正数的反码是其本身
- 负数的反码是在其原码的基础上，符号位不变，其余各位取反
［＋5］= [00000101]（原码）＝ ［00000101］（反码）
［ - 5］= [10000101]（原码）＝ ［11111010］（反码）
注意：0
- 0 的反码是 00000000
- -0 的反码是 11111111
（5）补码
在计算机系统中，数值一律用补码来表示和存储。原因在于，使用补码，可以将符号位和数值域统一处理；
同时，加法和减法也可以统一处理。补码的表示方法是:
- 正数的补码就是其本身
- 负数的补码是在其原码的基础上，符号位不变，其余各位取反，最后 +1 ，（即在反码的基础上 + 1）
［＋5］= [00000101]（原码）＝ ［00000101］（反码）＝［00000101］（补码）
［ - 5］= [10000101]（原码）＝ ［11111010］（反码）＝［11111011］（补码）
注意：0
- 补码消除了 +0 和 -0 的冗余和歧义，0 的补码只有一个：0000000
（6）小结
计算机中的符号数有三种表示方法，即原码、反码和补码。三种表示方法均有符号位和数值位两部分，符号位都是用 0 表示 “正”，用 1 表示 “负”，而数值位，三种表示方法各不相同。而在计算机系统中，数值一律用补码来表示和存储。
2、位运算
Java 位移操作：(只针对 int 类型的数据有效，java中，一个 int 的长度始终是 32 位，也就是 4 个字节，它操作的都是该整数的二进制数)。也可作用于以下类型，即 byte，short，char，long(它们都是整数形式)。当为这四种类型时，JVM 先把它们转换成 int 型再进行操作。
例如：int 类型占 4 个字节
private int x1 = 0b00000101; // 5
private int x2 = 0b11111111111111111111111111111011; // -5Java 中对位运算的支持有以下几个运算符：
（1）与
- &：与运算
| 结果 | ||
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
（2）或
- |：或运算
| 结果 | ||
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
（3）非
- ~：非运算
| 结果 | |
|---|---|
| 0 | 1 |
| 1 | 0 |
（4）异或
- ^：异或运算（半加运算：不带进位的二进制加法）
| 结果 | ||
|---|---|---|
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
异或有一些性质，在一些场景下使用它们比较高效：
- 交换律：任意交换因子位置，结果不变
- 结合律：（a ^ b）^ c = a ^ （b ^ c）
- 对任何数 x，都有 x ^ x = 0，x ^ 0 = x，同自己求异或为 0，同 0 求异或为自己：可以用来比较两个数值是否相等
- 自反性：A ^ B ^ B = A ^ 0 = A，连续和同一个因子做异或运算，最终结果为自己
（5）左移
- <<：左移
m << n 含义：把整数 m 表示的二进制数左移 n 位，高位移出舍弃 n 位，低位补 0（会出现整数变成负数的可能）。
要注意的是 n < 32，Java 中 int 占据 4 字节 32 位，最高位表示符号，其余位表示数值：
| 十进制 | 二进制 | 结果 |
|---|---|---|
| 1 | 0000 0000 0000 0000 0000 0000 0000 0001 | 1 |
| 1 << 31 | 1000 0000 0000 0000 0000 0000 0000 0000 | -2147483648 |
| 1 << 32 | 0000 0000 0000 0000 0000 0000 0000 0001 | 1 |
为什么 1 左移 31 后变为负数了，因为此时发生了溢出。
在 Java 中 int 型的范围是 [-2147483648, 2147483647]
| 十进制 | 二进制补码 |
|---|---|
| 2^31 - 1 = 2147483647 | 0111 1111 1111 1111 1111 1111 1111 1111 |
| 0 | 0000 0000 0000 0000 0000 0000 0000 0000 |
| - （2^31 - 1）= - 2147483647 | 1000 0000 0000 0000 0000 0000 0000 0001 |
| - 2147483648 | 1000 0000 0000 0000 0000 0000 0000 0000 |
由于 Java int 型占 4 个字节 32位，最高位表示符号，所以最大只能表示 0111 1111 1111 1111 1111 1111 1111 1111 即 2^31 - 1。
正常而言，Java 中 int 能表示的最小值应该是 -（2^31 - 1），即 1000 0000 0000 0000 0000 0000 0000 0001。
但是如果此时让 2^31 -1 + 1，就会变成 1000 0000 0000 0000 0000 0000 0000 0000，最高位为 1，表示负数，本来这个结果表示原码的 -0，但是我们现在计算机存储二进制用的是补码，在补码中消除了 +0 和 -0 的歧义和冗余，0 只有一个表达式 00000000 00000000 00000000 00000000。
所以（Java 环境下）计算机遇到了 1000 0000 0000 0000 0000 0000 0000 0000 的情况时，就有些不知所措，并不知道发生了 Java 整形溢出，如果按照正常输出，这个数值应该是补码的 0，但是 Java 对此做了处理，利用这个特殊的补码扩展了 Java 整形的下限，将 int 的最小值变为 - 2147483648。即：-（2^31 - 1） - 1
注意：Java 中没有无符号左移
小结：m << n 在数字没有溢出的前提下，对于正数和负数，左移 n 位都相当于 m 乘以 2 的 n 次方。
（6）右移
- >>：右移
m >> n 的含义：把整数 m 表示的二进制数右移 n 位，高位补符号位
- m 为正数，高位全补 0
- m 为负数，高位全补 1
小结：
- m >>n 即相当于 m 除以 2 的 n 次方，得到的结果为整数时，就作为结果。如果结果为小数，此时会出现两种情况：
- 如果 m 为正数，得到的商会无条件的舍弃小数位；
- 如果 m 为负数，舍弃小数部分，然后把整数部分 +1 得到位移后的值。
（7）无符号右移
- >>>：无符号右移
m >>> n：整数 m 表示的二进制数右移 n 位，不论正负数，最高位补 0
