位运算详解：从二进制到 LeetCode 常用技巧

位运算是算法题里非常高频的一类基础能力。
它看起来“底层”，但一旦掌握，你会发现很多题都能变得非常简洁。

这篇笔记按下面的顺序展开：

1. 先建立对二进制的直觉
2. 再理解每一种位运算符的含义
3. 然后总结刷题中最常见的套路
4. 最后给出 LeetCode 场景下常见模板和易错点

默认使用 C# 讲解。

一、为什么要学位运算

位运算的核心价值主要有三个：

• 表达状态很紧凑：一个整数就能表示很多布尔状态
• 某些操作非常高效：例如判断奇偶、乘除 2、提取最低位 1
• 有固定套路：很多看似难的题，实际上是经典位技巧

常见应用场景：

• 判断奇偶
• 交换两个数
• 统计二进制中 1 的个数
• 找只出现一次的数字
• 子集枚举
• 状态压缩 DP
• 掩码判断
• 权限标记
• Trie / 前缀异或 / XOR 题型

二、先建立二进制直觉

我们平时用十进制，例如：

13

它的二进制是：

1101

含义是：

1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0
= 8 + 4 + 0 + 1
= 13

也就是说，一个整数在计算机里，本质上就是一串 0 和 1。

例如：

理解位运算，本质上就是理解：

这些 0 和 1 在对应位置上如何变化。

三、五种常见位运算

C# 中常见位运算符：

• & 按位与
• | 按位或
• ^ 按位异或
• ~ 按位取反
• << 左移
• >> 右移

下面一个一个讲。

四、按位与 &

规则：

1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0

只有两个位置都为 1，结果才是 1。

例子：

  1101   (13)
& 1011   (11)
= 1001   (9)

作用 1：判断某一位是否为 1

例如判断第 k 位是不是 1：

bool isOne = ((n >> k) & 1) == 1;

或者写成：

bool isOne = (n & (1 << k)) != 0;

作用 2：做“掩码过滤”

例如：

int mask = 1 << 3; // 第 3 位
bool hasBit = (n & mask) != 0;

这在状态压缩里特别常见。

作用 3：把某些位清零

n = n & mask;

如果 mask 对应位是 0，那么 n 对应位就会被清掉。

五、按位或 |

规则：

1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0

只要有一个位置是 1，结果就是 1。

例子：

  1101
| 1011
= 1111

作用 1：把某一位置为 1

n = n | (1 << k);

也可以简写成：

n |= (1 << k);

这表示把第 k 位强行设成 1。

作用 2：合并状态

两个集合都用 bitmask 表示时，可以用 | 合并。

例如：

int a = 0b0101;
int b = 0b1010;
int c = a | b; // 1111

六、按位异或 ^

这是位运算里最重要的一个。

规则：

1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0

两个位置不同为 1，相同为 0。

例子：

  1101
^ 1011
= 0110

异或的四个核心性质

这是刷题必须记住的部分。

1. a ^ 0 = a

一个数和 0 异或，还是它自己。

2. a ^ a = 0

一个数和自己异或，变成 0。

3. 异或满足交换律和结合律

a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

所以一堆数异或时，顺序不重要。

4. 可以用于“消掉成对出现的数”

这就是很多题的核心。

七、异或最常见的题型

1. 只出现一次的数字

题意：除了一个数只出现一次，其他数都出现两次，找这个数。

例如：

[2, 2, 1]

做法：

public int SingleNumber(int[] nums)
{
    int ans = 0;
    foreach (int x in nums)
    {
        ans ^= x;
    }
    return ans;
}

为什么可以？

因为：

2 ^ 2 = 0
0 ^ 1 = 1

所有成对数字都会被抵消掉。

2. 交换两个数（了解即可）

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

现在面试里一般不推荐这样写，因为可读性差，而且普通交换更清楚。

3. 找两个只出现一次的数

如果数组中有两个数只出现一次，其余都出现两次：

1. 先把所有数异或，得到 x ^ y
2. 找到 x 和 y 二进制上某一位不同的位置
3. 按这一位把原数组分组
4. 两组各自异或，就能得到两个答案

这是经典题型，关键点是：

异或结果中为 1 的某一位，说明这两个数在这一位不同。

八、按位取反 ~

规则：0 变 1，1 变 0。

例如（假设只看 4 位）：

~0101 = 1010

但在实际编程里要注意：

整数通常不是“只看 4 位”，而是固定长度，比如 32 位。

所以 ~ 的结果经常和你肉眼想的不一样。

