位运算基础：与、或、异或、取反、左移、右移
位运算，说白了就是直接操作二进制位。很多刚入行的同学觉得这东西离自己很远，觉得现代编译器会优化，没必要手动搞。嗯，我以前也这么想，直到有一次在嵌入式项目里，一个整型标志位判断拖慢了整个中断响应……从那以后，我再也不敢小看位运算了。
位运算最大的魅力在于：它能在常数时间内完成很多看似复杂的判断。没有分支预测失败，没有内存访问延迟，就是几条 CPU 指令的事。
六种基本位运算操作
先过一遍基础。这六种操作，我建议你背到条件反射的程度。
| 运算符 | 名称 | 规则 | 示例（8位） |
|---|---|---|---|
& |
按位与 | 同1为1，否则为0 | 0b1100 & 0b1010 = 0b1000 |
| |
按位或 | 有1为1，否则为0 | 0b1100 | 0b1010 = 0b1110 |
^ |
按位异或 | 相同为0，不同为1 | 0b1100 ^ 0b1010 = 0b0110 |
~ |
按位取反 | 0变1，1变0 | ~0b1100 = 0b0011（仅低4位） |
<< |
左移 | 高位丢弃，低位补0 | 0b0001 << 2 = 0b0100 |
>> |
右移 | 低位丢弃，高位补符号位 | 0b1100 >> 2 = 0b1111（算术右移） |
>> 是算术右移，>>> 是逻辑右移。我见过有人在这上面栽跟头，移位后符号位扩散，结果完全不对。
位运算的常见套路
光知道操作符不够，得会用。下面这几个套路，我在代码审查里几乎每周都能用到。
1. 判断奇偶性
最经典的用法。不用取模，直接看最低位。
// 判断 n 是否为奇数
bool isOdd = (n & 1) == 1;
// 判断 n 是否为偶数
bool isEven = (n & 1) == 0;为什么快？n % 2 编译器可能会优化成 n & 1，但手动写出来，语义更清晰，也省去了对编译器优化能力的依赖。
2. 判断是否为 2 的幂
这个技巧我经常在内存分配器里用。2 的幂在二进制里只有一个 1。
// 判断 n 是否为正的 2 的幂
bool isPowerOfTwo = (n > 0) && ((n & (n - 1)) == 0);原理很简单：n - 1 会把最低位的 1 变成 0，后面的 0 全变成 1。如果 n & (n - 1) == 0，说明 n 只有一个 1。
n = 0 会返回 true（因为 0 & (-1) == 0），所以一定要加 n > 0 的前置条件。我曾经在哈希表扩容逻辑里忘了这个，结果 size 为 0 时也走了 2 的幂优化路径，死循环了半小时。
3. 交换两个数（不用临时变量）
这个技巧面试常考，但实际项目里我建议少用——可读性差，而且现代编译器对临时变量的优化已经很好了。
a ^= b;
b ^= a;
a ^= b;原理：异或满足交换律和结合律，且 x ^ x = 0，x ^ 0 = x。三步之后，a 和 b 的值就互换了。
4. 取最低位的 1
这个操作在树状数组（Fenwick Tree）里是核心操作。
int lowbit = n & (-n);负数的补码表示是取反加一。-n 和 n 只在最低位的 1 处对齐，其他位都相反。与运算后，就只保留了最低位的那个 1。
如何用位运算实现 O(1) 判断
好了，重点来了。为什么位运算能实现常数时间判断？因为位运算是 CPU 的原语操作，一条指令搞定，不依赖循环、不依赖分支、不依赖内存访问。
我总结了一个核心思路：把「判断条件」编码成「位模式」，然后用位运算一次性提取结果。
案例：判断一个数是否在集合中
假设我们要判断一个字符是不是元音字母（a, e, i, o, u）。常规做法是写个 switch 或者查哈希表，但用位运算可以做到 O(1)。
// 用 32 位整数表示元音字母的位图
// 'a' - 'a' = 0, 'e' - 'a' = 4, 'i' - 'a' = 8, 'o' - 'a' = 14, 'u' - 'a' = 20
const int VOWEL_BITMAP = (1 << 0) | (1 << 4) | (1 << 8) | (1 << 14) | (1 << 20);
bool isVowel(char c) {
// 只处理小写字母
int idx = c - 'a';
// 越界检查
if (idx < 0 || idx > 25) return false;
// O(1) 判断：检查对应位是否为 1
return (VOWEL_BITMAP >> idx) & 1;
}你看，没有循环，没有分支（除了越界检查），就是两次移位加一次与运算。这就是 O(1) 判断的本质。
案例：判断两个区间是否重叠
这个技巧我在做区间调度时用过。假设区间用 [start, end) 表示，判断两个区间是否重叠，常规做法是 a.start < b.end && b.start < a.end。但如果你把区间编码成位掩码，可以一次判断。
// 假设区间长度不超过 64，用 64 位整数表示
uint64_t rangeToMask(int start, int end) {
// 生成从 start 到 end-1 的位都为 1 的掩码
return ((1ULL << (end - start)) - 1) << start;
}
bool overlap(uint64_t a, uint64_t b) {
// 两个掩码按位与，非零则重叠
return (a & b) != 0;
}当然，这个技巧有局限性——区间长度不能超过位宽。但在很多嵌入式场景里，这个限制是可以接受的。
- 位图法：用整数的每一位表示一个布尔值，一次与运算判断多个条件
- 掩码法：用连续的位段表示数值范围，通过移位和与运算提取信息
- 奇偶法：利用二进制最低位的特性，判断奇偶、符号等简单属性
位运算的避坑指南
我踩过的坑，列出来给你参考。
- 移位位数不要超过类型位宽。在 C/C++ 里，移位位数等于或超过类型位宽是未定义行为。比如
1 << 32在 32 位 int 上是 UB，编译器可能给你任何结果。 - 有符号数的右移是算术右移。负数右移高位补 1，可能导致你预期的 0 没有出现。如果要做逻辑右移，用无符号类型。
- 取反操作要小心类型提升。
~0在 32 位系统上是0xFFFFFFFF，但如果你把它赋值给char，会截断成0xFF。我见过有人用~0做全 1 掩码，结果类型不匹配，高位被截掉了。 - 位运算优先级容易搞错。比如
if (n & 1 == 0)会被解析成if (n & (1 == 0))，结果永远是 0。记住：比较运算符优先级高于位运算符，加括号保平安。
知识体系总览
下面这张图，把位运算的核心知识点串起来了。你可以把它当作速查表。
这张图从六种基本操作出发，延伸到常见套路，再收敛到三种 O(1) 判断模式，最后落到避坑和应用场景。你可以把它当作学习路线图，也可以当作面试前的速查。