[面试题] C++ bitset容器深度解析：从bitmap原理到海量数据去重实战

我们来看一个腾讯的经典面试问题：内存限制1G，假设每个QQ号用占用4字节，那么如何在43亿个QQ号中进行去重？

这个问题通常的解决方案是使用 bitmap（位图）这一经典的数据结构。在传统的C语言中，需要自己实现位图操作，而在现代C++中，标准库提供了 bitset 容器，它完美封装了Bitmap思想，提供了标准且易用的接口。

底层实现：动态数组与位运算

bitset 的底层实现核心是整数数组配合位运算。它将多个比特位（bit）打包存储在一个更大的整型单元中，例如 unsigned int 或 unsigned long long。

bitset 在底层会封装一个整数数组，其大小根据模板参数N自动计算。例如：

• bitset<32>： 可能用一个 unsigned int（32位）存储。
• bitset<64>： 可能用一个 unsigned long long（64位）存储。
• bitset<100>： 则需要两个 unsigned long long，第一个存64位，第二个存36位。

空间优势对比非常明显。假设存储8个布尔值 [true, false, true, false, true, false, true, false]：

• 用 bool 数组存储：需要8字节，每个 bool 占1字节。
• 用 bitset<8> 存储：仅需1字节（8个比特位），内存布局为二进制 01010101（十六进制0x55）。

因此，bitset 的空间占用通常只有 bool 数组的 1/8，在处理海量状态标记（如去重、标志位管理）时优势巨大。

bitset基本使用：初始化、访问与位运算

使用 bitset 需要包含头文件 <bitset>。其模板参数 N 是比特位的数量，必须是编译期常量。

1. 初始化方式

bitset 支持多种初始化方式，适配不同场景。

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

int main(){
    // 方式1: 默认初始化，所有位为0
    bitset<8> b1;
    cout << "b1: " << b1 << endl; // 输出：00000000

    // 方式2: 整数初始化
    bitset<8> b2(0x55); // 十六进制0x55 -> 二进制01010101
    bitset<8> b3(10);   // 十进制10 -> 二进制00001010
    // 若整数位数超出bitset大小，仅取低N位
    bitset<4> b4(0x12); // 0x12(10010)取低4位 -> 0010

    // 方式3: 字符串初始化（首个字符对应高位）
    string s1 = "10101010";
    bitset<8> b5(s1);            // 直接使用字符串
    bitset<8> b6("1010");        // 字符串较短，高位补零 -> 00001010
    bitset<4> b7("101010");      // 字符串较长，取前4位"1010"
    bitset<4> b8(s1, 2, 4);      // 从s1索引2开始，截取4个字符("1010")

    cout << "b5: " << b5 << endl; // 输出：10101010
    // ... 其他输出
    return 0;
}

2. 访问与修改比特位

bitset 提供两种访问方式：下标运算符 [] 和成员函数 test()。需要注意，下标0对应二进制的最低位（最右边）。

方式	特点
b[i]	返回第i位的引用，可赋值，不做边界检查。
b.test(i)	返回第i位的值，越界会抛出std::out_of_range异常。

修改操作可以通过 [] 赋值，或使用成员函数：

• b.set(pos): 将指定位置1；无参数则所有位置1。
• b.reset(pos): 将指定位置0；无参数则所有位置0。
• b.flip(pos): 翻转指定位（0变1，1变0）；无参数则翻转所有位。

#include <bitset>
#include <iostream>
#include <stdexcept>
using namespace std;

int main(){
    bitset<8> b("00000000");
    // 访问
    cout << "b[0]: " << b[0] << endl;      // 0 (最低位)
    cout << "b.test(7): " << b.test(7) << endl; // 0 (最高位)

    // 修改
    b[0] = 1;     // 最低位置1
    b.set(7);     // 最高位置1
    b.reset(3);   // 第3位置0
    b.flip(5);    // 第5位翻转
    cout << "修改后b: " << b << endl; // 输出：10100001
    return 0;
}

3. 位运算操作

bitset 支持所有标准位运算符，如与(&)、或(|)、异或(^)、左移(<<)、右移(>>)、取反(~)，这些操作是高效算法和网络/系统底层编程的基础。

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

