程序中的所有数在计算机内存中都是以二进制的形式储存的，位运算就是直接对整数在内存中的二进制位进行操作。有或，与，亦或，非等。
位运算符
| 含义 | 运算符 | 示例 |
|---|---|---|
| 左移 | << |
0011 << 1 == 0110 |
| 右移 | >> |
0110 >> 1 == 0011 |
| 按位或 | | |
0011 | 1011 == 1011 |
| 按位与 | & |
0011 & 1011 == 0011 |
| 按位取反 | ~ |
!0011 == 1100 |
| 按位亦或 | ^ |
0011 ^ 1011 == 1000 |
亦或 - XOR
亦或相同为0，不同为一，也可以理解为不进位的加法。亦或有以下的一些特点：
- x ^ 0 = x
- x ^ x = 0
- x ^ (~x) = 1s // 1s表示全1，也就是 ~0
- x ^ 1s = ~x
- c = a ^ b，a ^ c = b，b ^ c = a // 交换律
- a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c // 结合律
一些移位的公式
- 将 x 最后边的 n 位 置 0：x & (~0 << n)
- 获取 x 的第 n 位值（0 或者 1）： (x >> n) & 1
- 获取 x 的第 n 位的幂值：x & (1 << n)
- 仅将第 n 位置为 1：x | (1 << n)
- 仅将第 n 位置为 0：x & (~ (1 << n))
- 将 x 最高位至第 n 位（含）清零：x & ((1 << n) - 1)
常用的位运算
- 判断奇偶性
x % 2 == 1 等价于 x & 1 == 1
x % 2 == 0 等价于 x & 1 == 0
- 乘以2与除以2
x * 2 等价于 x << 1
x / 2 等价于 x >> 1
- 清零最低位的1
x = x & (x - 1)
- 得到最低位的1
x = x & -x
- x & ~x == 0