位运算速查：二进制原理与高频解题模板

发布于 2026-07-28 09:58 · 最后编辑于 2026-07-31 15:53 · 字数 3,346 👁 133 次阅读

位运算速查手册：补码原理图解 → 核心技巧模板（附二进制逐步演示）→ 按套路分类的刷题例题（LeetCode + Codeforces）→ 状压 DP、格雷码、XOR 线性基进阶内容。

章节	说明
运算符速查	所有位运算符语义与示例
补码原理	`n & (-n)` 等技巧的底层基础
位运算与集合运算	状压 DP 的数学直觉
核心技巧模板	最常用的 6 类技巧，附二进制图解
按套路刷题	5 大套路 + 题目列表
Brian Kernighan 算法	高效统计 1 的个数
状态压缩与子集枚举	竞赛核心模板
格雷码	相邻只差 1 位的编码
XOR 线性基（进阶）	求任意子集 XOR 最大值
常用语言 API	Java / Python / C++
快速参考卡	场景 → 技巧一览

运算符速查

运算符	名称	规则	示例（4位）
`&`	AND（与）	同为 1 才为 1	`1010 & 1100 = 1000`
\|	OR（或）	有一个 1 就为 1	1010 \| 1100 = 1110
`^`	XOR（异或）	不同为 1，相同为 0	`1010 ^ 1100 = 0110`
`~`	NOT（取反）	0 ↔ 1 全部翻转	`~0110 = 1001`
`<<`	左移	低位补 0，相当于 × 2^k	`0011 << 2 = 1100`
`>>`	右移（算术）	高位补符号位	`-4 >> 1 = -2`
`>>>`	右移（逻辑，Java 独有）	高位始终补 0	`-1 >>> 1 = 2147483647`

Python 没有 >>>：Python 整数是无限精度，>> 始终补 0，不存在符号位溢出问题。

补码原理

理解补码是读懂 n & (-n)、~n + 1 = -n 等技巧的前提。

为什么 `-n = ~n + 1`

以 n = 6（8 位二进制）为例逐步演示：

原码  n      =  0000 0110   (+6)
取反 ~n      =  1111 1001   (这是 -7 的补码)
加1  ~n + 1  =  1111 1010   (这就是 -6 的补码)

直觉：n + (~n + 1) = 1 0000 0000（8 位溢出清零）。补码让加减法在同一套电路中实现。

`n & (-n)` 如何提取最低位的 1

以 n = 44（0010 1100）为例：

 n      =  0010 1100    (44)
-n      =  1101 0100    (补码：最低位 1 及右侧不变，左侧全部翻转)
────────────────────
n & -n  =  0000 0100    只剩最低位的 1

关键规律：-n 的最低位 1 右边与 n 完全相同，左边完全相反，AND 后自然只留最低位。

这是树状数组（BIT / Fenwick Tree）中 lowbit(x) = x & (-x) 的原理。

位运算与集合运算

用一个 int（32 位）的每一位表示"第 i 个元素是否在集合中"，1 表示在，0 表示不在。这是状压 DP 的核心直觉。

元素编号：  4  3  2  1  0
集合 A  =   0  1  0  1  1   → 包含 {0, 1, 3}
集合 B  =   1  1  0  0  1   → 包含 {0, 3, 4}

A & B   =   0  1  0  0  1   → 交集    {0, 3}
A | B   =   1  1  0  1  1   → 并集    {0, 1, 3, 4}
A ^ B   =   1  0  0  1  0   → 对称差  {1, 4}（只在其中一个集合里的元素）

集合操作	位运算	说明
交集 A ∩ B	`A & B`	两个集合都有的元素
并集 A ∪ B	A \| B	任一集合有的元素
对称差 A △ B	`A ^ B`	只在其中一个集合里的元素
补集	`~A`	不在 A 中的元素
判断 A 是 B 的子集	`(A & B) == A`	A 的每个元素都在 B 中
集合大小（元素个数）	`Integer.bitCount(mask)`	统计 1 的个数

