0. 原理
基本原理
0s 表示一串 0，1s 表示一串 1。
x ^ 0s = x x & 0s = 0 x | 0s = x x ^ 1s = ~x x & 1s = x x | 1s = 1s x ^ x = 0 x & x = x x | x = x
利用 x ^ 1s = ~x 的特点，可以将一个数的位级表示翻转；利用 x ^ x = 0 的特点，可以将三个数中重复的两个数去除，只留下另一个数。
1^1^2 = 2
利用 x & 0s = 0 和 x & 1s = x 的特点，可以实现掩码操作。一个数 num 与 mask：00111100 进行位与操作，只保留 num 中与 mask 的 1 部分相对应的位。
01011011 & 00111100 -------- 00011000
利用 x | 0s = x 和 x | 1s = 1s 的特点，可以实现设值操作。一个数 num 与 mask：00111100 进行位或操作，将 num 中与 mask 的 1 部分相对应的位都设置为 1。
01011011 | 00111100 -------- 01111111
位与运算技巧
n&(n-1) 去除 n 的位级表示中最低的那一位 1。例如对于二进制表示 01011011，减去 1 得到 01011010，这两个数相与得到 01011010。
01011011 & 01011010 -------- 01011010
n&(-n) 得到 n 的位级表示中最低的那一位 1。-n 得到 n 的反码加 1，也就是 -n=~n+1。例如对于二进制表示 10110100，-n 得到 01001100，相与得到 00000100。
10110100 & 01001100 -------- 00000100
n-(n&(-n)) 则可以去除 n 的位级表示中最低的那一位 1，和 n&(n-1) 效果一样。
移位运算
\>\> n 为算术右移，相当于除以 2n，例如 -7 \>\> 2 = -2。
11111111111111111111111111111001 >> 2 -------- 11111111111111111111111111111110
\>\>\> n 为无符号右移，左边会补上 0。例如 -7 \>\>\> 2 = 1073741822。
11111111111111111111111111111001 >>> 2 -------- 00111111111111111111111111111111
<< n 为算术左移，相当于乘以 2n。-7 << 2 = -28。
11111111111111111111111111111001 << 2 -------- 11111111111111111111111111100100
mask 计算
要获取 111111111，将 0 取反即可，~0。
要得到只有第 i 位为 1 的 mask，将 1 向左移动 i-1 位即可，1<<(i-1) 。例如 1<<4 得到只有第 5 位为 1 的 mask ：00010000。
要得到 1 到 i 位为 1 的 mask，(1<<i)-1 即可，例如将 (1<<4)-1 = 00010000-1 = 00001111。
要得到 1 到 i 位为 0 的 mask，只需将 1 到 i 位为 1 的 mask 取反，即 ~((1<<i)-1)。
Java 中的位操作
static int Integer.bitCount(); // 统计 1 的数量 static int Integer.highestOneBit(); // 获得最高位 static String toBinaryString(int i); // 转换为二进制表示的字符串
1. 统计两个数的二进制表示有多少位不同
- Hamming Distance (Easy)
Input: x = 1, y = 4 Output: 2 Explanation: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ The above arrows point to positions where the corresponding bits are different.
对两个数进行异或操作，位级表示不同的那一位为 1，统计有多少个 1 即可。
public int hammingDistance(int x, int y) { int z = x ^ y; int cnt = 0; while(z != 0) { if ((z & 1) == 1) cnt++; z = z >> 1; } return cnt; }
使用 z&(z-1) 去除 z 位级表示最低的那一位。
public int hammingDistance(int x, int y) { int z = x ^ y; int cnt = 0; while (z != 0) { z &= (z - 1); cnt++; } return cnt; }
可以使用 Integer.bitcount() 来统计 1 个的个数。
public int hammingDistance(int x, int y) { return Integer.bitCount(x ^ y); }
2. 数组中唯一一个不重复的元素
136. Single Number (Easy)
Input: [4,1,2,1,2] Output: 4
两个相同的数异或的结果为 0，对所有数进行异或操作，最后的结果就是单独出现的那个数。
public int singleNumber(int[] nums) { int ret = 0; for (int n : nums) ret = ret ^ n; return ret; }
3. 找出数组中缺失的那个数
268. Missing Number (Easy)
Input: [3,0,1] Output: 2
题目描述：数组元素在 0-n 之间，但是有一个数是缺失的，要求找到这个缺失的数。
public int missingNumber(int[] nums) { int ret = 0; for (int i = 0; i < nums.length; i++) { ret = ret ^ i ^ nums[i]; } return ret ^ nums.length; }
4. 数组中不重复的两个元素
260. Single Number III (Medium)
Leetcode (opens new window)/ 力扣(opens new window)
两个不相等的元素在位级表示上必定会有一位存在不同。
将数组的所有元素异或得到的结果为不存在重复的两个元素异或的结果。
diff &= -diff 得到出 diff 最右侧不为 0 的位，也就是不存在重复的两个元素在位级表示上最右侧不同的那一位，利用这一位就可以将两个元素区分开来。
public int[] singleNumber(int[] nums) { int diff = 0; for (int num : nums) diff ^= num; diff &= -diff; // 得到最右一位 int[] ret = new int[2]; for (int num : nums) { if ((num & diff) == 0) ret[0] ^= num; else ret[1] ^= num; } return ret; }
5. 翻转一个数的比特位
190. Reverse Bits (Easy)
Leetcode (opens new window)/ 力扣(opens new window)
public int reverseBits(int n) { int ret = 0; for (int i = 0; i < 32; i++) { ret <<= 1; ret |= (n & 1); n >>>= 1; } return ret; }
如果该函数需要被调用很多次，可以将 int 拆成 4 个 byte，然后缓存 byte 对应的比特位翻转，最后再拼接起来。
private static Map<Byte, Integer> cache = new HashMap<>(); public int reverseBits(int n) { int ret = 0; for (int i = 0; i < 4; i++) { ret <<= 8; ret |= reverseByte((byte) (n & 0b11111111)); n >>= 8; } return ret; } private int reverseByte(byte b) { if (cache.containsKey(b)) return cache.get(b); int ret = 0; byte t = b; for (int i = 0; i < 8; i++) { ret <<= 1; ret |= t & 1; t >>= 1; } cache.put(b, ret); return ret; }
6. 不用额外变量交换两个整数
a = a ^ b; b = a ^ b; a = a ^ b;
