Java中的二进制与位运算
正文
二进制是计算技术中广泛采用的一种数制。二进制数据是用0和1两个数码来表示的数。计算机的基础便是二进制，再早期的设计中常用的进制主要为10进制，但由于使用电子管表示十种状态过于复杂，所以所有的电子计算机中只有两种基本的状态，开和关。
在本片文章中，我会粗浅的说明二进制的部份知识、Java中二进制的基本运算和多种语言通用的的二进制位运算。
原码、反码、补码
- 原码
一个整数的二进制表示，以int类型为例，int类型占据4个字节，共32位。
5的原码为：00000000 00000000 00000000 00000101
-5的原码为：10000000 00000000 00000000 00000101
- 反码
正数的反码与原码相同，而负数的反码，是该负数除开符号位，所有位取反。
5的反码为：00000000 00000000 00000000 00000101
-5的反码为：11111111 11111111 11111111 11111010
- 补码
正数的补码与原码相同，负数的补码为反码最低位加1.
5的补码为：00000000 00000000 00000000 00000101
-5的反码为：11111111 11111111 11111111 11111010 + 1 = 11111111 11111111 11111111 11111011
简记：
正数：原码 = 反码 = 补码
负数：反码 = 原码除符号位逐位取反
补码 = 反码 + 1
Java中的二进制
对于二进制，有三点需要注意：
- 二进制原码的最高位是符号位，0为正数，1为负数
- Java中没有无符号数（C++中的uint32_t）
- 计算机采用补码数进行运算
以byte类型为例，byte类型占据1个字节，共8个进制。
对于十进制整数5，二进制真值为101，原码表示为0000 0101。
对于十进制整数-5，二进制真值为-101，原码表示为1000 0101。
所以，对于带符号位的8位二进制数的表示范围是 1111 1111 ~ 0111 1111，既-127 ~ 127（-（2^7 – 1） ~ 2^7 – 1）。
而在Java中，负数使用的是补码表示，所以Java中byte类型的表示范围实际上是1000 0000 ~ 0111 1111，既-128 ~ 127（-2^7 ~ 2^7 – 1）。
至于为什么计算机采用补码数进行运算，简单地说是为了提高效率，数学定义的加减法，在计算机中仅通过加法便能完成两种运算。想了解更多可点击：计算机为什么采用补码进行运算
位运算
以下的计算演示均以int作为数据类型
5：00000000 00000000 00000000 00000101
-5：11111111 11111111 11111111 11111011
10：00000000 00000000 00000000 00001010
-10：11111111 11111111 11111111 11110110
- <<（带符号左移）
一个数的各二进制位全部左移若干位，左边的二进制位丢弃，右边补0。
对于正数，则每左移一位，相当于该数乘以2。
5 << 2 = 00000000 00000000 00000000 00010100
-5 << 2 = 11111111 11111111 11111111 11101100
- >>（带符号右移）
将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃。
对于正数，操作数每右移一位，相当于该数除以2。
5 >> 2 = 00000000 00000000 00000000 00000001
-5 >> 2 = 11111111 11111111 11111111 11111110
- >>>（无符号右移）
将一个数的各二进制位全部右移若干位，不分正负，左补0，右边丢弃。
5 >>> 2 = 00000000 00000000 00000000 00000001
-5 >>> 2 = 00111111 11111111 11111111 11111110
- &（与）
0 & 0 = 0；0 & 1 = 0；1 & 0 = 0；1 & 1 = 0（有0则0，全1为1）
5 & 10 = 00000000 00000000 00000000 00000000
-5 & -10 = 11111111 11111111 11111111 11110010
- |（或）
0 | 0 = 0；0 | 1 = 1；1 | 0 = 1；1 | 1 = 1（有1则1，全0为0）
5 | 10 = 00000000 00000000 00000000 00001111
-5 | -10 = 11111111 11111111 11111111 11111111
- ^（异或）
0 ^ 0 = 0；0 ^ 1 = 1；1 ^ 0 = 1；1 ^ 1 = 0（相同为0，相异为1）
5 ^ 10 = 00000000 00000000 00000000 00001111
-5 ^ -10 = 00000000 00000000 00000000 00001101
- ~（取反）
将一个数的各二进制位全部取反，即将0变为1，1变0
~5 = 11111111 11111111 11111111 11111010
位运算的部份技巧用法
- 去除二进制中最后一个1
n & (n – 1)
扩展此方法，可以迅速判断一个数是否为2的幂次方
- 交换数据
n = n ^ m;
m = m ^ n;
n = n ^ m;
原理是异或运算符合交换律，并且一个数异或本身等于0，一个数异或0等于本身。
- 使特定二进制位翻转
设一个数n，对应n要翻转的位，该数的对应为1，其余位为零，此数与n对应位异或即可。
如n=1010 1011，使n低四位翻转，n^0000 1111=1010 0100。
- 颠倒整个二进制串
以下是个人代码，进阶建议参考Integer.reverse()方法源码。
int n = 0b11111110_10010100_00011110_10011111;
int M1 = 0b01010101_01010101_01010101_01010101;
int M2 = 0b00110011_00110011_00110011_00110011;
int M3 = 0b00001111_00001111_00001111_00001111;
int M4 = 0b00000000_11111111_00000000_11111111;
n = ((n & M1) << 1) | ((n >>> 1) & M1);
n = ((n & M2) << 2) | ((n >>> 2) & M2);
n = ((n & M3) << 4) | ((n >>> 4) & M3);
n = ((n & M4) << 8) | ((n >>> 8) & M4);
n = (n >>> 16) | (n << 16);