核心技巧模板

1. 读 / 写 / 翻转第 k 位

int bit = (n >> k) & 1;       // 读取第 k 位（k 从 0 开始，0 是最低位）
n = n | (1 << k);             // 设置第 k 位为 1
n = n & ~(1 << k);            // 清除第 k 位（设为 0）
n = n ^ (1 << k);             // 翻转第 k 位（0→1，1→0）

以 n = 1010（二进制），k = 1 为例：

读取：  1010 >> 1 = 0101，& 0001 = 1         → 第1位是 1
设置：  1010 | 0010 = 1010                   → 无变化（已是 1）
清除：  1010 & 1101 = 1000                   → 第1位变 0
翻转：  1010 ^ 0010 = 1000                   → 第1位 1→0

2. 消去最低位的 1：`n & (n-1)`

原理：n - 1 会把 n 最低位的 1 变成 0，并把其右边所有 0 变成 1。AND 后，最低位的 1 消失，右侧的差异也被 0 覆盖。

n       =  1 0 1 1 0 0    (44)
n - 1   =  1 0 1 0 1 1    (43)   ← 最低位1变0，右侧0全变1
────────────────────────
n&(n-1) =  1 0 1 0 0 0    (40)   ← 最低位的1消失

常见用途：

// 判断 n 是 2 的幂（2的幂只有1个比特1）
boolean isPow2 = n > 0 && (n & (n - 1)) == 0;

// 判断 n 是 4 的幂（先是2的幂，且唯一的1在偶数位）
// 0xAAAAAAAA = 1010...（奇数位全1），4的幂的1不在奇数位
boolean isPow4 = n > 0 && (n & (n - 1)) == 0 && (n & 0xAAAAAAAA) == 0;

4 的幂图解：

4  = 0000 0100  → 1 在第2位（偶数位）
16 = 0001 0000  → 1 在第4位（偶数位）
64 = 0100 0000  → 1 在第6位（偶数位）

0xAAAAAAAA = ...1010 1010   奇数位全为1
4的幂 & 0xAAAAAAAA == 0   ← 说明1不在奇数位 ✓

3. 提取最低位的 1：`n & (-n)`

n       =  0010 1100    (44)
-n      =  1101 0100    (补码)
────────────────────
n & -n  =  0000 0100    (4)  ← 只剩最低位的 1

用途：树状数组 lowbit，枚举集合的子集时精确定位最低有效位。

4. XOR 的三大性质与消消乐

a ^ a = 0      自消：相同的数异或为 0
a ^ 0 = a      幺元：与 0 异或不变
a ^ b = b ^ a  交换律：顺序无关

XOR 消消乐图解（LC 136：找只出现一次的数）：

数组：[2, 1, 4, 1, 2]

全部 XOR：2 ^ 1 ^ 4 ^ 1 ^ 2
        = (2 ^ 2) ^ (1 ^ 1) ^ 4    ← 成对的数两两抵消
        =    0    ^    0    ^ 4
        = 4                         ← 剩下的就是答案

进阶：两个单一数（LC 260）

全部 XOR 得 a^b（设为 0110），说明 a 和 b 至少有1位不同
找最低位的1：0110 & (-0110) = 0010  → 用 bit1 区分 a 和 b

按 bit1 分组，分别 XOR：
  组A（bit1=0）：包含 a → 全部消除后剩 a
  组B（bit1=1）：包含 b → 全部消除后剩 b

5. 不用 +/- 实现加法

二进制加法拆成两步：

无进位的和  = a ^ b          相同位为0，不同位为1
进位        = (a & b) << 1   两位都是1才产生进位，向左移一位

int add(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
}

演示 3 + 5：

a=0011, b=0101
轮1: carry = (0001)<<1 = 0010, a = 0011^0101 = 0110, b = 0010
轮2: carry = (0010)<<1 = 0100, a = 0110^0010 = 0100, b = 0100
轮3: carry = (0100)<<1 = 1000, a = 0100^0100 = 0000, b = 1000
轮4: carry = 0,               a = 0000^1000 = 1000, b = 0
结果 = 1000 = 8  ✓