例如 C# 中：

int x = 5;
int y = ~x;

y 会变成一个负数。

这是因为计算机中有符号整数通常使用 补码 表示。

一个常见结论

~x == -x - 1

例如：

~5 == -6

这个结论在做位技巧题时很有用，但前提是你知道它来自补码表示。

九、左移 <<

n << k

表示把二进制整体向左移动 k 位，右边补 0。

例如：

0011 << 2 = 1100

也就是：

3 << 2 = 12

直觉理解

左移一位，相当于乘以 2。

所以：

n << k = n * 2^k

前提是 不考虑溢出。

常见用法

1. 构造掩码

int mask = 1 << k;

表示第 k 位为 1，其余位为 0。

2. 快速乘 2

x << 1

不过在业务代码里通常直接写 x * 2 更清楚。

十、右移 >>

n >> k

表示把二进制整体向右移动 k 位。

例如：

1100 >> 2 = 0011

直觉理解

右移一位，通常相当于除以 2。

n >> k ≈ n / 2^k

但这里要特别注意：

对负数右移时，不同语言、不同规则可能会有细节差异。

在 C# 中，int 的右移是算术右移，符号位会保留。

所以你刷题时，若涉及负数，最好更谨慎，不要机械地把右移当作普通除法。

常见用法

1. 取第 k 位

int bit = (n >> k) & 1;

2. 遍历一个数的所有二进制位

while (n > 0)
{
    int bit = n & 1;
    n >>= 1;
}

十一、最常见的位运算技巧总结

这一节是刷题最值得背下来的部分。

技巧 1：判断奇偶

一个数的最低位：

• 1 表示奇数
• 0 表示偶数

所以：

bool isOdd = (n & 1) == 1;
bool isEven = (n & 1) == 0;

为什么？

因为二进制最低位表示 2^0，也就是 1 的位置。

技巧 2：取第 k 位

int bit = (n >> k) & 1;

含义：

1. 先把第 k 位移到最低位
2. 再和 1 做与运算
3. 得到结果 0 或 1

技巧 3：把第 k 位置为 1

n |= (1 << k);

技巧 4：把第 k 位清零

n &= ~(1 << k);

先构造：

1 << k

再取反：

~(1 << k)

这样除了第 k 位是 0，其他位都是 1。
再与一下，就能把第 k 位清零。

技巧 5：翻转第 k 位

n ^= (1 << k);

因为异或 1 会翻转，异或 0 不变。

技巧 6：判断一个数是不是 2 的幂

这是非常经典的一题。

结论

如果 n > 0 且：

(n & (n - 1)) == 0

那么 n 是 2 的幂。

为什么？

2 的幂在二进制里只有一个 1。

例如：

1   = 0001
2   = 0010
4   = 0100
8   = 1000

而 n - 1 会把那个 1 右边全部变成 1。

例如：

8     = 1000
8 - 1 = 0111

所以：

1000 & 0111 = 0000

代码：

public bool IsPowerOfTwo(int n)
{
    return n > 0 && (n & (n - 1)) == 0;
}

技巧 7：去掉最低位的 1

n = n & (n - 1);

这个操作会把 最低位的那个 1 去掉。

例如：

n      = 110100
n - 1  = 110011
&      = 110000

这个技巧非常重要。

典型用途：统计 1 的个数

public int HammingWeight(uint n)
{
    int count = 0;
    while (n != 0)
    {
        n &= (n - 1);
        count++;
    }
    return count;
}

每次循环去掉一个 1，所以循环次数等于 1 的个数。

技巧 8：提取最低位的 1

lowbit = n & (-n);

例如：

n =  110100
-n = 001100   // 这里只是帮助理解，实际是补码运算
结果 = 000100

它提取出的就是最右边那个 1。

这个技巧在下面这些地方特别常见：

• 树状数组（Fenwick Tree）
• 位分组
• 某些异或题
• lowbit 枚举

技巧 9：判断某个集合状态里是否包含元素 k

如果我们用一个整数 mask 表示集合：

• 第 k 位是 1，表示包含元素 k
• 第 k 位是 0，表示不包含元素 k

那么：

bool contains = (mask & (1 << k)) != 0;

技巧 10：枚举一个集合的所有子集

这是状态压缩题中的高频技巧。

给定一个集合状态 mask，枚举它的所有子集：

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

如果还想包含空集，可以最后再单独处理 0。

这个写法建议直接背。

十二、为什么 n & (n - 1) 能去掉最低位的 1

这块很多人会背结论，但不理解原因。
其实只要看一个例子就很清楚。