int main(){
    bitset<8> b1("10101010");
    bitset<8> b2("01010101");

    cout << "b1 & b2: " << (b1 & b2) << endl; // 与：00000000
    cout << "b1 | b2: " << (b1 | b2) << endl; // 或：11111111
    cout << "b1 ^ b2: " << (b1 ^ b2) << endl; // 异或：11111111
    cout << "b1 << 2: " << (b1 << 2) << endl; // 左移：10101000
    cout << "~b1: " << (~b1) << endl;         // 取反：01010101
    return 0;
}

4. 其他常用成员函数

成员函数	功能说明	示例
size()	返回比特位数量（编译期确定）	bitset<8> b; b.size() 返回 8
count()	返回值为1的比特位个数	bitset<8> b(“1010”); b.count() 返回 2
any()	判断是否有位为1	全0时返回 false
none()	判断是否全为0	全0时返回 true
all()	判断是否全为1 (C++11)	全1时返回 true
to_ulong() / to_ullong()	转换为无符号长整型，可能抛出 overflow_error
to_string()	转换为 ‘0’/‘1’ 字符串

实战：QQ号去重问题

现在，我们用 bitset 解决开头的腾讯面试题。假设QQ号为32位无符号整数，需要找出并去重。

实现思路：

1. 创建一个足够大的 bitset（2^32 位）。
2. 遍历所有QQ号，将对应比特位置1，实现标记。
3. 遍历 bitset，输出所有为1的位对应的QQ号。

#include <bitset>
#include <fstream>
#include <iostream>

// QQ号最大值是2^32-1，需要4294967296位
constexpr size_t MAX_QQ = 1ULL << 32;
using QQBitset = std::bitset<MAX_QQ>;

bool process_qq(QQBitset& bs, unsigned int qq) {
    if (qq < 10001) return false; // 过滤无效号
    if (bs.test(qq)) return false; // 已存在
    bs.set(qq);
    return true;
}

int main() {
    QQBitset bs;
    std::ifstream in("qq_numbers.txt");
    std::ofstream out("unique_qq.txt");
    unsigned int qq;
    size_t count = 0;

    // 读取并标记
    while (in >> qq) {
        if (process_qq(bs, qq)) ++count;
    }
    // 输出结果
    for (size_t i = 10001; i < MAX_QQ; ++i) {
        if (bs.test(i)) out << i << '\n';
    }
    std::cout << "去重完成，共" << count << "个不重复QQ号" << std::endl;
    return 0;
}

内存计算：2^32 bit = 512 MB，满足1G内存限制。代码简洁且利用了标准算法/数据结构容器，移植性好。

易错点与注意事项

1. 大小必须是编译期常量 bitset 的模板参数 N 必须是编译期常量，无法动态调整大小。

   int n = 8;
   // bitset<n> b1; // 错误：n是变量
   const int N = 8;
   bitset<N> b2; // 正确

   替代方案：需要动态大小时，可使用 vector<bool>（特化实现，也压缩存储）或自定义基于 vector<unsigned long long> 的动态位图。

2. 位序：下标0对应最低位 这是最常见的混淆点。bitset 下标0对应二进制最右边（最低有效位），与我们书写习惯（高位在左）相反，编程时需特别注意。

3. 警惕越界访问

   • 使用 [] 越界访问是未定义行为。
   • 使用 test(), set(), reset(), flip() 越界会抛出 std::out_of_range 异常。
   • to_ulong()/to_ullong() 在数值超出目标类型范围时，会抛出 std::overflow_error。

4. 适用场景：仅为布尔状态 bitset 的核心优势是节省空间，专为存储大量布尔状态设计。若非布尔场景（如存整数、字符串），应选用 vector<T>、unordered_set 等更合适的数据结构。对于存在误差允许的海量数据存在性判断，可以考虑布隆过滤器（Bloom Filter）。

总结

bitset 是C++标准库中基于bitmap思想的高效位状态管理工具，其核心价值在于极致的空间效率。它将8个布尔值压缩至1字节存储，是处理海量数据标记、去重、位标志集合等问题的利器。

学习要点：

• 底层：整数数组存储，位运算操作，大小编译期固定。
• 使用：掌握初始化、访问([], test)、修改(set, reset, flip)及位运算。
• 注意：大小需常量、下标0是最低位、警惕越界、明确适用场景（布尔值）。
• 场景：适用于比特位数量固定、需要密集存储布尔值并进行位操作的场合，是理解网络/系统底层和设计高性能算法/数据结构的重要组件。