6. 符号位与绝对值

int sign = n >> 31;                  // 正数/0 → 0（全0），负数 → -1（全1）
int abs  = (n ^ sign) - sign;        // 不调用 Math.abs 求绝对值
boolean isNeg = (n >> 31) == -1;     // 判断是否为负数

按套路刷题

套路一：XOR 消消乐

核心：利用 a ^ a = 0，成对出现的数全部抵消，剩下出现奇数次的数。

题目	平台	核心思路
136. 只出现一次的数字	LC	全部 XOR，重复的消掉，剩唯一
268. 丢失的数字	LC	数组与 `0..n` 全部 XOR，配对消除
260. 只出现一次的数字 III	LC	全部 XOR 得 `a^b`，找一位区分，分两组分别 XOR
1194D. The Number of Pairs	CF	前缀 XOR + 哈希判断子数组 XOR

套路二：位统计

核心：逐位统计 1 的个数，或通过位操作推出 DP 递推式。

题目	平台	核心思路
191. 位1的个数	LC	Brian Kernighan：反复 `n &= n-1`
338. 比特位计数	LC	DP：`dp[n] = dp[n >> 1] + (n & 1)`
461. 汉明距离	LC	`Integer.bitCount(x ^ y)`，XOR 后统计 1
477. 汉明距离总和	LC	对每一位统计 0 和 1 的个数，贡献为 `ones × zeros`

338 题 DP 推导图解：

n 的1的个数 = (n 右移1位) 的1的个数 + 最低位是否为1

n=6 (110): dp[6] = dp[6>>1] + (6&1) = dp[3] + 0 = 2
n=7 (111): dp[7] = dp[7>>1] + (7&1) = dp[3] + 1 = 3
n=8 (1000): dp[8] = dp[4] + 0 = 1

套路三：幂次判断

核心：利用 n & (n-1) 判断是否恰好只有 1 个比特 1。

题目	平台	核心思路
231. 2 的幂	LC	`n > 0 && (n & (n-1)) == 0`
342. 4 的幂	LC	先判 2 的幂，再判 1 在偶数位：`(n & 0xAAAAAAAA) == 0`
1009C. Aka...	CF	用 lowbit 分解质因子

套路四：加减法 / 编码模拟

题目	平台	核心思路
371. 两整数之和	LC	`a^b` 无进位求和，`(a&b)<<1` 求进位，迭代
190. 颠倒二进制位	LC	逐位取出放到结果的对称位
89. 格雷码	LC	`i ^ (i >> 1)` 直接生成第 i 个格雷码

套路五：状态压缩 DP

核心：用整数的每一位表示某元素"是否被选/访问"，将指数级的集合状态压缩成一个整数下标。

题目	平台	核心思路
78. 子集	LC	枚举 `0` 到 `2^n-1`，每个数对应一个子集
847. 访问所有节点的最短路径	LC	`dp[mask][i]`：访问了 mask 中的节点、当前在 i 的最短路
1239. 串联字符串的最大长度	LC	状压枚举字符集，用位运算检查是否有重叠
1986G. Sum over Subsets	CF	SOS DP：枚举子集求和，O(n × 2^n)

模板代码见下一节。

Brian Kernighan 算法

每次 n &= (n-1) 消去最低位的 1，直到 n 为 0。

int countOnes(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);   // 消去最低位的 1
        count++;
    }
    return count;
}

时间复杂度：O(k)，k 为 1 的个数，最优情况远好于逐位检查的 O(32)。

逐步演示 n = 44（0010 1100，有 3 个 1）：

初始：  0010 1100   (44)
第1次：0010 1100 & 0010 1011 = 0010 1000   count=1
第2次：0010 1000 & 0010 0111 = 0010 0000   count=2
第3次：0010 0000 & 0001 1111 = 0000 0000   count=3  → 结束

状态压缩与子集枚举

枚举所有 2^n 个子集