假设：

n = 1011000

最低位的 1 在第 4 位（从右往左数）。

那么：

n - 1 = 1010111

你会发现规律：

• 最低位那个 1 变成了 0
• 它右边原来的 0 全都变成了 1
• 它左边保持不变

所以再做一次 &：

  1011000
& 1010111
= 1010000

最低位那个 1 就被消掉了。

这个结论建议理解，不要死记。

十三、补码到底是什么，为什么负数这么表示

这是位运算里最容易让人晕的部分，但刷题其实只需要掌握够用版本。

1. 正数的补码就是它本身

例如 5：

00000101

2. 负数的补码：先取反，再加 1

例如 -5：

先写 5：

00000101

取反：

11111010

加 1：

11111011

这就是 -5 的补码表示。

3. 为什么要用补码

因为这样可以把加法和减法统一到同一套硬件逻辑上。

对刷题来说，更重要的是理解下面两个结论：

结论 1

-x = ~x + 1

结论 2

~x = -x - 1

结论 3

n & (-n)

可以提取最低位的 1。

十四、位运算在 LeetCode 中的几类经典题型

题型 1：异或消重

代表题：

• Single Number
• Missing Number（某些解法）
• 两个只出现一次的数字

识别特征：

• “其他都出现两次 / 成对”
• “只有一个或两个例外”
• “要求线性时间、常数空间”

第一反应通常应该是：异或。

题型 2：统计二进制 1 的个数

代表题：

• Number of 1 Bits
• Counting Bits

识别特征：

• 让你数 bit
• 让你利用前一个状态推出后一个状态

常见方法：

• 循环右移
• n & (n - 1)
• DP：bits[i] = bits[i >> 1] + (i & 1)

例如：

public int[] CountBits(int n)
{
    int[] ans = new int[n + 1];
    for (int i = 1; i <= n; i++)
    {
        ans[i] = ans[i >> 1] + (i & 1);
    }
    return ans;
}

题型 3：判断 2 的幂 / 4 的幂

代表题：

• Power of Two
• Power of Four

2 的幂常用：

n > 0 && (n & (n - 1)) == 0

4 的幂要进一步判断那个唯一的 1 是否落在正确位置。

题型 4：状态压缩

代表题：

• 子集类题目
• N 皇后某些优化写法
• DP + mask
• 访问状态记录

识别特征：

• 元素数量不大，常见是 n <= 15、n <= 20
• 每个元素只有“选/不选”、“访问/未访问”两种状态
• 想用一个整数表示整组状态

核心思想：

用一个整数的每一位表示一个元素的状态。

题型 5：子集枚举

如果题目需要枚举所有选择方案：

for (int mask = 0; mask < (1 << n); mask++)
{
    for (int i = 0; i < n; i++)
    {
        if (((mask >> i) & 1) == 1)
        {
            // 选择了 nums[i]
        }
    }
}

这就是最标准的位掩码枚举子集写法。

十五、刷题时最容易犯的错误

1. 把“第 k 位”写错

很多题里，第 k 位到底是从左往右数，还是从右往左数，要看题意。
在代码中我们通常默认：

从右往左，从 0 开始计数

也就是最低位是第 0 位。

2. 忘了优先级，加错括号

例如：

n & 1 << k

虽然有时结果对，但可读性很差。
建议始终写成：

n & (1 << k)

再比如：

(n >> k) & 1

括号别省。

3. 忽略负数问题

尤其是：

• >> 对负数的行为
• ~x 得到负数
• int.MinValue 取相反数溢出风险

如果题目只讨论非负数，问题会简单很多。
如果题目涉及 32 位有符号整数，一定要谨慎。

4. 1 << 31 的坑

在 C# 里：

1 << 31

结果可能涉及符号位。
如果你想处理无符号场景，可能需要考虑使用 uint 或更小心地判断。

5. 把位运算当魔法，不理解含义

位运算最怕“背公式不懂为什么”。

建议你至少真正理解这几个：

• n & 1
• (n >> k) & 1
• n & (n - 1)
• n & (-n)
• mask | (1 << k)
• mask & ~(1 << k)

只要这些真的懂了，大多数位题都能顺下去。

十六、最实用的 C# 位运算模板

1. 判断奇偶

bool isOdd = (n & 1) == 1;

2. 取第 k 位

int bit = (n >> k) & 1;

3. 设置第 k 位为 1

n |= (1 << k);

4. 清除第 k 位

n &= ~(1 << k);

5. 翻转第 k 位

