算法题讲解：位运算解决两数之和与缺失数字问题 | 极客日志

C++算法

算法题讲解：位运算解决两数之和与缺失数字问题

位运算解决经典算法题。包括两整数之和（无进位加法循环）、只出现一次的数字 II（比特位计数模三）、消失的两个数字（异或分组）。代码使用 C++ 实现，涵盖算法思路与流程解析。

CloudNative发布于 2026/3/23更新于 2026/5/910 浏览

35.两个整数之和

题目链接：

371. 两整数之和 - 力扣（LeetCode）

题目描述：

文章配图

题目示例：

文章配图

解法（位运算）：

算法思路：

异或 ^ 运算本质是【无进位加法】
按位与 & 操作能够得到【进位】的对应位置，但还需要左移 1 才是需要进位的位置。
然后一直循环，直到【进位】变成 0 为止

C++ 算法代码：

class Solution {
public:
    int getSum(int a, int b) {
        // 解法：位运算 (^异或：无进位相加)
        while(b) {
            int x = a ^ b;
            int y = (a & b) << 1;
            a = x;
            b = y; // 得到进位的对应位置，再左移 1 才是需要进位的位置
                   // 只进行一次 a & b 不一定保证新的 a 和 b 没有需要进位的位置，所以需要将这个步骤进行循环
                   // a & b 为 0 则说明没有进位的位置了
        }
        return a ^ b;
    }
};

算法总结及流程解析：

文章配图

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Gemini 图片去水印
基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印，支持批量处理与下载。在线工具，Gemini 图片去水印在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // 方法一：排序 (时间复杂度较大:O(NlogN)，但容易想到)
        // sort(nums.begin(), nums.end());
        // for(int i = 0; i < nums.size() - 1; i += 3) {
        //     if(nums[i] != nums[i + 1]) {
        //         return nums[i];
        //     }
        // }
        // return nums.back();
        
        // 方法二：位运算 (为线性时间复杂度:O(32N)，但非常巧妙比较难想)
        int ret = 0; // 作为位图
        for(int i = 0; i < 32; i++) { // 一个数二进制位的长度，依次修改 ret 的每一位
            int sum = 0;
            for(int x = 0; x < nums.size(); x++) { // 计算 nums 中所有数的二进制第 i 位的和
                sum += ((nums[x] >> i) & 1);
            }
            ret |= ((sum % 3) << i); // 求和结果余 3 后修改到 ret 对应第 i 位的位置
        }
        return ret;
    }
};

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        // 位运算
        // 先将数组 nums 所有数以及 1~N+2 区间所有数全部异或一遍，得到消失两数的异或
        int ret = 0;
        int a = 0;
        int b = 0; // 分别表示两个消失的数
        
        for(int i = 0; i < nums.size(); i++) {
            ret ^= nums[i];
        }
        for(int i = 1; i <= nums.size() + 2; i++) {
            ret ^= i;
        }
        // 此时 ret = a ^ b
        // 由于 a 和 b 一定不同，所以一定会存在某一位比特位一个是 0 一个是 1
        // 两者异或后对应的那一位就一定是 1，所以我们需要找到那一位
        // 获取到 ret 最右侧出现 1 的比特位位置
        int x = 0;
        while(1) {
            if(((ret >> x) & 1) == 1) {
                break;
            }
            x++;
        }
        
        // 将数组 nums 所有数以及 (1~N+2) 区间所有数分成两类：
        // 一类就是第 x 位比特位值为 0，一类就是第 x 位比特位值为 1
        // 这样两个消失数就会被分开，通过异或，在数组以及 (1~N+2) 区间都出现的数就会抵消，
        // a 和 b 也就分别是这两个消失数了
        for(int i = 0; i < nums.size(); i++) {
            if(((nums[i] >> x) & 1) == 0) // 假设 a 是第 x 位比特位为 0 的消失数
            {
                a ^= nums[i];
            } else // 假设 b 就是第 x 位比特位为 1 的消失数
            {
                b ^= nums[i];
            }
        }
        for(int i = 1; i <= nums.size() + 2; i++) {
            if(((i >> x) & 1) == 0) {
                a ^= i;
            } else {
                b ^= i;
            }
        }
        // 两次循环则数组中存在的数异或了两次被抵消，a 和 b 就分别是两个消失数
        return {a, b};
    }
};

算法题讲解：位运算解决两数之和与缺失数字问题

35.两个整数之和

题目链接：

题目描述：

题目示例：

解法（位运算）：

算法思路：

C++ 算法代码：

算法总结及流程解析：

更多推荐文章

相关免费在线工具

36.只出现一次的数字 II

题目链接：

题目描述：

题目示例：

解法（比特位计数）：

算法思路：

C++ 算法代码：

算法总结及流程解析：

38.消失的两个数字

题目链接：

题目描述：

题目示例：

解法（位运算）：

算法思路：

C++ 算法代码：

算法总结及流程解析：

更多推荐文章

相关免费在线工具

算法题讲解：位运算解决两数之和与缺失数字问题

35.两个整数之和

题目链接：

题目描述：

题目示例：

解法（位运算）：

算法思路：

C++ 算法代码：

算法总结及流程解析：

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

36.只出现一次的数字 II

题目链接：

题目描述：

题目示例：

解法（比特位计数）：

算法思路：

C++ 算法代码：

算法总结及流程解析：

38.消失的两个数字

题目链接：

题目描述：

题目示例：

解法（位运算）：

算法思路：

C++ 算法代码：

算法总结及流程解析：

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具