前言
LeetCode死磕系列五： 位运算
位运算，在性能上是超过加减乘除的，只不过，费些脑细胞。基础的与& 或| 异或^ 运算，以及左移动、右移。
常用操作
&、| 、^、>>、<<、>>>
假设整数变量 A 的值为 60 和变量 B 的值为 13：
| 操作符 | 描述 | 例子 | ||
|---|---|---|---|---|
| ＆ | 如果相对应位都是1，则结果为1，否则为0 | （A＆B），得到12，即0000 1100 | ||
| \ | 如果相对应位都是 0，则结果为 0，否则为 1 | （A \ | B）得到61，即 0011 1101 | |
| ^ | 如果相对应位值相同，则结果为0，否则为1 | （A ^ B）得到49，即 0011 0001 | ||
| 〜 | 按位取反运算符翻转操作数的每一位，即0变成1，1变成0。 | （〜A）得到-61，即1100 0011 | ||
| << | 按位左移运算符。左操作数按位左移右操作数指定的位数。 | A << 2得到240，即 1111 0000 | ||
| >> | 按位右移运算符。左操作数按位右移右操作数指定的位数。 | A >> 2得到15即 1111 | ||
| >>> | 按位右移补零操作符。左操作数的值按右操作数指定的位数右移，移动得到的空位以零填充。 | A>>>2得到15即0000 1111 |
异或
2 ^ 2 = 0;
与
0 & 1 = 0；
1 & 1 = 0；
n & (n-1)
10000000；
01111111;
<----- binary ---->
n n n-1 n&(n-1)
-- ---- ---- -------
0 0000 0111 0000 *
1 0001 0000 0000 *
2 0010 0001 0000 *
3 0011 0010 0010
4 0100 0011 0000 *
5 0101 0100 0100
6 0110 0101 0100
7 0111 0110 0110
8 1000 0111 0000 *
9 1001 1000 1000
10 1010 1001 1000
11 1011 1010 1010
12 1100 1011 1000
13 1101 1100 1100
14 1110 1101 1100
15 1111 1110 1110
可以看到，其第一个方式是用于判断是否为2的幂次，n&(n-1)的结果为0的话，则为2的幂次。
从运算结果分析（以12为例）：
12二进制表示为：1100，减去1之后，为1011，可以发现，减去1之后，是将该数字的二进制的最右边的1改为0，n&(n-1)之后的结果为1000，比较1100和1000，这个操作可以总结为：将当前数字二进制最右边的1去除。最右边的1左边部分不变。所以，也可可以用于统计数字的二进制中1的个数问题。
补码：
~x + 1 是 x的补码;
补码
1 + 11111111111111111 = 000000000000000000;
2 + 11111111111111110 = 000000000000000000
(s | 1<<k)
s: 集合（二进制表示包含的元素）
集合元素$s = {1,4,6}$ 则 $s = 1010010{2} = 82{10}$
k: 元素
将元素
k放入集合s中
举例说明
当前$s=82$, 此时$k=2$，将$k$放入集合$s$中
- $(1<<k) = 4 = 100_{2}$
- $(s | 1<< k) == 1010110{2} == 86{10}$
神奇的操作，适用于压缩状态dp
LeetCode & 剑指offer 位运算题目整理
- 面试题15：二进制中1的个数
- 136 Single Number
LeetCode 位运算题目整理
面试题15：二进制中1的个数
public static int numberOf(int n){
// n & (n - 1) 会消除 n 中最后一位中的 1。
int res = 0;
while (n != 0){
res++;
n &= (n-1);
}
return res;
}
136 Single Number
这题是去除数组中的重复元素（给的测试集是只有一个不重复的元素），用了异或运算，
思路：
相等的数相异或结果为0，0和任何数相异或结果为这个数本身。根据这个特点，可以先设置一个初始值为0，然后分别和数组中的每个元素相异或，最后保留的肯定为唯一一个不重复的值。
相等的元素相异或的值为0，不是特指相等的元素必须相连，也可以不相连。
public singleNumber(int[] nums){
int res = 0;
for( int i : nums){
res ^= i;
}
return res;
}
