位运算入门到精通：3道经典LeetCode题带你吃透二进制思维

位运算入门到精通3道经典LeetCode题带你吃透二进制思维文章目录位运算入门到精通3道经典LeetCode题带你吃透二进制思维一、引言为什么要学位运算二、位运算核心基础先搞懂5大核心运算符位运算核心性质高频考点三、经典实战1LeetCode 371. 两整数之和题目描述解题思路用二进制加法模拟十进制加法代码实现C复杂度分析四、经典实战2LeetCode 268. 丢失的数字题目描述解题思路利用异或的自反性消去重复元素代码实现C复杂度分析其他解法对比五、经典实战3面试题 01.01. 判定字符是否唯一题目描述解题思路用位掩码BitMap实现O(1)空间代码实现C复杂度分析其他解法对比六、位运算核心思想总结位运算解题通用技巧七、结语一、引言为什么要学位运算位运算是计算机世界最底层的运算逻辑也是算法面试中考察编程功底的高频考点。它直接操作二进制位能实现时间复杂度O(1)、空间复杂度O(1)的极致优化是算法优化的「核武器」。很多开发者对位运算望而生畏本质是没搞懂二进制的底层逻辑和核心应用场景。本文将从位运算基础原理出发结合3道经典LeetCode真题由浅入深拆解位运算的核心思想帮你彻底掌握这一算法利器轻松应对面试中的位运算题目。二、位运算核心基础先搞懂5大核心运算符在刷题前我们先系统回顾位运算的核心运算符这是所有位运算算法的基础运算符名称运算规则核心作用示例以8位二进制为例按位与两位都为1结果为1否则为0取指定位、判断奇偶、清零指定位5 3 100000101 00000011 00000001按位或只要有一位为1结果为1置位指定位、合并状态^按位异或两位不同为1相同为0翻转指定位、交换数、找只出现一次的数5 ^ 3 600000101 ^ 00000011 00000110~按位取反0变11变0求负数补码、掩码生成~5 -6补码表示下00000101取反为11111010对应-6左移二进制位左移高位丢弃低位补0等价于乘以2ⁿ5 1 1000000101 1 00001010右移二进制位右移低位丢弃高位补符号位等价于除以2ⁿ向下取整5 1 200000101 1 00000010位运算核心性质高频考点异或的三大核心性质交换律a ^ b b ^ a结合律(a ^ b) ^ c a ^ (b ^ c)自反性a ^ a 0a ^ 0 a与运算的核心性质a 1可判断奇偶结果为1是奇数0是偶数左移/右移的边界左移可能导致溢出右移对负数仍保持符号位不变算术右移三、经典实战1LeetCode 371. 两整数之和题目描述给你两个整数a和b不使用运算符和-计算并返回两整数之和。示例 1输入a 1, b 2 输出3示例 2输入a 2, b 3 输出5提示-1000 a, b 1000解题思路用二进制加法模拟十进制加法我们日常的十进制加法本质是「本位相加 进位处理」二进制加法同理本位和由异或运算得到a ^ b相同为0不同为1对应无进位加法进位由与运算 左移得到(a b) 1只有两位都为1时才会产生进位左移1位是进位到高位因此我们可以循环执行以下步骤直到进位为0计算无进位和x a ^ b计算进位carry (a b) 1将a更新为xb更新为carry重复步骤1-3直到b 0此时a就是最终的和代码实现CclassSolution{public:intgetSum(inta,intb){// 循环直到进位为0while(b!0){// 计算无进位和intxa^b;// 计算进位左移1位intcarry(ab)1;// 更新a为无进位和b为进位ax;bcarry;}returna;}};复杂度分析时间复杂度O(1)整数的二进制位数固定32位循环次数最多为32次空间复杂度O(1)仅使用常数额外空间四、经典实战2LeetCode 268. 丢失的数字题目描述给定一个包含[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 中。解题思路利用异或的自反性消去重复元素根据异或的自反性a ^ a 0a ^ 0 a我们可以设计如下思路先将[0, n]所有的数依次异或得到一个基准值再将数组中所有的数依次与基准值异或最终结果就是丢失的数字因为出现过的数字会两两异或为0只剩下未出现的数字为了简化代码我们可以直接将基准值初始化为n数组长度然后遍历数组将ret ^ nums[i] ^ i一次遍历即可完成计算。代码实现CclassSolution{public:intmissingNumber(vectorintnums){// 初始化为n数组长度对应[0,n]的上限intretnums.size();// 遍历数组依次异或索引和元素for(inti0;inums.size();i){ret^nums[i]^i;}returnret;}};复杂度分析时间复杂度O(n)仅需一次遍历数组空间复杂度O(1)仅使用常数额外空间完美满足空间优化要求其他解法对比解法思路时间复杂度空间复杂度缺点异或法利用自反性消去重复元素O(n)O(1)最优无溢出风险求和法用[0,n]的和 - 数组和O(n)O(1)大数求和可能溢出哈希法用哈希表记录出现的数字O(n)O(n)空间复杂度高五、经典实战3面试题 01.01. 判定字符是否唯一题目描述实现一个算法确定一个字符串s的所有字符是否全都不同。示例 1输入: s leetcode 输出: false示例 2输入: s abc 输出: true限制0 len(s) 100s[i]仅包含小写字母如果你不使用额外的数据结构会很加分。解题思路用位掩码BitMap实现O(1)空间题目要求不使用额外数据结构而字符串仅包含26个小写字母正好可以用一个32位整数作为位掩码用整数的第0~25位分别对应字符a~z遍历字符串时计算字符对应的位i ch - a检查掩码的第i位是否为1如果是说明字符重复返回false否则将掩码的第i位置为1继续遍历遍历完成无重复返回true同时我们可以做一个优化如果字符串长度超过26根据鸽巢原理必然有重复字符直接返回false。代码实现CclassSolution{public:boolisUnique(string astr){// 鸽巢原理长度超过26必然有重复if(astr.size()26)returnfalse;// 位掩码初始为0intbitMap0;// 遍历字符串for(autoch:astr){// 计算字符对应的位a对应0b对应1...z对应25intich-a;// 检查该位是否已被置1说明重复if(((bitMapi)1)1){returnfalse;}// 将该位置1bitMap|1i;}returntrue;}};复杂度分析时间复杂度O(n)n为字符串长度仅需一次遍历空间复杂度O(1)仅使用一个整数作为掩码完美满足无额外数据结构的要求其他解法对比解法思路时间复杂度空间复杂度缺点位掩码法用整数存储字符出现状态O(n)O(1)最优空间极致优化哈希集合用集合记录出现的字符O(n)O(1)最多26个元素不符合「无额外数据结构」的加分要求暴力法双重循环遍历比较O(n²)O(1)时间复杂度高效率低六、位运算核心思想总结通过这3道经典题目我们可以总结出位运算的三大核心应用场景替代常规运算用异或、与、移位替代加减乘除实现无运算符加法等特殊需求状态压缩用整数的二进制位存储状态实现O(1)空间的极致优化如字符唯一判定消去重复元素利用异或的自反性快速找到只出现一次的元素、丢失的数字等位运算解题通用技巧遇到「不使用加减」的加法题优先用「异或求无进位和 与运算求进位」的思路遇到「找只出现一次的数/丢失的数」优先用异或的自反性消去重复元素遇到「状态存储/字符判定」优先用位掩码用整数的二进制位存储状态压缩空间遇到「奇偶判断/取指定位」优先用与运算高效实现判断和提取七、结语位运算是计算机科学的底层语言也是算法优化的核心工具。掌握位运算不仅能帮你轻松应对面试中的高频考点更能让你从二进制的视角理解计算机的运行逻辑写出更高效、更优雅的代码。本文的3道题目覆盖了位运算最核心的应用场景建议你亲手敲一遍代码结合二进制演算理解每一步的逻辑彻底吃透位运算的核心思想。如果你觉得这篇文章对你有帮助欢迎点赞、收藏、转发也可以在评论区分享你的位运算解题技巧~LeetCode 136. 只出现一次的数字异或经典题LeetCode 191. 位1的个数位运算基础题LeetCode 231. 2 的幂与运算经典应用