有些代码第一眼看像天书，看懂以后会心一笑。比如x & (x - 1)这一行，既能判断一个数是不是 2 的幂，也能用来数出二进制里到底有多少个 1。再比如x & -x这半行，能把一个整数的最低位的 1 单独拎出来，喂给树状数组就是现成的 lowbit。这就是位运算的日常：看起来绕，但它是少数几种真正贴着 CPU 寄存器逻辑走的技术，每一个与、或、异或、移位都对应一条机器指令，没有分支、没有访存，处理的是“一排开关同时动作”的问题。
这篇文章我就把平时项目里、算法题里、还有写底层工具时真正用得上的位运算技巧挑出来，一共 30 个，按数值运算、位元操作、计数与集合、状态与编码四类做了张总览表。其中 12 个最高频的我会把原理逐帧拆开讲清楚，剩下的给出表达式和用途，后面再用位图去重、权限掩码、N 皇后剪枝、状态压缩 DP 四个完整的实战场景收尾。适合刚接触位运算想建立直觉的读者，也适合写了多年代码但平时只敢用&判断奇偶的老同事——看完这一篇，位运算应该就不再是“天书”了。
1. 先建立位运算直觉：开关、掩码与三条铁律
1.1 一个整数就是一排开关，位运算就是同时拨一排开关
我刚开始学位运算的时候，总觉得六个符号拗口：&、|、^、~、<<、>>。后来换了个角度，一下就通了——把整数看成“一排开关”，而不是“一个数字”。一个 32 位 int 就是 32 个开关，一个 64 位 long long 就是 64 个开关。每个开关只有两个状态：开（1）和关（0）。
&（与）：两个开关都开着，结果才开着。像串联电路，一个断了就全断。|（或）：两个开关只要有一个开着，结果就开着。像并联电路，任何一路通了就通。^（异或）：两个开关状态不同，结果才开着；状态相同，结果就是关的。可以理解为“找不同”。~（取反）：把这一排开关全部拨到相反状态。<<（左移）：整排开关往高位方向挪，低位空出来的位置补 0。>>（右移）：整排开关往低位方向挪，高位空出来的位置按符号位补。
这套“开关直觉”对后面所有技巧都管用。判断奇偶时我们只看最低位那个开关；掩码提取时我们把不想看的开关全部遮住；“置位、清位、取位”这三个基础动作，本质就是“拨一个开关、关一个开关、读一个开关的状态”。
1.2 掩码、最低位与 0-based 位编号约定
掩码（mask）是位运算里最常用的词。一个整数本身就可以当模板用，比如0b1111这个掩码，和任何数做&，结果就只有这个数的低 4 位会留下来，高位的所有位都被清成 0。就好比你在开关柜前面放了一块只留 4 个孔的铁皮，你只能看到那一排开关里的最后 4 个。
约定俗成，位运算里最低位叫 bit 0，从右往左数。1 << n表示“把第 n 位这个开关点亮”，1 << 0就是 1，1 << 3就是 8。很多表达式看着吓人，拆开其实就是“1 左移之后和一个数做与/或/异或”。这里我建议一开始就养成 0-based 的习惯，不然很多代码读起来会错位。比如x & (1 << 3)大家默认是检查第 3 位，而不是“第 4 位”——虽然从人的角度第 3 位是第 4 个开关。
1.3 取位、置位、清位：三个祖传基础动作
几乎所有位运算高阶技巧，都能拆成这三个动作的组合：
// 取第 n 位：右移到最低位，再和 1 做与，得到 0 或 1 int get_bit(int x, int n) { return (x >> n) & 1; } // 置第 n 位为 1：用 1<<n 点亮开关，再用或合并 int set_bit(int x, int n) { return x | (1 << n); } // 清第 n 位为 0：先取反 1<<n，得到一个除第 n 位外全 1 的掩码，再与 int clear_bit(int x, int n) { return x & ~(1 << n); } // 翻第 n 位：异或会改变不同的位 int toggle_bit(int x, int n) { return x ^ (1 << n); }置位为什么用或？因为1 << n只有第 n 位是 1，其他位都是 0，x | 掩码会“强制把第 n 位变成 1”，其他位保持原样。清位为什么用与加取反？因为~(1 << n)只有第 n 位是 0，其他位都是 1，x & 掩码会“强制把第 n 位变成 0”，其他位不动。理解这四个动作，后面 30 个技巧基本就是它们在不同场景下的排列组合。
2. 30 例总览：一张表把所有常用位运算按场景分门别类
这张表我按四个场景分类：数值运算、位元操作、计数与集合、状态与编码。表里的“表达式”我已经做了简化，为了能放进表格里没写完整边界条件，实际使用时请对照第 3 章和上下文补全（比如判断 2 的幂需要x > 0）。
| 分类 | 编号 | 技巧名称 | 核心表达式 | 典型用途 |
|---|---|---|---|---|
| 数值运算 | 1 | 判断奇偶 | x & 1 | 替代取模，循环奇偶判定 |
| 数值运算 | 2 | 乘以 2 的 n 次幂 | x << n | 快速乘法，内存对齐 |
| 数值运算 | 3 | 除以 2 的 n 次幂（非负） | x >> n | 快速除法，二分下标 |
| 数值运算 | 4 | 判断是否为 2 的幂 | x > 0 && (x & (x - 1)) == 0 | 容量校验、检测对齐 |
| 数值运算 | 5 | 向上取整到 2 的幂 | `n--; n | = n >> 1; ...; n++;` |
| 数值运算 | 6 | 取绝对值 | (x ^ (x >> 31)) - (x >> 31) | 无分支绝对值 |
| 数值运算 | 7 | 防溢出的平均值 | (a & b) + ((a ^ b) >> 1) | 二分查找求中值 |
| 数值运算 | 8 | 判断两数是否同号 | (a ^ b) >= 0 | 方向变化、碰撞判断 |
| 数值运算 | 9 | 对 2 的幂取模 | x & (m - 1) | 环形队列、哈希槽位 |
| 数值运算 | 10 | 无临时变量交换两数 | a ^= b; b ^= a; a ^= b; | 原地交换、特殊寄存器场景 |
| 位元操作 | 11 | 检查第 n 位是否为 1 | (x >> n) & 1 | 读取标志位、开关状态 |
| 位元操作 | 12 | 设置第 n 位为 1 | `x | = 1 << n` |
| 位元操作 | 13 | 清除第 n 位为 0 | x &= ~(1 << n) | 取消标记、熄灭开关 |
| 位元操作 | 14 | 翻转第 n 位 | x ^= 1 << n | 切换状态、按钮逻辑 |
| 位元操作 | 15 | 取最低位的 1（lowbit） | x & -x | 树状数组、枚举单个位 |
| 位元操作 | 16 | 清除最低位的 1 | x & (x - 1) | 判 2 幂、位计数 |
| 位元操作 | 17 | 最低位 1 的位置 | __builtin_ctz(x) | 索引定位、快速 log2 |
| 位元操作 | 18 | 最高位 1 的位置 | 31 - __builtin_clz(x) | 估算数量级、求 log2 取整 |
| 位元操作 | 19 | 反转二进制位 | 循环 `(rev <<= 1) | (x & 1)` |
| 位元操作 | 20 | ASCII 大小写切换 | c ^= 32 | 字符格式转换 |
| 计数与集合 | 21 | 统计 1 的个数（软件版） | while (n) { cnt++; n &= n - 1; } | 汉明重量、权限计数 |
| 计数与集合 | 22 | 统计 1 的个数（硬件版） | __builtin_popcount(x) | 最快位计数 |
| 计数与集合 | 23 | 集合求并 | a | b | 合并标志、幂等合并 |
| 计数与集合 | 24 | 集合求交 | a & b | 找公共元素、权限交集 |
| 计数与集合 | 25 | 集合求差 | a & ~b | 排除集合、撤销权限 |
| 计数与集合 | 26 | 判断集合是否有交集 | (a & b) != 0 | 冲突检测、重叠判断 |
| 计数与集合 | 27 | 汉明距离 | __builtin_popcount(a ^ b) | 相似度、编辑距离近似 |
| 计数与集合 | 28 | 枚举一个集合的全部子集 | for (sub = s; sub; sub = (sub - 1) & s) | 组合枚举、DP 子状态 |
| 状态与编码 | 29 | 多段数据打包/解包 | `(a << 24) | (b << 16) |
| 状态与编码 | 30 | 位图标记与查找 | `bits | = 1 << id; (bits >> id) & 1` |
这 30 个技巧不是互相孤立的。第 9 个和第 30 个用在一起就有了位图数组的下标换算；第 15 个和第 28 个用在一起就有了 N 皇后最简写法；第 21 个和第 27 个本来就是一回事。下一章我从表里挑出真正最高频、最能长出其他技巧的 12 个，把每个表达式的原理掰开揉碎讲透。
3. 12 个高频模式逐帧拆解：从表达式到原理
3.1 判奇偶与 2 的幂判断：x & 1和(x & (x - 1)) == 0
先说x & 1。一个数的二进制最低位是 0 就是偶数，是 1 就是奇数。所以x & 1直接得到奇偶性，不需要走除法器。实话讲，现代编译器开优化之后x % 2 == 0生成的机器码也是and 1，两者没什么性能差别。但x & 1写出来会让读代码的人第一时间注意到“我在看最低位”，这个语义更直接。我在做循环交替、表格斑马纹、队列奇偶槽位分配时经常用它。
x & (x - 1)这个式子太经典了，值得背下来。它的原理是：x - 1会让最低位的那个 1 变成 0，同时它后面所有 0 全部变成 1。比如 x = 12 = 0b1100，x - 1 = 11 = 0b1011，两个数做与运算，最高位两个 1 保留，但最低位的那个 1（bit 2）在 x 里是 1、在 x-1 里是 0，所以与完变 0。结论就是：x & (x - 1)会把 x 的最低位的 1 清除。而一个数如果是 2 的幂，二进制里只会有一个 1，清掉就变 0。所以x > 0 && (x & (x - 1)) == 0就精确判定了“是 2 的幂且不是 0”。0 必须单独排除，因为 0 和 -1 做与结果也是 0，但 0 显然不是 2 的幂。
3.2 lowbit 与清除最低位 1：x & -x、x & (x - 1)的补码原理
x & -x是个反复出现的式子。很多读者第一次看树状数组，看到i += i & -i就不理解了：负数和正数与，怎么就把最低位 1 提出来了？关键在于补码。在二进制补码表示里，负数是“取反加一”：-x = ~x + 1。随便举例，x = 0b1011000。取反后是 0b0100111，加 1 变成 0b0101000。原数 0b1011000 和取反加一后的 0b0101000 做与，高位全被清掉，只有最低位那个 1 的位置两边都是 1，于是结果就是 0b0001000。
这就是 lowbit，中文常翻译成“最低位 1 的权值”。它的用途极其广泛：树状数组的索引推进、枚举一个整数里所有为 1 的位、N 皇后里逐列尝试可用位置。x & (x - 1)和x & -x正好是一个“清除最低位 1”，一个“提取最低位 1”，配合起来做位计数非常漂亮：
int count_one_soft(int n) { int cnt = 0; while (n) { n &= n - 1; cnt++; } return cnt; }这个循环的次数只等于 1 的个数，而不是固定 32 次。对稀疏位来说，比逐位扫描快得多。
3.3 无临时变量交换与防溢出平均：异或的恒等式与应用
异或有三个性质值得写下来：x ^ 0 = x、x ^ x = 0、异或满足交换律和结合律。从这三条能推出著名的无临时变量交换：
a ^= b; // a = a ^ b b ^= a; // b = (a ^ b) ^ b = a a ^= b; // a = (a ^ b) ^ a = b推演过程很漂亮，但我得泼盆冷水：实际工程里我不推荐用这个。第一，现代编译器对普通三行交换的优化已经很彻底；第二，如果a和b指向同一个变量，这个技巧会把那个变量清零，这是非常隐蔽的 bug。我唯一见到它值得出现的场景，是在某些寄存器极少的嵌入式代码里不想引入额外变量。面试时展现思路可以，生产代码里知道原理就够了。
防溢出平均是另一个实用式子：(a & b) + ((a ^ b) >> 1)。拆开看，a & b取出两个数都为 1 的位，这些位直接贡献给平均值；a ^ b取出两个数不同的位，这些位在两个数里一个是 1 一个是 0，平均值就是它们除以 2，也就是右移一位。两部分相加就是平均值。防溢出体现在哪里？a + b可能溢出，但(a & b) + ((a ^ b) >> 1)每一步都在安全范围内。二分查找里mid = low + ((high - low) >> 1)更常用，但当你手上只有两个操作数，且两个数都可能很大时，这个位运算版本就有意义了。
3.4 取绝对值与同号判断：算术右移的妙用与边界陷阱
先看同号判断，(a ^ b) >= 0。异或的符号位是 0，说明两个数符号位一致，也就是同号；是 1 说明异号。一个表达式搞定，不需要做两次比较或者乘除判断正负。
再看“无分支绝对值”：(x ^ (x >> 31)) - (x >> 31)。核心是利用x >> 31这个算术右移：如果 x 非负，最高位是 0，右移 31 位得到 0；如果 x 为负，最高位是 1，算术右移 31 位得到全 1，也就是 -1。然后：x 非负时x ^ 0 - 0还是 x；x 为负时，x ^ -1等于~x（全位取反），减(-1)相当于加 1，也就是~x + 1，恰好是 x 的绝对值。这个式子避免了分支，也就避免了分支预测失败的可能，在数据分布完全随机的场景下确实有微弱优势。
但我必须提醒一个边界：当 x 是 32 位 int 的最小值-2147483648时，绝对值在 int 范围内并不存在，这个式子算出来还是-2147483648，相当于没变。所以在绝大多数业务代码里，我建议直接写x < 0 ? -x : x，可读性好，也没有未定义行为。位运算版本留给真正对分支敏感的热点循环。
3.5 对 2 的幂取模与内置位计数：减少除法，数出 1
任意 2 的幂m = 2^n，取模运算x % m和x & (m - 1)在 x 非负时完全等价。因为m - 1的二进制恰好是低 n 位全 1，x & (m - 1)就是把 x 高于第 n 位的部分全部清零，留下的就是余数。这个式子在环形缓冲区里几乎是标配：只要把缓冲区大小设成 2 的幂，idx = (idx + 1) & (size - 1)就能让下标自动回绕，还避开了除法指令。
不过有一个细节：遇到常量除法时，现代编译器会自动把除以 2 的幂优化成移位和掩码，所以“为了性能”手写x & (m-1)未必有收益。它真正的价值是让代码体现出“容量必须是 2 的幂”这一约束，我把这个式子看作一种接口约定，而不只是性能优化。
说到数 1，__builtin_popcount(x)是编译器内置函数，在支持 POPCNT 指令的 CPU 上是一条硬件指令，常数时间数完 1 的个数。用的场景包括：汉明距离、位图占用率统计、乘法散列质量的检验。手写版while (n) n &= n - 1循环次数等于 1 的个数，两者各有适用场景——内置函数明确要求硬件支持，软件版可移植性更强。
3.6 枚举子集的三行循环：(sub - 1) & s的逆序魔法
这是状态压缩里最漂亮的一个套路。给定一个集合用整数 s 表示，想枚举 s 的所有非空子集，标准写法：
for (int sub = s; sub; sub = (sub - 1) & s) { // 处理子集 sub }为什么(sub - 1) & s能跳到下一个子集？我们拿 s = 0b1011 走一遍：子集序列依次是 1011、1010、1001、1000、0011、0010、0001，最后是 0。每一步sub - 1会把 sub 最低位的 1 变成 0，同时把它右边的所有位都变成 1；紧接着& s把这些“多余的 1”里不属于 s 的部分全部清掉。结果就是“在 s 的限制下，比当前子集恰好小一号的那个子集”。
这个循环的复杂度是O(2^|s|)，比枚举全部位组合再判断包含关系要省掉大量无效遍历。它出现在：背包组合枚举、集合划分 DP 初始化、N 皇后中“已占用对角线有哪些 column”的传递，以及所有需要“从当前状态去掉某个元素”的场景。我建议你把s = 0b1011这个例子亲手在纸上排一遍，比看十遍文章都有用。
3.7 大小写字母的第五位翻转：从一个 ASCII 冷知识说起
你可能在某段代码里见过c ^= 32，然后一头雾水：32 从哪里来的？答案藏在 ASCII 编码表里。大写'A'的 ASCII 码是 65，即 0b1000001；小写'a'的 ASCII 码是 97，即 0b1100001——两种编码恰好只差 bit 5（那一位的值就是 32）。同理，'B'和'b'也只差 bit 5。所以：
c ^= 32：大小写互相转换，无论当前是大写还是小写，都切到另一个。c |= 32：强制转小写（把 bit 5 置 1）。c &= ~32：强制转大写（把 bit 5 清 0）。
char ch = 'A'; ch ^= 32; // 'a' ch ^= 32; // 'A' 又回来了这类技巧是 ASCII 设计者留下的编码红利，我在解析协议头、处理十六进制字符串、兼容大小写输入时用过不少次。但一定要记住：它只对 ASCII 的 26 个字母成立，UTF-8 编码的中文等其他字符不适用，更不能拿去做业务层的大小写归一化。真要说实用性，c |= 32在实现tolower语义时比一次分支判断更省事，前提是你已经确认输入是字母。
4. 从技巧到工程：位图、权限掩码与 N 皇后剪枝
4.1 位图：用一块连续内存管住海量布尔状态
假设一个业务场景：需要记录一千万个 ID 是否出现过，ID 范围在 0 到 一千万。用bool seen[N]数组，一个字节一个 ID，需要 10MB；用位图，一个 bit 一个 ID，只需要 1000 万 / 8 = 1.25MB。在缓存敏感的流量入口，这差距就是热数据能不能装进 L2 cache 的区别。
位图实现非常直接，核心是刚才讲的整除和取模换成移位和掩码：
#include <cstdint> #include <vector> class BitMap { public: explicit BitMap(int max_id) : bits_((max_id >> 6) + 1, 0) {} void set(int id) { bits_[id >> 6] |= 1ULL << (id & 63); } bool test(int id) const { return (bits_[id >> 6] >> (id & 63)) & 1ULL; } private: std::vector<uint64_t> bits_; };这里id >> 6等于id / 64，id & 63等于id % 64。为什么是 64？因为uint64_t有 64 个位。这套写法的好处不只是省内存，更重要的是：判断“某 ID 是否见过”只用两次数组访问和两次位运算，没有分支预测压力。我在做日志去重、爬虫 URL 去重、数据库查询缓存标记时都这么干过。更进阶一点，多个位图做与运算就能直接得到“同时出现过哪些 ID”的集合，这比遍历一个数组去查快得多。
4.2 权限掩码：把“增删改查”打包进一个整数
权限系统是位运算在业务代码里最自然的应用。用三个位表达三种权限：
enum Perm { READ = 1 << 0, // 1 WRITE = 1 << 1, // 2 EXEC = 1 << 2 // 4 };一个用户的权限可以自由组合，比如int perm = READ | WRITE;表示可读可写。理由也很简单：每个权限占用独立的一位，多个权限的集合就变成了“这些位同时为 1”的整数。
int grant(int perm, int add) { return perm | add; } // 授予权限 int revoke(int perm, int remove) { return perm & ~remove; } // 撤销权限 bool has_all(int perm, int need) { return (perm & need) == need; } // 是否拥有全部 bool has_any(int perm, int need) { return (perm & need) != 0; } // 是否拥有任一has_all为什么是(perm & need) == need？因为perm & need把 perm 里与 need 无关的位全部清掉，留下的就是 perm 和 need 的交集；如果这个交集还等于 need，说明 need 中要求的每一位，perm 里都有。这套逻辑我做过一个内部运营后台的权限中心，几个函数覆盖了所有角色判断，比一张权限关系表轻量太多。需要注意的只有一点：位掩码一定要起名字，perm &= ~2这种直接写数字的代码几天后再看就是灾难。
4.3 N 皇后：三条对角线也能塞进三个整数
N 皇后问题的经典位运算写法，是我见过“位运算把 O(n) 判断变成 O(1)”的最漂亮案例。传统解法每次尝试放皇后，要检查同一列、两条对角线是否已有皇后，通常要开三个二维布尔数组或者循环检查；位运算解法里，状态全部压缩进三个整数：列占用 col、主对角线占用 d1、副对角线占用 d2。
#include <cstdint> int total = 0; int limit; void dfs(int col, int d1, int d2) { if (col == limit) { total++; return; } // 当前行所有可放的位置：列、两条对角线都没被占用的位 int avail = limit & ~(col | d1 | d2); while (avail) { int pos = avail & -avail; // 取最低位的可用位置 avail -= pos; // 下一行时，主对角线整体左移一位，副对角线整体右移一位 dfs(col | pos, (d1 | pos) << 1, (d2 | pos) >> 1); } }为什么对角线要移位？你在第 row 行某列放了皇后，下一行这个皇后的主对角线会投影到“右边一列”，也就是在主对角线的位集合里向左平移一格；副对角线则投影到“左边一列”，向右平移一格。用<< 1和>> 1代替了“每次检查 8 个方向”的循环。pos = avail & -avail取最低位 1，配合avail -= pos逐个枚举可用位置。这套写法在 n = 16 时仍然能在毫秒级跑完，而普通二维标记法可能已经卡到秒级。我给某算法课程当助教时，很多同学第一次看到这个写法都是“还能这样”的反应——但原理并不复杂，就是 lowbit 和位掩码的叠加。
4.4 状态压缩 DP：用位掩码当数组下标
如果一个问题的状态是“某个集合已经选了什么”，这个集合就能直接用整数表示，这就是状态压缩 DP。最经典的是最短 Hamilton 路径：有 n 个城市，求从 0 出发走完所有城市再回到 0 的最短路径。全排列枚举是 n!，n=20 时完全不可行；用dp[mask][i]表示“已经访问过集合 mask，当前停在城市 i”的最小代价，状态数是n * 2^n，n=20 时只有约两千万，完全可接受。
const int INF = 0x3f3f3f3f; int dp[1 << 20][20]; for (int mask = 1; mask < (1 << n); mask++) { for (int i = 0; i < n; i++) { if (!(mask & (1 << i))) continue; // i 必须已经在集合里 if (dp[mask][i] == INF) continue; for (int j = 0; j < n; j++) { if (mask & (1 << j)) continue; // j 不能再访问 int next = mask | (1 << j); dp[next][j] = std::min(dp[next][j], dp[mask][i] + w[i][j]); } } }这里所有的“判断城市 j 是否已访问”和“把城市 j 加入集合”都变成了一次位运算。用位掩码当数组下标，让“集合”这个概念有了确定的整数表示，内存连续、访问随机、缓存友好。这也是为什么位运算在算法、在游戏 AI 的移动规划、在调度系统里至今无法被替代——不是因为它“算得快”，而是因为它把一个抽象集合压缩成了一个基础类型，让程序的表达和机器存储直接对齐。
5. 五个常见坑，以及“位运算真的更快吗”的性能真相
5.1 优先级陷阱：(x & mask) == 0必须带括号
这是我能想到的位运算最常见、也最隐蔽的坑。C/C++ 里==的优先级高于&，所以if (x & mask == 0)实际解析成if (x & (mask == 0))：先比较mask == 0，得到 0 或 1，再拿 x 和这个 0 或 1 做与。想判断“某两个集合没有交集”，结果要么恒为 0，要么只判断了最后一个位，和预期完全不同。
这个 bug 好用的地方在于它不会编译报错，行为却完全错误。解决思路只有一个：所有位运算参与比较时，一律给位运算加括号，写(x & mask) == 0。我还会开编译器的-Wparentheses警告，现代 Clang 和 GCC 都能截住这类问题。顺便说一个反直觉的坑：Python 的运算符优先级和 C 相反，x & mask == 0在 Python 里解析成(x & mask) == 0，因为它把&排得比比较运算符高。从 C 移植代码到 Python，这种细节能让人 debug 到怀疑人生。
5.2 负数右移与符号扩展：无符号类型是位操作默认选择
x >> 31这个式子能用于取绝对值，前提是 x 为负数时右移补进的是 1，也就是算术右移。但 C/C++ 标准里，“负数右移”的行为其实是实现定义的——虽然几乎在所有主流平台上你拿到的都是算术右移，可一旦你写了一个依赖“负数右移补 1”的表达式，可移植性就已经打了折扣。
更常见的坑是符号扩展。看这段代码：
char c = 0xE0; // 如果 char 是 signed，c 其实是负数 int v = c >> 4; // 结果是 0xFFFFFFFE，而不是 0x0E原因很简单：signed char 的 0xE0 最高位是 1，在 32 位 int 上会先做符号扩展变成 0xFFFFFFE0，再右移 4 位得到 0xFFFFFFFE。做协议解析、颜色分量提取、位图处理时踩过这个坑的人不在少数。我的建议是：凡是做位操作的数据，一律用无符号类型，uint8_t、uint32_t、uint64_t是位操作的标准公民。无符号右移永远是逻辑右移，行为确定、不会符号扩展，几乎没有理由用 signed 类型做位运算。
5.3 移位量越界：1 << 32不是 0，是未定义行为
在 C/C++ 里，移位量大于等于类型的位宽是未定义行为。1 << 32在 32 位 int 上会发生什么？不同编译器给出的结果可能完全不同，有的按shift count & 31来，得到 1；有的在调试版本直接给你一个意外结果。这种 bug 通常在循环里出现：你想处理一个 32 位的位图，for (int i = 0; i <= 32; i++) bits |= 1 << i;，i 到 32 的时候行为就不确定了。
解决方式：
bits |= 1ULL << i; // 用 64 位，i 最大到 63 // 或者先判断 if (i >= 32) { /* 单独处理最高位 */ }Java 的处理方式是移位量会先对位宽取模，1L << 32在 Java 里其实是1L << (32 & 63)，和 C 又不一样。Python 则没有这个问题，它的整数无限长，1 << 100直接就是一个大整数。三个语言三种行为，所以看到“同一个位运算表达式跨语言”时要格外警惕，不能拿 C 的思维写 Python，也不能拿 Python 的思维写 C。
5.4 语言差异：Python 的无界整数与 JavaScript 的 32 位陷阱
Python 的位运算有它的特殊性。第一，Python 整数无上限，1 << n不会溢出，但 n 很大时会生成一个巨大的整数，位运算反而变慢；第二，~0在 Python 里是-1而不是“全 1”，因为 Python 用无限长度的二进制补码表示负数；第三，Python 的&、|、^优先级比 C 高，和比较运算符的关系也和 C 相反。这些差异叠加在一起，最危险的是从 C 移植一行位运算代码，不改括号直接抄。
JavaScript 的坑则是另一个方向：位运算在 JS 里先把操作数强制转成 32 位有符号整数。所以0xFFFFFFFF | 0结果是-1，2147483648 | 0得到-2147483648。如果你在 Node.js 里做哈希、做 IP 地址转换，不小心数字就变成了负数。解决办法是理解这个限制，需要无符号语义时用>>> 0把结果转回无符号 32 位整数。这套机制确实烦，但了解之后写起来就能避坑。
5.5 “位运算更快”的真相：编译器优化与工程权衡
很多人有一个朴素认知：位运算比算术运算快，所以我把所有能换成位运算的都换掉。这个认知一半对一半偏。对的一半是，x * 8和x << 3在编译器开优化之后生成的机器码几乎一样，你手写移位并不会多快；偏的一半是，位运算真正的性能价值往往不在“单条指令更少”，而在两个更深的层面。
第一是消除分支。x < 0 ? -x : x在有分支预测失败的场景可能付出 20 个周期的代价，而无分支版本是几条算术指令顺序执行。数据分布越随机，分支预测失败率越高，无分支位运算的相对优势越大。第二是状态压缩。把一个多维状态压成一个整数后，内存占用变小、访问模式变连续，cache 命中率大幅提升——这才是状态压缩 DP 和位图真正快的原因，不是那一次与或非。
所以我的工程建议是：先写可读版本，用 profile 找热点，确认热点确实慢，再考虑用位运算替换。同时给位运算加注释，解释“这个掩码代表什么、为什么这么写”。我曾经接手过一段全是x ^= y的代码，没人能解释每一行在干什么，最后只能重写。位运算应该成为你工具箱里的利器，而不是把它当炫耀的资本。写完之后，用printf("%08x", x)或者 Python 的bin(x)打出来，肉眼检查二进制结果，是我最常用的调试手段。
最后再分享几个我自己养成的习惯
位运算写多了之后，我慢慢形成了几条很笨但很有效的习惯。第一，能用无符号类型绝不用有符号类型，位运算世界里“符号扩展”坑人的次数远比你想象的多。第二，所有位掩码都要起名字，哪怕只是临时用的常量，也写成const int FLAG_A = 1 << 3;而不是x |= 8;，这能让半年后的自己和同事少掉一大半头发。第三，调试位运算时永远打印二进制格式，不要盯着十进制硬想，用printf("%08x")或者 Python 的bin()一眼就能看出来每一位置对了没有。
我个人还有一个很小的技巧：把普通的算术版本和位运算版本并排写在一个测试函数里，随机生成几万组输入做对拍，两边结果一致才认为位运算版本写对了。因为位运算表达式太容易“看着对，边界炸”，对拍能覆盖掉大多数肉眼看不出来的边界情况。这套流程我用了很多年，踩过的坑基本都坑底躺平了。位运算这东西，一旦建立了开关直觉，再往后的每一个技巧都只是这套直觉的排列组合。希望这 30 个例子能让你在下次看到0x5F3759DF或者(sub - 1) & s时，不再觉得那是一堆魔法数字，而是一排排可以拨动的开关。