int n = 4;
for (int mask = 0; mask < (1 << n); mask++) {
    // mask 的每一位对应一个元素是否在子集中
    for (int i = 0; i < n; i++) {
        if ((mask >> i & 1) == 1) {
            // 元素 i 在当前子集中
        }
    }
}

枚举 mask 的所有非空子集（竞赛必备）

for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // sub 是 mask 的一个非空子集
}

为什么 sub = (sub-1) & mask 能覆盖所有子集？

mask = 1010

sub 的变化过程：
  1010  (mask 本身)
  1010-1 = 1001, & 1010 = 1000
  1000-1 = 0111, & 1010 = 0010
  0010-1 = 0001, & 1010 = 0000  → 停止

覆盖了所有子集：{3,1}=1010，{3}=1000，{1}=0010  ✓

原理：sub-1 把 sub 最低位的 1 清零并把右侧全置 1，再 & mask 把不属于 mask 的位压回 0，恰好跳到下一个更小的子集。

状压 DP 经典框架（旅行商问题 TSP）

// dp[mask][i]：访问过 mask 中所有节点、当前停在 i 的最短距离
int[][] dp = new int[1 << n][n];
// 初始化、转移...
for (int mask = 1; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
        if ((mask >> i & 1) == 0) continue;   // i 不在 mask 中
        int prev = mask ^ (1 << i);           // 去掉 i 的上一个状态
        for (int j = 0; j < n; j++) {
            if ((prev >> j & 1) == 0) continue;
            dp[mask][i] = Math.min(dp[mask][i], dp[prev][j] + dist[j][i]);
        }
    }
}

格雷码

定义：一种二进制编码，任意相邻两个数只有 1 位不同。

生成公式：第 i 个格雷码 = i ^ (i >> 1)

i    二进制    i ^ (i>>1)   格雷码
─────────────────────────────────
0    000       000 ^ 000  =  000  (0)
1    001       001 ^ 000  =  001  (1)
2    010       010 ^ 001  =  011  (3)
3    011       011 ^ 001  =  010  (2)
4    100       100 ^ 010  =  110  (6)
5    101       101 ^ 010  =  111  (7)

相邻格雷码只有1位不同 ✓（如 011 → 010，只变了最低位）

List<Integer> grayCode(int n) {
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < (1 << n); i++) {
        res.add(i ^ (i >> 1));
    }
    return res;
}

应用：LC 89；旋转编码器（避免多位同时跳变导致的读数错误）。

XOR 线性基（进阶）

问题：给定一组数，从中选任意非空子集，求所有可能 XOR 值中的最大值。

原理：XOR 在 GF(2) 上构成线性空间。线性基是一组"基底"，所有可能的 XOR 值都能由基底线性组合（XOR）得到，基底的每一个元素负责"贡献"一个比特位。

插入过程（贪心高位优先）：
  对每个数 x，从最高位往低位看，
  若该位为1且 basis[i] 为空 → 放入 basis[i]，结束
  若该位为1且 basis[i] 已有数 → x ^= basis[i]，继续处理低位
  若 x 变为 0 → x 已被线性基表示，无需插入

int[] basis = new int[32];

void insert(int x) {
    for (int i = 31; i >= 0; i--) {
        if ((x >> i & 1) == 0) continue;
        if (basis[i] == 0) { basis[i] = x; return; }
        x ^= basis[i];
    }
}

int maxXor() {
    int res = 0;
    for (int i = 31; i >= 0; i--) {
        res = Math.max(res, res ^ basis[i]);
    }
    return res;
}

适用场景：CF 895C、LeetCode 1707（离线 + 线性基）、任意子集 XOR 最大/最小值。

常用语言 API

