常用技巧
位运算是算法题里比较特殊的一种类型，它们利用二进制位运算的特性进行一些奇妙的优化和计算。常用的位运算符号包括：“∧ 按位异或”、“& 按位与”、“| 按位或”、“~ 取反”、“<< 算术左移”和“>> 算术右移”。以下是一些常见的位运算特性，其中 0s 和 1s 分别表示只由 0 或 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 |
除此之外，n & (n - 1) 可以去除 n 的位级表示中最低的那一位，例如对于二进制表示 11110100，减去 1 得到 11110011，这两个数按位与得到 11110000。n & -n 可以得到 n 的位级表示中最低的那一位，例如对于二进制表示 11110100，取负得到 00001100，这两个数按位与得到 00000100。还有更多的并不常用的技巧，若读者感兴趣可以自行研究，这里不再赘述。
位运算基础问题
461. Hamming Distance
对两个数进行按位异或操作，统计有多少个 1 即可。
190. Reverse Bits
使用算术左移和右移，可以很轻易地实现二进制的翻转。
136. Single Number
我们可以利用 x ∧ x = 0 和 x ∧ 0 = x 的特点，将数组内所有的数字进行按位异或。出现两次的所有数字按位异或的结果是 0，0 与出现一次的数字异或可以得到这个数字本身。
二进制特性
利用二进制的一些特性，我们可以把位运算使用到更多问题上。例如，我们可以利用二进制和位运算输出一个数组的所有子集。假设我们有一个长度为 n 的数组，我们可以生成长度为 n 的所有二进制，1 表示选取该数字，0 表示不选取，这样我们就获得了 2^n 个子集。
342. Power of Four
首先我们考虑一个数字是不是 2 的（整数）次方：如果 n & (n - 1) 为 0，那么这个数是 2 的次方。如果这个数也是 4 的次方，那二进制表示中 1 的位置必须为奇数位。
318. Maximum Product of Word Lengths
怎样快速判断两个字母串是否含有重复数字呢？可以为每个字母串建立一个长度为 26 的二进制数字，每个位置表示是否存在该字母。如果两个字母串含有重复数字，那它们的二进制表示的按位与不为 0。
338. Counting Bits
本题可以利用动态规划和位运算进行快速的求解。定义一个数组 dp，其中 dp[i] 表示数字 i 的二进制含有 1 的个数。对于第 i 个数字，如果它二进制的最后一位为 1，那么它含有 1 的个数则为 dp[i-1] + 1；如果它二进制的最后一位为 0，那么它含有 1 的个数和其算术右移结果相同，即 dp[i>>1]。
练习
268. Missing Number
Single Number 的变种题。除了利用二进制，也可以使用高斯求和公式。
693. Binary Number with Alternating Bits
利用位运算判断一个数的二进制是否会出现连续的 0 和 1。
476. Number Complement
二进制翻转的变种题。
260. Single Number III
Single Number 的 follow-up，需要认真思考如何运用位运算求解。