定义
- 定义：其实说白了，位运算就是直接对整数在内存中的二进制位进行操作
- 特点：位运算直接对内存数据进行操作，不需要转成十进制，速度很快
基本位运算符
- and( & ) : 通常用于二进制位操作，如一个数&1的结果就是取二进制的最末尾，可以用来判断整数奇偶
- or( | ) : 通常用于二进制定位上的无条件赋值，例如一个数or1的结果就是把二进制最末位强行变成1,若要变成0则减1就可以了，实际意义就是把这个数强行变成最接近的偶数
- xor( ^ ) : 通常用于对二进制的特定一位进行取反，可以对两个数进行交换
- not( ~ ) : 取反，注意的是整数类型有没有符号，如果是无符号整数，那么得到的值为其与上界的差
- left shift( « ) : 左移，在二进制数每添一位0就相当于乘2，因此每左移一位就相当于乘2；并且在常量的定义上，比如可以通过
1 << 16来表示65535
对应与集合运算则是交集、并集、差集和补集，假设集合 A 是 {0, 3, 5, 6}，集合 B 是 {0, 2, 4, 6}，全集为 {0, 1, 2, 3, 4, 5, 6, 7}那么：
&交集 Intersection{0, 6}|并集 Union{0, 2, 3, 4, 5, 6}^差集 Symmetric difference{2, 3, 4, 5}~补集 Complement{1, 3, 5, 7}
位 运算符简单应用
经典题型：做数独时我们需要27个Hash表来统计每一行、每一列和每一个小九宫格里已经有哪些数了。此时，我们可以用27个小于2^9的整数进行记录。例如，一个只填了2和5的小九宫格就用数字18表示（二进制为000010010），而某一行的状态为511则表示这一行已经填满。需要改变状态时我们不需要把这个数转成二进制修改后再转回去，而是直接进行位操作。在搜索时，把状态表示成整数可以更好地进行判重等操作。
| 功能 | 位运算 |
|---|---|
| 去掉最后一位 | x » 1 |
| 最后加一个0 | x « 1 |
| 最后加一个1 | (x « 1) + 1 |
| 把最后一位变成1 | x | 1 |
| 把最后一位变成0 | (x | 1) - 1 |
| 最后一位取反 | x ^ 1 |
| 把右数第k位变成1 | x | (1 « (k-1)) |
| 把右数第k位变成0 | x & ~(1 « (k-1)) |
| 右数第k位取反 | x ^ (1 « (k-1)) |
| 取末三位 | x & 7 |
| 取末k位 | x & ( ( 1 « k ) -1) |
| 取右数第k位 | x » (k -1) & 1 |
| 把末k位变成1 | x | ( ( 1 « k) - 1 ) |
| 末k位取反 | x ^ ( ( 1 « k) -1 ) |
| 把右边连续的1变成0 | x & (x + 1) |
| 把右起第一个0变成1 | x | (x+1) |
| 把右边连续的0变成1 | x | (x-1) |
| 取右边连续的1 | (x ^ (x+1)) » 1 |
| 去掉右边第一个1的左边(树状数组) | x & (x ^ (x-1)) |
如何在数组中对指定位置置1
就像上面表格提到的，把右数第k位变成1，这里也是这个原理，但是要注意数组中，一般整型32位，所以
//在第i个位置写i
for (i = 0; i < 40; i ++) {
b[i / 32] |= ( 1 << (i%32) ) ```> 判断奇偶
只需要根据最末尾是0还是1即可判定，为0就是偶数，为1就是奇数
```c
i & 1
交换两数
a ^= b 即 a = (a ^ b)；b ^=a即b = (b^a) = b^(a^b)，由于^满足交换律，b = b^b^a，因为一个数和自己异或的结果为0，并且0与任何数异或都不变，所以b = a；a ^= b 相当于a = a^b=(a^b)^a = b
if (a != b){
a ^= b;
b ^= a;
a ^= b;
}
变换符号，把正数变为负数，负数变为正数
变换符号只需要取反加1即可
~a + 1
求绝对值
方法1：对于负数可以通过对其取反加1来得到整数，先移位来取符号为，int i = a » 31；如果a为正数，i等于0，如果为负数，i等于-1，
int i = a >> 31;
return i == 0 ? a : (~a + 1);
方法2：任何数，与0异或都保持不变，与-1(0xFFFFFFFFF)异或相当于取反，因此a与i异或再减i也可以得到绝对值
int i = a >> 31;
return ((a ^ i) - i);