常见的位运算符(如 AND、OR、XOR 和 NOT)允许我们直接操作整数内部的二进制位。这为我们提供了一个强大的工具箱,不仅能高效地检测重复项、统计置位数(Set Bits)或执行算术运算,还能在解决诸如寻找序列中缺失的数字或优化数据结构空间占用等问题时事半功倍。无论我们要解决哪类问题,掌握位操作技巧都能显著提升我们在编码面试中的解题能力。
简单问题
- 二进制表示
- 关闭最右边的置位
- 检查第 K 位是否置位
- 设置第 K 位
- 对 2 的幂次进行模除
- 出现奇数次的数字
- 判断 2 的幂
- 唯一的置位
- 二进制字符串相加
- 检查整数溢出
- 不使用 XOR 运算符进行异或
- 检查相等
- 检查符号相反
- 交换两个数
- 俄国农民乘法
中等问题
- 最高有效置位
- 最右边的置位
- 统计置位数
- 交换位
- 旋转位
- 三个数中的最小值
- 无分支求最小值
- 大于或等于 n 的最小 2 的幂
- 查找奇偶性程序
- 检查二进制是否为回文
- 生成 n 位格雷码
- 检查稀疏数
- 当 % 和 / 开销较大时的欧几里得算法
- 不使用 *、/ 和 pow() 计算平方
- 循环冗余校验和模 2 除法
- 设置范围内的位
- 检查荒凉数
- 格雷码与二进制互换
困难问题
- 具有相同置位数的下一个更大数
- 用于快速乘法的 Karatsuba 算法
- 最大子数组异或和
- 二进制中翻转一次得到的最长 1 序列
- 具有相同置位数的最近较小和较大数
- 位掩码与动态规划
- 计算奇偶性
- 通过移动明文进行 XOR 加密
- [统计至少有一位相同的数对](https://www.geek