一文吃透位运算：从入门到高阶技巧

位运算、位操作、二进制、快速幂、图压缩、状态压缩、低级编程、算法优化

在现代计算体系中，甭管你是前端、后端还是算法工程师，位运算 都像一把隐藏在大腿里的瑞士军刀——平时不显山漏水，关键时刻能一刀封喉。本文将带你用不到两千字的时间，从 二进制语义 一路拆到 实用技巧与坑位提示，并穿插高频面试题与性能对比，力求一文通关。

为什么位运算如此强势？

所有数据在内存底层都以 0/1 形式存在，位运算正是直接对这些 二进制位 进行操作的技术统称。与循环里反复做乘除相比，位运算只需 一条 CPU 指令 就能完成深度的数值转换，时间复杂度直接拉到 O(1)，在 状态压缩、快速幂、图遍历优化 等场景尤为致命。

👉 仅用 3 行代码将算法提速 10 倍？点我继续深挖位运算黑科技！

二进制编码速成课

补码（Two’s Complement）

正数：首位 0 开头，剩下 31 位表示数值。
例：43₁₀ = 00000000 00000000 00000000 00101011₂
负数：负数 -x 使用 ~x + 1 计算得到。
例：-43₁₀ = 11111111 11111111 11111111 11010101₂

无符号数

32 位无符号整型（uint32_t）范围：0 到 2³²-1（约 42 亿）。
与有符号数转换关系：-x 的有符号值 ≡ 2³² - x 的无符号值。

五个最常用位运算符号

运算符	数学含义	使用场景示例
`&`	按位与	保留指定位掩码（mask）
`	`	按位或	把某些位强制置 1
`^`	按位异或	交换变量、加密简单混淆
`~`	按位取反	快速得到补码掩码
`<<` / `>>`	左移 / 右移	快速乘除 2 的幂

一条口诀记位运算：

同 1 则 1（&），有 1 则 1（|），异性相吸（^）。

高频技巧实战

技巧一：判奇偶

bool isOdd(int n) { return n & 1; }

最低位为 1 → 奇数；为 0 → 偶数，执行速度和常量无异，极简极快。

技巧二：交换两变量

a ^= b; b ^= a; a ^= b;

⚠ 仅 两变量指向不同地址 时使用，否则会把同一内存直接清零。

技巧三：二进制去尾

x >> 1  // x/2
x << 1  // x*2

技巧四：取出/翻转/清空第 k 位

int getBit(int n, int k) { return (n >> k) & 1; }
int setBit(int n, int k) { return n | (1 << k); }
int clearBit(int n, int k) { return n & ~(1 << k); }
int flipBit(int n, int k) { return n ^ (1 << k); }

👉 一行代码帮你搞定「二进制状态压缩」并多次 AC 经典题！

状态压缩 DP 入门范例

状态压缩即把集合用 31 位或 63 位整数 表示，位 1 代表选中，一键枚举子集。

经典题：旅行商问题（TSP）

显式状态：dp[mask][u] 表当前已访问节点集合 mask，位于节点 u 时的最短路径。核心枚举代码：

for (int mask = 0; mask < (1 << n); ++mask)
    for (int u = 0; u < n; ++u)
        if (mask >> u & 1)  // 判断 u 是否已访问
            for (int v = 0; v < n; ++v)
                if (!(mask >> v & 1))
                    dp[mask | (1 << v)][v] = min(...);

时间复杂度 O(n²·2ⁿ)，碾压朴素的 O(n!)。

面试场景的必刷题精要

只出现一次的数字（LeetCode 136）
全员异或一次，剩余的即答案。
数字范围按位与（LeetCode 201）
找到公共前缀：while (left < right) right &= (right - 1);
位 1 的个数（LeetCode 191/剑指 15）
Brian Kernighan 算法：count = 0; while (n) {++count; n &= n-1;}
能被无符号整数表示的最大 2 的幂
1 << (31 - __builtin_clz(n))（GCC 内建语句），__builtin_clz 计算前导零个数。

FAQ：关于位运算的五个高频疑问

Q1：为什么用 n & (n-1) 能消除最低位 1？
A：任何正整数 n，其二进制最低位 1 及右侧 0 在 n-1 全部翻转，与运算后最低位 1 直接清零。

Q2：左移是否一定等价于乘以 2？
A：仅无符号整数/正整数成立，有符号数可能溢出产生负数或 UB（undefined behavior），务必确认范围。

Q3：异或的交换律和结合律有什么用？
A：大量 加密、哈希、校验 场景（如 Blake 系列）利用其逆运算即自身的特性，避免额外逆函数。

Q4：状态压缩会不会内存爆炸？
A：最多 64 位整数即可打包 64 维布尔状态，100 万状态的 long long 数组约占用 8 MB，可接受。

Q5：有没有可视化工具帮助理解？
A：VSCode bitwise-calculator 插件 + OnlineGDB 调试端，实时查看 32 位长串，一文一图加速学习。

小结与延展阅读

位运算的魅力在于 极致效能与极简语义 的统一。理解二进制后，你能立刻将 复杂度从线性能拉到常数级，并在 状态压缩 DP、图形位掩码、数据流校验 等场景大杀四方。下一步可以尝试：

阅读《Hacker’s Delight》深入位技巧库
研究 __builtin_popcount、BitSet 在 Go 与 Rust 的实现差异
亲手写 Bloom Filter、SIMD 位运算优化 体验工业级用法

愿你下次遇到粗看复杂的题目时，脑海里立刻浮现一个 64 位的二进制掩码，轻轻一点，AC 到手。