从LeetCode入门位运算：常见技巧与实战题目全解析

位运算详解

1. 基础位运算

2. 确定二进制第x位是0还是1

公式：(n >> x) & 1

原理拆解：

1） n >> x：把n的二进制右移x位，让原来的第x位“移到最右边（第0位）”

2） & 1：和1（二进制000...0001）做按位与，只保留最右边的位，其他位全变0

3） 结果：0表示原第x位是0，1表示原第x位是1

画图举例：

以n=0b0110101001（十进制425），求第3位（从0开始数，最右边是第0位）的值 n: 0 1 1 0 1 0 1 0 0 1 （第9位到第0位） 位数: 9 8 7 6 5 4 3 2 1 0 n >> 3: 0 0 0 0 1 1 0 1 0 1 （右移3位，第3位移到了第0位） & 1: 0 0 0 0 0 0 0 0 0 1 → 结果为1，说明原第3位是1

3. 将二进制第x位修改成1

公式：n | (1 << x)

原理拆解：

1） 1 << x：把1左移x位，得到一个只有第x位是1、其他位全是0的数（比如x=3时，得到000...1000）

2） n | (1 << x)：按位或运算，只有第x位会被强制变成1，其他位保持不变（因为0|原数=原数，1|原数=1）

画图举例：

以n=0b0110101011（十进制427），把第4位改成1 n: 0 1 1 0 1 0 1 0 1 1 1 << 4: 0 0 0 0 1 0 0 0 0 0 （只有第4位是1） n | (1<<4): 0 1 1 0 1 0 1 0 1 1 → 第4位本来就是1，结果不变 如果n的第4位是0，比如n=0b0110001011： n: 0 1 1 0 0 0 1 0 1 1 1 << 4: 0 0 0 0 1 0 0 0 0 0 n | (1<<4): 0 1 1 0 1 0 1 0 1 1 → 第4位成功变成1

4. 将二进制第x位修改成0

公式：n & (~(1 << x))

原理拆解：

1） 1 << x：得到只有第x位是1的数

2） ~(1 << x)：对它取反，得到只有第x位是0、其他位全是1的数（比如x=3时，得到111...0111）

3） n & 这个数：按位与运算，只有第x位会被强制变成0，其他位保持不变（因为1&原数=原数，0&原数=0）

画图举例：

以n=0b0110101111（十进制431），把第3位改成0 n: 0 1 1 0 1 0 1 1 1 1 1 << 3: 0 0 0 0 0 0 1 0 0 0 ~(1 << 3): 1 1 1 1 1 1 0 1 1 1 （只有第3位是0） n & ~(1<<3):0 1 1 0 1 0 0 1 1 1 → 第3位成功变成0

5. 位图的思想

位图（BitMap）是用一个数的二进制位来表示状态的技巧，核心是“用1位存1个状态”，非常省空间。

画图举例：

比如我们要记录数字0~6是否出现过：

用普通数组：需要int[7]，每个int占4字节，共28字节

用位图：1个int（4字节=32位）就够了，每一位对应一个数字，1表示出现过，0表示没出现

位数: 6 5 4 3 2 1 0 二进制: 0 1 0 1 0 0 1 → 表示数字0、2、5出现过

6. 提取二进制最右侧的1（lowbit）

公式：n & -n

原理拆解（关键是补码）：

1. 负数在计算机里用补码表示：-n = ~n + 1

2. 对n取反后，最右侧的1会变成0，它右边的所有0都会变成1；再加1后，这些1会全部进位，把最右侧的0变成1，左边的位则保持取反后的状态

3. n & -n时，只有最右侧的1的位置会同时为1，其他位都会变成0，最终结果就是最右侧的1对应的值

画图举例：

以n=0b0110101000（十进制424）为例： n: 0 1 1 0 1 0 1 0 0 0 （最右侧的1在第3位，值为8） ~n: 1 0 0 1 0 1 0 1 1 1 （取反，最右侧的1变0，右边的0变1） ~n + 1(-n): 1 0 0 1 0 1 1 0 0 0 （加1，进位后，最右侧的1变回1，左边保持取反） n & -n: 0 0 0 0 0 0 1 0 0 0 → 结果为8，就是最右侧的1的值