n ^= (1 << k);

6. 判断是否是 2 的幂

bool isPowerOfTwo = n > 0 && (n & (n - 1)) == 0;

7. 统计 1 的个数

int count = 0;
while (n != 0)
{
    n &= (n - 1);
    count++;
}

8. 提取最低位的 1

int lowbit = n & -n;

9. 枚举所有子集

for (int mask = 0; mask < (1 << n); mask++)
{
    // mask 表示一种选择方案
}

10. 枚举某个集合的所有非空子集

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

十七、一道题该怎么判断能不能用位运算

你刷题时可以这样判断：

信号 1：元素状态只有两种

例如：

• 选 / 不选
• 在 / 不在
• 用过 / 没用过

这时很可能能用 bitmask。

信号 2：题目反复提“二进制位”“1 的个数”“异或”

这是直接提示你用位运算。

信号 3：数组里“其他都成对出现”

这类题第一反应通常是异或。

信号 4：数据范围很小，但需要枚举组合

例如 n <= 15，常常可以用状态压缩。

十八、学习位运算的正确顺序

如果你现在还不熟，建议按这个顺序掌握：

第一步：先会最基本的 6 个操作

• &
• |
• ^
• ~
• <<
• >>

第二步：牢牢记住 5 个核心技巧

• n & 1
• (n >> k) & 1
• n & (n - 1)
• n & (-n)
• n ^ n = 0

第三步：刷经典题

推荐顺序：

1. Single Number
2. Number of 1 Bits
3. Counting Bits
4. Power of Two
5. Missing Number
6. Subsets
7. 两个只出现一次的数字
8. 状态压缩 DP 入门题

十九、一个简短的总复习

你可以把位运算理解成：

直接操作整数的二进制表示。

最重要的不是把所有符号都背下来，而是先抓住几个核心用途：

• &：检查、过滤、清零
• |：置 1、合并状态
• ^：翻转、消重、找不同
• <<：构造掩码、乘 2
• >>：取某一位、除 2
• n & (n - 1)：去掉最低位 1
• n & (-n)：提取最低位 1

如果你把这些吃透，位运算题的主体就已经掌握了。

二十、推荐你重点记住的 8 句话

1. n & 1 可以判断奇偶
2. (n >> k) & 1 可以取第 k 位
3. n | (1 << k) 可以把第 k 位置 1
4. n & ~(1 << k) 可以把第 k 位清零
5. n ^ (1 << k) 可以翻转第 k 位
6. n & (n - 1) 可以去掉最低位的 1
7. n & (-n) 可以提取最低位的 1
8. n > 0 && (n & (n - 1)) == 0 可以判断 2 的幂

二十一、附：几个适合直接练手的 LeetCode 题

• 136. Single Number
• 191. Number of 1 Bits
• 338. Counting Bits
• 231. Power of Two
• 268. Missing Number
• 78. Subsets
• 260. Single Number III
• 190. Reverse Bits

建议刷的时候不要只背答案，而是问自己：

• 这题为什么想到位运算？
• 用的是哪条性质？
• 这个写法的边界情况是什么？
• 如果换成负数会不会有坑？

二十二、最后的学习建议

位运算刚开始不顺很正常。
因为它不像双指针、哈希表那样直观，它更像是：

先有一点抽象，再突然开窍。

真正开窍的关键，不是看更多公式，而是把下面这几件事搞懂：

1. 一个整数就是一串二进制位
2. 每个运算符到底是怎么逐位作用的
3. 为什么 n & (n - 1) 和 n & (-n) 这么有用
4. 为什么异或能“抵消”

一旦这几个点通了，后面很多题会越来越顺。

二十三、面试复习版速查表

// 判断奇偶
(n & 1) == 1

// 取第 k 位
(n >> k) & 1

// 第 k 位置 1
n |= (1 << k);

// 第 k 位清零
n &= ~(1 << k);

// 第 k 位翻转
n ^= (1 << k);

// 去掉最低位 1
n &= (n - 1);

// 提取最低位 1
int lowbit = n & -n;

// 判断 2 的幂
n > 0 && (n & (n - 1)) == 0

二十四、练习建议

复习这篇笔记时，建议你自己动手做这三件事：

1. 把几个数字手写成二进制，比如 5、6、8、13
2. 自己手算一遍 &、|、^
3. 手推一次 n & (n - 1) 和 n & (-n) 的变化过程

只看不算，很容易觉得“好像懂了”；
一旦自己推过，记忆会牢很多。

希望这篇笔记能帮你把位运算真正吃透。