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

位运算详解1. 基础位运算运算符名称规则真值表通俗理解按位与000 010 100 111有0就是0按位或011 111 000有1就是1^按位异或0^00 0^11 1^01 1^10相同为0不同为1无进位加法按位取反~01 ~10所有位取反注意补码规则左移n k二进制左移k位右边补0等价于乘2^k右移n k二进制右移k位左边补符号位正数补0负数补1等价于除2^k向下取整2. 确定二进制第x位是0还是1公式(n x) 1原理拆解1 n x把n的二进制右移x位让原来的第x位“移到最右边第0位”2 1和1二进制000...0001做按位与只保留最右边的位其他位全变03 结果0表示原第x位是01表示原第x位是1画图举例以n0b0110101001十进制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位是13. 将二进制第x位修改成1公式n | (1 x)原理拆解1 1 x把1左移x位得到一个只有第x位是1、其他位全是0的数比如x3时得到000...10002 n | (1 x)按位或运算只有第x位会被强制变成1其他位保持不变因为0|原数原数1|原数1画图举例以n0b0110101011十进制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 | (14): 0 1 1 0 1 0 1 0 1 1 → 第4位本来就是1结果不变 如果n的第4位是0比如n0b0110001011 n: 0 1 1 0 0 0 1 0 1 1 1 4: 0 0 0 0 1 0 0 0 0 0 n | (14): 0 1 1 0 1 0 1 0 1 1 → 第4位成功变成14. 将二进制第x位修改成0公式n (~(1 x))原理拆解1 1 x得到只有第x位是1的数2 ~(1 x)对它取反得到只有第x位是0、其他位全是1的数比如x3时得到111...01113 n 这个数按位与运算只有第x位会被强制变成0其他位保持不变因为1原数原数0原数0画图举例以n0b0110101111十进制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 ~(13):0 1 1 0 1 0 0 1 1 1 → 第3位成功变成05. 位图的思想位图BitMap是用一个数的二进制位来表示状态的技巧核心是“用1位存1个状态”非常省空间。画图举例比如我们要记录数字0~6是否出现过用普通数组需要int[7]每个int占4字节共28字节用位图1个int4字节32位就够了每一位对应一个数字1表示出现过0表示没出现位数: 6 5 4 3 2 1 0 二进制: 0 1 0 1 0 0 1 → 表示数字0、2、5出现过6. 提取二进制最右侧的1lowbit公式n -n原理拆解关键是补码1. 负数在计算机里用补码表示-n ~n 12. 对n取反后最右侧的1会变成0它右边的所有0都会变成1再加1后这些1会全部进位把最右侧的0变成1左边的位则保持取反后的状态3. n -n时只有最右侧的1的位置会同时为1其他位都会变成0最终结果就是最右侧的1对应的值画图举例以n0b0110101000十进制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都变成12. n (n-1)时最右侧的1和它右边的位都会被清0左边的位保持不变相当于“删掉了最右侧的1”画图举例以n0b0110101100十进制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^11 → 1^01 → 1^10 → 0^00 → 0^11 → 1^10 → 0^00 结果为0因为相同的数两两抵消了经典应用LeetCode 136题只出现一次的数字数组里其他数都出现两次用ans ^ nums[i]遍历最后剩下的就是只出现一次的数成对的数异或为00^唯一数唯一数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.011. 题目描述实现一个算法确定一个字符串 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 个关键操作操作代码作用通俗理解1. 获取字符对应的位索引i ch - a将 a~z 映射为 0~25把字符转为位图中的“下标”2. 检查该位是否为 1((bitMap i) 1) 1判断字符是否已出现把位图右移 i 位只看最右边的位3. 将该位置为 1bitMap | 1 i把当前字符对应的位设为1标记字符已出现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; } };维度数组哈希法位图法空间复杂度O(1)固定大小数组O(1)仅用 1 个 int额外数据结构用了数组不符合加分项完全不用额外数据结构符合加分项时间复杂度O(n)O(n)可读性直观易懂需要理解位运算4. 知识点拓展1 鸽巢原理因为小写字母只有 26 个所以字符串长度超过 26 时必然存在重复字符直接返回 false这是一个重要的剪枝优化。2 位运算的常见应用场景状态压缩如本题的位图 快速判断奇偶性n 1交换两个数a ^ b; b ^ a; a ^ b; 统计二进制中 1 的个数n (n-1)题目2丢失的数字LeetCode 2681. 题目描述给定一个包含 [0, n] 中 n 个数的数组 nums找出 [0, n] 这个范围内没有出现在数组中的那个数。示例 1: 输入: nums [3,0,1] 输出: 2解释: n3因为有3个数字所以所有的数字都在范围 [0,3] 内。2是丢失的数字因为它没有出现在 nums 中。示例 2: 输入: nums [0,1] 输出: 2解释: n2因为有2个数字所以所有的数字都在范围 [0,2] 内。2是丢失的数字因为它没有出现在 nums 中。示例 3: 输入: nums [9,6,4,2,3,5,7,0,1] 输出: 8解释: n9因为有9个数字所以所有的数字都在范围 [0,9] 内。8是丢失的数字因为它没有出现在 nums 中。示例 4: 输入: nums [0] 输出: 1解释: n1因为有1个数字所以所有的数字都在范围 [0,1] 内。1是丢失的数字因为它没有出现在 nums 中。提示: n nums.length1 n 10^40 nums[i] nnums 中的所有数字都 独一无二进阶你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?2. 解法哈希表/高斯求和方法1高斯求和数学公式法思路0~n 的总和sum n * (n 1) / 2 减去数组元素和差值即为缺失数字。class Solution { public: int missingNumber(vectorint 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(vectorint nums) { unordered_setint 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] 中的所有数全部「异或」在一起那么根据「异或」运算的「消消乐」规律最终的异或结果应该就是缺失的数~异或运算的性质一个数和自身异或结果为 0x ^ x 0一个数和 0 异或结果为它本身x ^ 0 x异或运算满足交换律和结合律a ^ b ^ c a ^ c ^ b把数组里的所有数和 [0, n] 范围内的所有数全部异或在一起。 出现过的数都会和自己抵消变成 0。最终剩下的结果就是只出现了一次的那个“丢失的数字”。class Solution { public: int missingNumber(vectorint 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 3711. 题目描述给你两个整数 a 和 b不使用运算符 和 -计算并返回两整数之和。示例 1: 输入: a 1, b 2 输出: 3示例 2: 输入: a 2, b 3 输出: 5提示: -1000 a, b 10002. 解法位运算算法思路异或 ^ 运算本质是「无进位加法」按位与 操作能够得到「进位」然后一直循环进行直到「进位」变成 0 为止。加法可以拆分为两步1 无进位相加用异或 ^ 实现异或的结果就是两个数不考虑进位时的和。2 计算进位用按位与 实现两个数都为 1 的位会产生进位(a b) 1 就是进位值。3 循环将“无进位和”与“进位”相加直到进位为 0 为止。运算作用二进制规则异或a ^ b无进位相加相同为0不同为1按位与左移(a b) 1计算进位全1才进位左移1位到高位计算 13 28先转二进制高位补0对齐位权13 0110128 11100a 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进位 ------------------------------------------------- 新状态a17b24 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进位 ------------------------------------------------- 新状态a9b32 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 → 无进位 -------------------------------------------------- 最终状态a41b0C代码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只出现一次的数字 IILeetCode 1371. 题目描述给你一个整数数组 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 - 1nums 中除某个元素仅出现一次外其余每个元素都恰出现三次2. 解法比特位计数算法思路设要找的数位 ret。由于整个数组中需要找的元素只出现了「一次」其余的数都出现的「三次」因此我们可以根据所有数的「某一个比特位」的总和 %3 的结果快速定位到 ret 的「一个比特位上」的值是 0 还是 1。这样我们通过 ret 的每一个比特位上的值就可以将 ret 给还原出来。1 统计数组中所有数字每一个二进制位上 1 出现的次数。2 因为其他数字都出现了 3 次所以每一位上 1 的个数要么是 3 的倍数要么是 3k1如果目标数的该位是 1。3 对每一位的计数取模 3如果结果为 1说明目标数的这一位是 1否则是 0。4 按位还原出目标数即可。举个具体例子假设数组是[2, 2, 3, 2]出现3次的数2二进制10只出现1次的目标数3二进制11步骤1统计每一个二进制位上1出现的次数我们把数组里所有数转成二进制按位统计数字二进制第1位/最低位二进制第2位201201311201计数14步骤2分析计数的规律因为其他数字都出现了3次所以如果目标数的某一位是0那这一位的1的总个数 3 ×出现3次的数在这一位的1的个数也就是3的倍数如果目标数的某一位是1那这一位的1的总个数 3 ×出现3次的数在这一位的1的个数 1也就是3k1对应我们的例子第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的二进制1017的二进制111统计每一位1的次数位从低到高第1位第2位第3位计数414取模3第1位4%31 → 1 第2位1%31 → 1 第3位4%31 → 1 拼起来111 → 7正确总结统计每一位1的次数把数组所有数按二进制位拆分逐位计数利用3次的规律出现3次的数每一位的1的贡献都是3的倍数不会影响取模3的结果取模3还原目标数结果为1 → 目标数这一位是1结果为0 → 目标数这一位是0C 算法代码class Solution { public: int singleNumber(vectorint 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.191. 题目描述给定一个数组包含从 1 到 N 所有的整数但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗以任意顺序返回这两个数字均可。示例 1: 输入: [1] 输出: [2,3]示例 2: 输入: [2,3] 输出: [1,4]提示: nums.length 300002. 解法位运算算法思路本题就是 268.丢失的数字 260.只出现一次的数字 III 组合起来的题。先将数组中的数和 [1, n 2] 区间内的所有数「异或」在一起问题就变成了有两个数出现了「一次」其余所有的数出现了「两次」。进而变成了 260.只出现一次的数字 III 这道题。1 把数组里的所有数和 [1, n2] 范围内的所有数全部异或。最终的结果 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]也就是 n4n26缺失的两个数字a4b6步骤1所有数异或得到 a ^ b我们把数组里的数和**[1, n2] 范围内的数**全部异或数组[1, 2, 3, 5] 范围[1, 2, 3, 4, 5, 6]异或运算规则x ^ x 0x ^ 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 110100 ^ 110 ------ 010所以 tmp 4 ^ 6 2二进制 010步骤2找到tmp中第一个为1的二进制位tmp 010从右往左低位到高位数第1位最右0 第2位1 ✅ 第3位0所以我们选第2位作为分组依据a和b在这一位不同4的第2位是06的第2位是1步骤3按这一位分组分别异或得到a和b分组规则组1第2位为0的数 组2第2位为1的数我们把所有参与异或的数数组范围按这个规则分组数字二进制第2位分组10010组120101组230111组251010组110010组120101组230111组241000组151010组161101组2组1异或第2位为01 ^ 5 ^ 1 ^ 4 ^ 5 (1^1) ^ (5^5) ^ 4 0 ^ 0 ^ 4 4✅ 得到第一个缺失数4组2异或第2位为12 ^ 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]n4n28缺失a1b8步骤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^11101011 (11) tmp 1^8 9(1001)这里简化后实际最终tmp1^89步骤2找第一个1位第1位最右步骤3分组异或最终得到1和8总结1 所有数异或后出现2次的数会相互抵消x^x0只剩下两个缺失数的异或结果tmpa^b2 tmp中为1的位说明a和b在这一位不同以此分组可以把a和b分到不同组3 每组内的数异或出现2次的数抵消最终剩下的就是两个缺失数C 算法代码class Solution { public: vectorint missingTwo(vectorint 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)以上就是几道典型位运算题的完整思路与实现。理解核心性质后这类题目往往能写出简洁高效的代码。位运算看似抽象实则规律清晰。掌握这些经典思路就能轻松解决一类高频算法题。