7. 干掉二进制最右侧的1

公式：n & (n-1)

原理拆解：

1. n-1会把n最右侧的1变成0，它右边的所有0都变成1

2. n & (n-1)时，最右侧的1和它右边的位都会被清0，左边的位保持不变，相当于“删掉了最右侧的1”

画图举例：

以n=0b0110101100（十进制428）为例： n: 0 1 1 0 1 0 1 1 0 0 （最右侧的1在第2位，值为4） n-1: 0 1 1 0 1 0 1 0 1 1 （最右侧的1变0，右边的0变1） n & (n-1): 0 1 1 0 1 0 1 0 0 0 → 最右侧的1被清掉了，结果为424

这个技巧常用来统计二进制里1的个数（比如LeetCode 191题），循环执行n = n & (n-1)，直到n为0，循环次数就是1的个数。

8. 位运算的优先级

能加括号就加括号，因为位运算符的优先级比加减乘除、甚至比比较运算符都低，很容易踩坑：比如n & (1 << x)不能写成n & 1 << x，因为<<优先级比&高，会先算1 << x，但如果写成n & 1 + x，就会先算1 + x，结果完全错了；记不住优先级就全加括号，是最稳妥的方式。

9. 异或(^)的运算律与应用

核心运算律：

1） a ^ 0 = a：任何数和0异或，结果还是它本身（0不影响）

2） a ^ a = 0：任何数和自己异或，结果为0（消消乐，相同的数会抵消）

3） a ^ b ^ c = a ^ (b ^ c)：异或满足结合律和交换律，顺序不影响结果

画图举例（消消乐）：

比如0 ^ 1 ^ 0 ^ 1 ^ 0 ^ 1 ^ 1 ^ 0：

过程：0^1=1 → 1^0=1 → 1^1=0 → 0^0=0 → 0^1=1 → 1^1=0 → 0^0=0 结果为0，因为相同的数两两抵消了

经典应用：

LeetCode 136题：只出现一次的数字，数组里其他数都出现两次，用ans ^= nums[i]遍历，最后剩下的就是只出现一次的数（成对的数异或为0，0^唯一数=唯一数）

LeetCode 260题：只出现一次的两个数字，利用异或的性质分组求解

补充：3个经典题目

1. 191 位1的个数：用n & (n-1)循环清掉最右侧的1，统计循环次数

2. 238 比特位计数：利用dp[i] = dp[i & (i-1)] + 1，动态规划统计每个数的1的个数

3. 461 汉明距离：两个数异或，统计结果里1的个数（不同的位就是1）

题目1：判定字符是否唯⼀（LeetCode ⾯试题 01.01）

1. 题目描述

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

• 示例：

示例 1：输入: s = "leetcode" → 输出: false

示例 2：输入: s = "abc" → 输出: true

• 限制： 0 <= len(s) <= 100， s[i] 仅包含小写字母， 加分项：不使用额外的数据结构实现

2. 解法一：哈希表

class Solution { public: bool isUnique(string astr) { int len = astr.size(); if (len > 26) return false; int hash[26] = {0}; for (int i = 0; i < len; i++) { if (hash[astr[i] - 'a'] == 1) return false; hash[astr[i] - 'a']++; } return true; } };

1） 时间复杂度分析

核心操作：先执行一次长度判断 len > 26，是 O(1) 操作。然后遍历字符串的每个字符，循环次数等于字符串长度 n，每次循环里的操作（字符转索引、数组访问、判断和自增）都是 O(1) 的。

结论：时间复杂度为O(n)，其中 n 是字符串的长度。由于题目限制 n ≤ 100，实际运行中可以看作常数级时间。

2） 空间复杂度分析

核心操作：定义了一个长度为 26 的数组 hash[26]，大小是固定的，和输入字符串长度无关。额外只用到了几个变量（len、i），空间开销可以忽略。

结论：空间复杂度为 O(1)，因为使用的额外空间是常数级，不随输入规模变化。

3. 解法二：位图（BitMap）思想

