位运算技巧

位运算可以测试和修改标志、统计 1 的个数、判断二的幂。表达式虽然短，每一步仍有可解释的位变化。本课保留完整八位字，逐项核对。

当位本身代表权限或功能开关时，这些操作很有用。稀疏标志集合可以每次访问一个 1；popcount(a ^ b) 计算两位串的汉明距离；要求2 的幂容量或对齐时，可先验证该前提。

掩码像开孔模板：AND 检查或保留选定位，OR 将它们置 1，取反掩码配合 AND 将它们清零。x - 1 则利用借位改变末尾模式。

清除最低的 1

目标位为 k 时，构造 mask = 1 << k。只有 k 位为 1。x & mask 测试该位，x | mask 置位，x & ~mask 清零。

OR 置位是幂等的，原先为 1 就不变。清零则保证目标位变 0，无论原来是什么。因此先置位再清零，只有目标位原先为 0 时才恢复原输入。

x & (x - 1) 清除最低置位。对正整数减一时，更高位不变，最低的 1 变 0，其下方的 0 都因借位变 1。再与原 x 做 AND，高位保留，下方新增的 1 被原来的 0 清除，只有最低那个 1 消失。重复到 0，次数就是置位数。

正的2 的幂恰好有一个 1，因此判定为 x > 0 and (x & (x - 1)) == 0。x > 0 是必要条件，0 也满足后面的等式。

逐步演示

默认 x = 40 = 00101000、k = 2，构造 mask = 00000100。

1. 40 & 4 = 0，说明位 2 原先为 0。
2. 置位：00101000 | 00000100 = 00101100，即 44。再用同一掩码测试，结果非零。
3. 可见八位内，反掩码为 11111011。清零得到 00101100 & 11111011 = 00101000。位 2 原先为 0，所以本例回到 40。
4. 从原始 40 重新开始计数。40 - 1 = 39 = 00100111，40 & 39 = 32 = 00100000，最低 1 被清除，计数为 1。
5. 32 - 1 = 31 = 00011111，32 & 31 = 0，计数为 2。两次循环，对应两个 1。
6. 2 的幂判断复用第一次结果：40 & 39 = 32 非零，所以 40 不是2 的幂。32 & 31 = 0 且 32 为正，所以 32 是。
7. 检查 0：0 & -1 = 0 会通过无保护的等式，但 0 > 0 为假，完整判断拒绝 0。

最终 32 被接受，40 因多个 1 被拒绝，0 因不满足正数条件被拒绝。

时间与空间复杂度

固定机器字下，构造掩码、测试、置位、清零、判断2 的幂均为 O(1) 时间和 O(1) 额外空间。

Kernighan 计数循环每个 1 执行一次。1 的个数为 p，时间 O(p)，空间 O(1)。W 位中 p <= W，最坏 O(W)；逐位扫描则即使只有一个 1 也固定检查 W 个位置。

稀疏标志或需要逐个处理置位时，清除最低 1 的循环有用。只需计数时，可采用语言或 CPU 提供的原生 popcount。对 a ^ b 计数就得到汉明距离。

边界情况

• x = 0：计数循环执行零次，2 的幂检查为 false。
• x = 1：一个 1，清除一次到 0，是2 的幂。
• x = 255 = 11111111：八次循环，是本课最密输入。
• k = 0、k = 7：分别选择最低位和最左侧可见位，构造规则相同。
• 目标位已为 1：OR 不改值，但后续清零会移除原有位，不是还原。

常见错误

• 2 的幂判定省略 x > 0。 0 & -1 为 0，会错把 0 当2 的幂。
• 用 XOR 代替清零。 x ^ mask 将 0、1 互换；要求结果必为 0 时，用 x & ~mask。
• 只背 x & (x - 1)。 观察借位如何改变最低 1 及其下方后缀，再看 AND 为什么只清一位。
• 混淆位号和掩码。 k = 2 是位置，1 << k = 4 才是选择它的掩码。

简化范围

输入限制为 0–255 的非负数，显示低八位。Python 整数为任意精度，JavaScript 位运算把操作数转换为有符号 32 位整数。选定范围使两段代码结果一致，不涵盖范围外的符号掩码、溢出和语言移位差异。