功能	Java	Python	C++
统计 1 的个数	`Integer.bitCount(n)`	`bin(n).count('1')`	`__builtin_popcount(n)`
最高位 1 的位置	`31 - Integer.numberOfLeadingZeros(n)`	`n.bit_length() - 1`	`31 - __builtin_clz(n)`
最低位 1 的位置	`Integer.numberOfTrailingZeros(n)`	`(n & -n).bit_length() - 1`	`__builtin_ctz(n)`
翻转所有位（32位）	`Integer.reverse(n)`	手动实现	`__builtin_bswap32(n)`
INT 最大值	`Integer.MAX_VALUE`（2^31 - 1）	`float('inf')`	`INT_MAX`

⚠️ Java 中 Integer.MIN_VALUE（-2^31）取负仍是自身，~Integer.MIN_VALUE == Integer.MAX_VALUE，处理绝对值边界时注意。

快速参考卡

遇到这类问题	优先想到的技巧
找数组中唯一出现一次的数	全部 XOR（`a^a=0`）
两个单一数	全部 XOR 后用 `lowbit` 分组，各组再 XOR
判断 n 是 2 的幂	`n > 0 && (n & (n-1)) == 0`
判断 n 是 4 的幂	2的幂 + `(n & 0xAAAAAAAA) == 0`
统计二进制中 1 的个数	Brian Kernighan / `Integer.bitCount`
提取最低位的 1（lowbit）	`n & (-n)`
消去最低位的 1	`n & (n-1)`
读 / 写 / 翻转第 k 位	移位 + 掩码（见核心模板）
集合的交 / 并 / 对称差	`&` / \| / `^`
枚举所有子集	`mask` 从 `0` 到 `2^n - 1`
枚举某集合 mask 的所有子集	`sub = (sub-1) & mask`
加法但不能用 +/-	`^` 求和，`(a&b)<<1` 求进位，迭代
生成格雷码	`i ^ (i >> 1)`
任意子集 XOR 最大值	XOR 线性基
两数 XOR 最大值	前缀 Trie 逐位贪心

← 返回列表

(1 人打了分，平均分： 5.00)

暂无评论，来留下第一条吧。

登录或注册后才能发表评论

位运算速查：二进制原理与高频解题模板

目录

运算符速查

补码原理

为什么 `-n = ~n + 1`

`n & (-n)` 如何提取最低位的 1

位运算与集合运算

核心技巧模板

1. 读 / 写 / 翻转第 k 位

2. 消去最低位的 1：`n & (n-1)`

3. 提取最低位的 1：`n & (-n)`

4. XOR 的三大性质与消消乐

5. 不用 +/- 实现加法

6. 符号位与绝对值

按套路刷题

套路一：XOR 消消乐

套路二：位统计

套路三：幂次判断

套路四：加减法 / 编码模拟

套路五：状态压缩 DP

Brian Kernighan 算法

状态压缩与子集枚举

枚举所有 2^n 个子集

枚举 mask 的所有非空子集（竞赛必备）

状压 DP 经典框架（旅行商问题 TSP）

格雷码

XOR 线性基（进阶）

常用语言 API

快速参考卡

评论 (0)

位运算速查：二进制原理与高频解题模板

目录

运算符速查

补码原理

为什么 -n = ~n + 1

n & (-n) 如何提取最低位的 1

位运算与集合运算

核心技巧模板

1. 读 / 写 / 翻转第 k 位

2. 消去最低位的 1：n & (n-1)

3. 提取最低位的 1：n & (-n)

4. XOR 的三大性质与消消乐

5. 不用 +/- 实现加法

6. 符号位与绝对值

按套路刷题

套路一：XOR 消消乐

套路二：位统计

套路三：幂次判断

套路四：加减法 / 编码模拟

套路五：状态压缩 DP

Brian Kernighan 算法

状态压缩与子集枚举

枚举所有 2^n 个子集

枚举 mask 的所有非空子集（竞赛必备）

状压 DP 经典框架（旅行商问题 TSP）

格雷码

XOR 线性基（进阶）

常用语言 API

快速参考卡

评论 (0)

为什么 `-n = ~n + 1`

`n & (-n)` 如何提取最低位的 1

2. 消去最低位的 1：`n & (n-1)`

3. 提取最低位的 1：`n & (-n)`