位图的核心是用一个整数的二进制位来表示状态，实现“一个位存一个状态”，空间效率极高。

1） 原理说明

题目限定字符为小写字母，共 26 个，而 C++ 中 int 类型占 32 位，足够容纳所有字母的状态。

第 i 位为 0：表示字母 'a' + i 未出现过 第 i 位为 1：表示字母 'a' + i 已出现过

这样，仅用 1 个 int 变量就能充当“哈希表”，无需额外数组。

2） 核心位运算技巧（本题用到的 3 个关键操作）

class Solution { public: bool isUnique(string astr) { // 1. 鸽巢原理优化：超过26个字符必然重复 if(astr.size() > 26) return false; // 2. 用一个int变量作为位图，初始全为0（所有字符都未出现） int bitMap = 0; // 3. 遍历字符串中的每个字符 for(auto ch : astr) { // 3.1 计算当前字符在字母表中的索引（0~25） int i = ch - 'a'; // 3.2 检查该字符对应的位是否为1（即是否已出现过） if(((bitMap >> i) & 1) == 1) { // 已出现过，直接返回false return false; } // 3.3 把当前字符对应的位设为1，标记为已出现 bitMap |= 1 << i; } // 4. 遍历完所有字符都没重复，返回true return true; } };

4. 知识点拓展

1） 鸽巢原理：因为小写字母只有 26 个，所以字符串长度超过 26 时，必然存在重复字符，直接返回 false，这是一个重要的剪枝优化。

2） 位运算的常见应用场景：

状态压缩（如本题的位图） 快速判断奇偶性（n & 1）

交换两个数（a ^= b; b ^= a; a ^= b;） 统计二进制中 1 的个数（n & (n-1)）

题目2：丢失的数字（LeetCode 268）

1. 题目描述

给定一个包含 [0, n] 中 n 个数的数组 nums，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1: 输入: nums = [3,0,1] 输出: 2
解释: n=3，因为有3个数字，所以所有的数字都在范围 [0,3] 内。2是丢失的数字，因为它没有出现在 nums 中。

示例 2: 输入: nums = [0,1] 输出: 2
解释: n=2，因为有2个数字，所以所有的数字都在范围 [0,2] 内。2是丢失的数字，因为它没有出现在 nums 中。

示例 3: 输入: nums = [9,6,4,2,3,5,7,0,1] 输出: 8
解释: n=9，因为有9个数字，所以所有的数字都在范围 [0,9] 内。8是丢失的数字，因为它没有出现在 nums 中。

示例 4: 输入: nums = [0] 输出: 1
解释: n=1，因为有1个数字，所以所有的数字都在范围 [0,1] 内。1是丢失的数字，因为它没有出现在 nums 中。

提示: n == nums.length，1 <= n <= 10^4，0 <= nums[i] <= n，nums 中的所有数字都 独一无二

进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

2. 解法（哈希表/高斯求和）

方法1：高斯求和（数学公式法）

思路：0~n 的总和：sum = n * (n + 1) / 2 ，减去数组元素和，差值即为缺失数字。

class Solution { public: int missingNumber(vector<int>& nums) { int n = nums.size(); long long total = (long long)n * (n + 1) / 2; long long sum = 0; for (int x : nums) sum += x; return total - sum; } };

时间复杂度：O(n)，空间复杂度：O(1)

方法2：哈希表 / 哈希集合

思路：把所有数存入哈希集合，再从 0 到 n 遍历，找不在集合里的数。

class Solution { public: int missingNumber(vector<int>& nums) { unordered_set<int> st(nums.begin(), nums.end()); int n = nums.size(); for (int i = 0; i <= n; ++i) { if (!st.count(i)) return i; } return -1; } };

时间复杂度：O(n)，空间复杂度：O(n)（开辟了哈希集合）

3. 解法（位运算）

算法思路：设数组的大小为 n，那么缺失之前的数就是 [0, n]，数组中是在 [0, n] 中缺失一个数形成的序列。如果我们把数组中的所有数，以及 [0, n] 中的所有数全部「异或」在一起，那么根据「异或」运算的「消消乐」规律，最终的异或结果应该就是缺失的数~

异或运算的性质：

一个数和自身异或，结果为 0：x ^ x = 0

一个数和 0 异或，结果为它本身：x ^ 0 = x

异或运算满足交换律和结合律：a ^ b ^ c = a ^ c ^ b

把数组里的所有数，和 [0, n] 范围内的所有数，全部异或在一起。 出现过的数都会和自己抵消，变成 0。最终剩下的结果，就是只出现了一次的那个“丢失的数字”。

class Solution { public: int missingNumber(vector<int>& nums) { int ret = 0; // 异或数组中所有数 for(auto x : nums) ret ^= x; // 异或 [0, n] 范围内的所有数 for(int i = 0; i <= nums.size(); i++) ret ^= i; return ret; } };

时间复杂度：O(n)，遍历数组一次 O(n)，再遍历 0~n 一次 O(n)，总线性。

空间复杂度：O(1)，只使用常数额外变量。

题目3：两整数之和（LeetCode 371）

1. 题目描述

给你两个整数 a 和 b，不使用运算符 + 和 -，计算并返回两整数之和。

示例 1: 输入: a = 1, b = 2 输出: 3

示例 2: 输入: a = 2, b = 3 输出: 5

提示: -1000 <= a, b <= 1000

2. 解法（位运算）

算法思路：异或 ^ 运算本质是「无进位加法」；按位与 & 操作能够得到「进位」；然后一直循环进行，直到「进位」变成 0 为止。

加法可以拆分为两步：

1） 无进位相加：用异或 ^ 实现，异或的结果就是两个数不考虑进位时的和。

2） 计算进位：用按位与 & 实现，两个数都为 1 的位会产生进位，(a & b) << 1 就是进位值。

3） 循环将“无进位和”与“进位”相加，直到进位为 0 为止。

计算 13 + 28，先转二进制（高位补0，对齐位权）：13 = 01101，28 = 11100

a = 13: 0 1 1 0 1 b = 28: 1 1 1 0 0 ------------------------------------------------- ① 异或（无进位和）： 1 0 0 0 1 → 十进制 17 ② 按位与&： 0 1 1 0 0 左移 <<1： 1 1 0 0 0 → 十进制 24（进位） ------------------------------------------------- 新状态：a=17，b=24 a = 17: 1 0 0 0 1 b = 24: 1 1 0 0 0 ------------------------------------------------- ① 异或（无进位和）： 0 1 0 0 1 → 十进制 9 ② 按位与&： 1 0 0 0 0 左移<<1： 1 0 0 0 0 0 → 十进制 32（进位） ------------------------------------------------- 新状态：a=9，b=32 a = 9: 0 0 1 0 0 1 b = 32: 1 0 0 0 0 0 -------------------------------------------------- ① 异或（无进位和）： 1 0 1 0 0 1 → 十进制 41 ② 按位与&： 0 0 0 0 0 0 左移<<1： 0 0 0 0 0 0 → 无进位 -------------------------------------------------- 最终状态：a=41，b=0

C++代码：

class Solution { public: int getSum(int a, int b) { while(b != 0) { // 先算出无进位相加的结果 int x = a ^ b; // 算出进位，用 unsigned 防止负数左移溢出 unsigned int carry = (unsigned int)(a & b) << 1; a = x; b = carry; } return a; } };

时间复杂度：O(1)，整数固定 32 位，循环最多 32 次，与输入大小无关。

空间复杂度：O(1)

题目4：只出现一次的数字 II（LeetCode 137）

1. 题目描述

给你一个整数数组 nums，除某个元素仅出现一次外，其余每个元素都恰出现三次。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且不使用额外空间来解决此问题。

示例 1: 输入: nums = [2,2,3,2] 输出: 3

示例 2: 输入: nums = [0,1,0,1,0,1,99] 输出: 99

提示: 1 <= nums.length <= 3 * 10^4 ，-2^31 <= nums[i] <= 2^31 - 1
nums 中，除某个元素仅出现一次外，其余每个元素都恰出现三次

2. 解法（比特位计数）

算法思路：设要找的数位 ret。由于整个数组中，需要找的元素只出现了「一次」，其余的数都出现的「三次」，因此我们可以根据所有数的「某一个比特位」的总和 %3 的结果，快速定位到 ret 的「一个比特位上」的值是 0 还是 1。这样，我们通过 ret 的每一个比特位上的值，就可以将 ret 给还原出来。

1） 统计数组中所有数字，每一个二进制位上 1 出现的次数。

2） 因为其他数字都出现了 3 次，所以每一位上 1 的个数，要么是 3 的倍数，要么是 3k+1（如果目标数的该位是 1）。

3） 对每一位的计数取模 3，如果结果为 1，说明目标数的这一位是 1；否则是 0。

4） 按位还原出目标数即可。

举个具体例子

假设数组是：[2, 2, 3, 2]，出现3次的数：2（二进制：10），只出现1次的目标数：3（二进制：11）

步骤1：统计每一个二进制位上1出现的次数

我们把数组里所有数转成二进制，按位统计：

步骤2：分析计数的规律

因为其他数字都出现了3次，所以：

如果目标数的某一位是0：那这一位的1的总个数 = 3 ×（出现3次的数在这一位的1的个数），也就是3的倍数

如果目标数的某一位是1：那这一位的1的总个数 = 3 ×（出现3次的数在这一位的1的个数） + 1，也就是3k+1

对应我们的例子：

第1位：计数1 = 3×0 + 1 → 目标数这一位是1 第2位：计数4 = 3×1 + 1 → 目标数这一位是1

步骤3：对每一位计数取模3，还原目标数

对每一位的计数做%3运算：

第1位：1 % 3 = 1 → 目标数这一位是1 第2位：4 % 3 = 1 → 目标数这一位是1

拼起来就是二进制11，对应十进制3，正好是我们要找的只出现1次的数

一个更复杂的例子

数组：[5, 5, 5, 7]，5的二进制：101，7的二进制：111

统计每一位1的次数：

取模3：

第1位：4%3=1 → 1 第2位：1%3=1 → 1 第3位：4%3=1 → 1 拼起来：111 → 7，正确

总结：统计每一位1的次数：把数组所有数按二进制位拆分，逐位计数；利用3次的规律：出现3次的数，每一位的1的贡献都是3的倍数，不会影响取模3的结果；取模3还原目标数：结果为1 → 目标数这一位是1，结果为0 → 目标数这一位是0

C++ 算法代码：

class Solution { public: int singleNumber(vector<int>& nums) { int ret = 0; // 依次处理 32 位 int 的每一位 for(int i = 0; i < 32; i++) { int sum = 0; // 统计 nums 中所有数的第 i 位的和 for(int x : nums) { if(((x >> i) & 1) == 1) sum++; } // 模 3 后如果是 1，说明目标数的第 i 位是 1 sum %= 3; if(sum == 1) ret |= 1 << i; } return ret; } };

时间复杂度：O(n)，外层 32 位固定，内层遍历 n 个数，32n 仍是线性。

空间复杂度：O(1)

题目5：消失的两个数字（LeetCode 面试题 17.19）

1. 题目描述

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？以任意顺序返回这两个数字均可。

示例 1: 输入: [1] 输出: [2,3]

示例 2: 输入: [2,3] 输出: [1,4]

提示: nums.length <= 30000

2. 解法（位运算）

算法思路：本题就是 268.丢失的数字 + 260.只出现一次的数字 III 组合起来的题。先将数组中的数和 [1, n + 2] 区间内的所有数「异或」在一起，问题就变成了：有两个数出现了「一次」，其余所有的数出现了「两次」。进而变成了 260.只出现一次的数字 III 这道题。

1） 把数组里的所有数，和 [1, n+2] 范围内的所有数全部异或。最终的结果 tmp 就是两个缺失数字 a 和 b 的异或结果（tmp = a ^ b）。

2） 找到 tmp 中第一个为 1 的二进制位（说明 a 和 b 在这一位上的值不同，一个是 0，一个是 1）。

3） 根据这一位的不同，把所有数分成两组，分别异或。两组的异或结果，就分别是 a 和 b。

例子

假设数组是：[1, 2, 3, 5]，原本的完整序列应该是 [1, 2, 3, 4, 5, 6]（也就是 n=4，n+2=6）

缺失的两个数字：a=4，b=6

步骤1：所有数异或，得到 a ^ b

我们把数组里的数和**[1, n+2] 范围内的数**全部异或：数组：[1, 2, 3, 5] 范围：[1, 2, 3, 4, 5, 6]

异或运算规则：x ^ x = 0，x ^ 0 = x，相同为0，不同为1

计算过程：(1^1) ^ (2^2) ^ (3^3) ^ (5^5) ^ 4 ^ 6 = 0 ^ 0 ^ 0 ^ 0 ^ 4 ^ 6 = 4 ^ 6

把4和6转成二进制：4 = 100 ，6 = 110

100 ^ 110 ------ 010

所以 tmp = 4 ^ 6 = 2（二进制 010）

步骤2：找到tmp中第一个为1的二进制位

tmp = 010，从右往左（低位到高位）数：

第1位（最右）：0 第2位：1 ✅ 第3位：0

所以我们选第2位作为分组依据（a和b在这一位不同：4的第2位是0，6的第2位是1）

步骤3：按这一位分组，分别异或，得到a和b

分组规则：组1：第2位为0的数 组2：第2位为1的数

我们把所有参与异或的数（数组+范围）按这个规则分组：

组1异或（第2位为0）

1 ^ 5 ^ 1 ^ 4 ^ 5 = (1^1) ^ (5^5) ^ 4 = 0 ^ 0 ^ 4 = 4

✅ 得到第一个缺失数：4

组2异或（第2位为1）

2 ^ 3 ^ 2 ^ 3 ^ 6 = (2^2) ^ (3^3) ^ 6 = 0 ^ 0 ^ 6 = 6

✅ 得到第二个缺失数：6

再举一个例子巩固

数组：[2, 3, 5, 7]，完整范围[1,2,3,4,5,6,7,8]（n=4，n+2=8），缺失：a=1，b=8

步骤1：异或所有数

(2^2)^(3^3)^(5^5)^(7^7) ^1^4^6^8 = 1^4^6^8 = 1(0001) ^ 4(0100) ^ 6(0110) ^ 8(1000) = (0001 ^ 0100)=0101, (0110^1000)=1110, 0101^1110=1011 (11) tmp = 1^8 = 9(1001)（这里简化后，实际最终tmp=1^8=9）

步骤2：找第一个1位：第1位（最右）
步骤3：分组异或，最终得到1和8

总结：1） 所有数异或后，出现2次的数会相互抵消（x^x=0），只剩下两个缺失数的异或结果tmp=a^b；2） tmp中为1的位，说明a和b在这一位不同，以此分组可以把a和b分到不同组；3） 每组内的数异或，出现2次的数抵消，最终剩下的就是两个缺失数

C++ 算法代码：

class Solution { public: vector<int> missingTwo(vector<int>& nums) { // 1. 将所有的数异或在一起，得到 a ^ b int tmp = 0; for(auto x : nums) tmp ^= x; for(int i = 1; i <= nums.size() + 2; i++) tmp ^= i; // 2. 找出 a, b 中比特位不同的那一位 int diff = 0; while(1) { if(((tmp >> diff) & 1) == 1) break; else diff++; } // 3. 根据 diff 位的不同，将所有的数划分为两类来异或 int a = 0, b = 0; for(int x : nums) { if(((x >> diff) & 1) == 1) b ^= x; else a ^= x; } for(int i = 1; i <= nums.size() + 2; i++) { if(((i >> diff) & 1) == 1) b ^= i; else a ^= i; } return {a, b}; } };

时间复杂度：O(n)，三次线性遍历，总复杂度仍为 O(n)。

空间复杂度：O(1)

以上就是几道典型位运算题的完整思路与实现。理解核心性质后，这类题目往往能写出简洁高效的代码。位运算看似抽象，实则规律清晰。掌握这些经典思路，就能轻松解决一类高频算法题。