已发布·持续改进
Algorithm
位运算把整数看作二进制位，用 AND、OR、XOR 和移位来处理集合、标志位和状态压缩 DP，既快速又简洁。
位运算把整数看作由 0 和 1 组成的序列，用 AND、OR、XOR、NOT 和移位来读取、置位、清除或翻转指定的二进制位。计算机以二进制存储整数，并用补码表示负数，因此这些运算通常只需一条 CPU 指令。像 x & -x（取最低位的 1）或 x & (x - 1)（清除这一位）这样的短表达式，常常可以代替一整个循环。
位运算之所以重要，是因为一个整数就能表示约 20 个元素的集合，从而可以枚举所有子集，并把集合当作状态进行状态压缩 DP。算法竞赛和技术面试中经常出现子集枚举、异或性质和 popcount 问题；在实际系统中，文件权限、功能开关、子网计算、哈希表和位图索引也都依赖位运算。不过各语言的规则不同：Python 的整数没有位数上限，JavaScript 会先转换为 32 位并提供 >>>，Java 同样有 >>>，而 C++ 中掩码最好使用无符号类型。
建议先手动把数字转换成二进制和补码。接着熟悉单个位的四种操作（置位、清除、翻转、检查），并让掩码从 0 遍历到 2^n - 1，打印出所有子集。然后进入子掩码枚举以及任务分配、旅行商问题等状态压缩 DP，最后确认自己所用语言的整数位宽和移位规则。
负数的补码是把所有位取反再加 1。左移相当于乘以 2，右移相当于除以 2，不同语言会区分算术右移和逻辑右移。
借助掩码 1 << i，用 OR 置位、AND NOT 清除、XOR 翻转第 i 位。x & -x 取出最低位的 1，x & (x - 1) 则把它清除。
n 个元素的子集与 0 到 2^n - 1 的整数一一对应，并集、交集和差集都只需一次位运算。
可以反复执行 x &= x - 1 或调用内置函数来统计 1 的个数。利用 a ^ a = 0，异或能找出落单的数，并求汉明距离和格雷码。
popcount 用 x &= x - 1 逐个清除最低位的 1，从而统计 1 的个数。subsets 让掩码从 0 遍历到 2^n - 1，选出第 i 位为 1 的元素，生成所有子集。最后一行展示 12 & -12 为最低位的 1 即 4，12 & 11 为清除该位后的 8，x ^ x 为 0。用 python bit_manipulation.py 运行。
bit_manipulation.py
def popcount(x: int) -> int:
count = 0
while x:
x &= x - 1 # clear the lowest set bit
count += 1
return count
def subsets(items):
n = len(items)
for mask in range(1 << n):
yield mask, [items[i] for i in range(n) if (mask >> i) & 1]
for mask, chosen in subsets(["a", "b", "c"]):
print(format(mask, "03b"), popcount(mask), chosen)
x = 12
print(x & -x, x & (x - 1), x ^ x) # 4 8 0
python bit_manipulation.py共六章，带你从安装一步步了解 位运算 的核心概念。
在这里提问、分享经验，交流关于 位运算 的看法。
还没有讨论。来发起第一个吧。
0 条评论
登录 · 登录后即可发表评论。
来发表第一条评论吧。