位运算算法核心技巧与经典例题解析 | 极客日志

C++算法

位运算算法核心技巧与经典例题解析

系统讲解了位运算的基础符号、常用技巧（如取反、异或、位图思想）及优先级，并通过六个经典算法题（判定字符唯一、丢失数字、两整数之和、只出现一次的数字 II、消失的两个数字）展示了位运算在实际编程中的应用。内容涵盖哈希表替代方案、高斯求和、二分查找及异或抵消等解法，提供了完整的 C++ 代码实现与复杂度分析，适合算法学习者深入理解位操作优化。

leon发布于 2026/3/24更新于 2026/4/162 浏览

位运算算法核心技巧与经典例题解析

常见位运算总结

基础位运算符号

这六个位运算符是实现位运算算法的重要运算符，在 C 语言阶段有详细的介绍。

位运算符号

记法如图所示，强调一下什么是无进位相加？

异或运算的规则决定了它天然契合无进位相加的概念。异或运算在比较两个二进制位时，0 ^ 0 = 0，0 ^ 1 = 1，1 ^ 0 = 1，1 ^ 1 = 0。只是单纯对比两个数在每一位上的值，将不同的视为 1，相同的视为 0，不涉及向高位进位。

确定二进制表示中的第 x 位是 0 还是 1

约定二进制位从右到左，为最低位到最高位，定义为从 0 到 31，为的就是对应右移 x 位刚好对应第 x 位。所以将要比较的数 n 的第 x 位右移 x 位，与 1 按位与 &，如果是 0，第 x 位为 0；如果是 1，第 x 位是 1。

确定第 x 位

修改二进制表示的第 x 位

修改成 1： 要修改数 n 第 x 位为 1 就不能破坏原来的数，所以将 1 移动 x 位，与 1 按位或 |，只修改了我们想要修改的那一位。

修改为 1

修改成 0： 要修改数 n 第 x 位为 0 就不能破坏原来的数，所以将 1 移动 x 位，取反 ~ 为 0，与 1 按位与 &，只修改了我们想要修改的那一位。

修改为 0

位图的思想

位图其实和哈希表相似，哈希表是额外开辟一个空间，计算数据出现频次，而位图则是把数据存在数据类型一个个字节里，这就省去了多开一个空间，然后利用上述的方法修改为 1 或 0，统计数是否出现过。

位图思想

提取最右侧的 1

将数 n 取反后 +1 得到相反数 -n，然后两数按位与 & 得到最右侧的 1。即最右侧的 1 及其右边都不变，左边的数都变成 0。

提取最右侧 1

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，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
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    bool isUnique(string astr) {
        if (astr.size() > 26) {
            return false;
        }
        int bitMap = 0;
        for (auto ch : astr) {
            int i = ch - 'a';
            if ((bitMap >> i) & 1 == 1) {
                return false;
            }
            bitMap |= 1 << i;
        }
        return true;
    }
};

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = 0;
        for (auto x : nums) {
            ret ^= x;
        }
        for (int i = 0; i <= nums.size(); ++i) {
            ret ^= i;
        }
        return ret;
    }
};

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            int x = a ^ b;
            unsigned int carry = (unsigned int)(a & b) << 1;
            a = x;
            b = carry;
        }
        return a;
    }
};

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (int i = 0; i < 32; ++i) {
            int sum = 0;
            for (auto x : nums) {
                if (((x >> i) & 1) == 1) {
                    sum++;
                }
            }
            sum %= 3;
            if (sum == 1) {
                ret |= 1 << i;
            }
        }
        return ret;
    }
};

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int ret = 0;
        for (auto x : nums) {
            ret ^= x;
        }
        for (int i = 1; i <= nums.size() + 2; ++i) {
            ret ^= i;
        }
        int diff = 0;
        while (1) {
            if (((ret >> diff) & 1) == 1) {
                break;
            } else {
                diff++;
            }
        }
        int a = 0, b = 0;
        for (auto 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};
    }
};