CC++ & Algorithm

bitset位集的原理与应用

极难2
语言版本：通用
概述：学习C++中高效存储和操作比特位的bitset容器，以及Python中通过整数位运算模拟位集。

比特级的“开关面板”：C++ bitset 与 Python 位运算模拟

想象一下，你是班级的考勤管理员，班里有32个同学。每天要记录谁来了、谁没来。最直接的方法是拿一张纸，写上所有名字，然后在名字旁打勾或打叉。但这样做，每个同学的状态需要1个字节（比如用 bool 存），32个同学就要32个字节。其实，一个同学的状态只需要1个比特——0表示没来，1表示来了。32个同学只需要 4个字节（32比特）就够了！这就是 位集（bitset） 的威力：把多个逻辑值压缩到一个整数里，用每一位来代表一个开关。

C++ 标准库提供了 std::bitset，它是一个固定大小的容器，专门用来存储和操作比特位。你可以把它想象成一个超级紧凑的“开关面板”，每个开关代表一个标记位。你不仅可以一次性翻转、置位、查询所有开关，还能像集合一样做并、交、差运算。

Python 中没有内置的 bitset 类，但我们可以用整数的位运算来模拟同样的功能——Python 的整数可以无限大，非常适合做“大位集”。

为什么要用 bitset？——存储和速度的“双赢”

存储方式占用的空间（32个状态）能否快速做集合运算
bool 数组至少 32 字节（通常 32 个字节）不能直接做位运算
bitset<32>4 字节能直接 &、`

更重要的是，位运算在 CPU 层面是一条指令完成的，速度极快。比如判断“今天来的人里有没有小明和小红同时来的情况”，只需要把两个人的位做 & 运算，结果非零即表示两人都来了。

C++ bitset 原理和使用方法

std::bitset 定义在头文件 <bitset> 中，模板参数是 位数（编译期常量），比如 std::bitset<32> 表示 32 位的位集。它内部用一个或多个无符号整数存储位，但对外提供了非常直观的接口。

创建 bit set

#include <iostream>
#include <bitset>
#include <string>

int main() {
    // 1. 创建一个8位的位集，初始所有位为0
    std::bitset<8> bs1;          // 默认全0
    std::cout << "bs1: " << bs1 << std::endl;  // 输出: 00000000

    // 2. 用二进制字符串初始化
    std::bitset<8> bs2("10101110");  // 字符串最左边是最高位（索引7），最右边是最低位（索引0）
    std::cout << "bs2: " << bs2 << std::endl;  // 输出: 10101110

    // 3. 用无符号整数初始化
    std::bitset<8> bs3(0b10101110);  // 等同于上面，直接用整数
    std::cout << "bs3: " << bs3 << std::endl;  // 输出: 10101110
}

特别注意下标方向：bitset 的下标 0 表示 最低位（最右边），下标 7 表示最高位（最左边）。例如 bs2[0] 是最后一个字符 '0'，bs2[7] 是第一个字符 '1'。这一点与人类的读写习惯（从左到右）相反，新手容易搞混！

常用成员函数（“开关面板”上的操作）

成员函数说明生活中的比喻
operator[]访问第 i 位（可读写，不检查越界）直接拨动开关
test(i)检查第 i 位是否为 1（返回 bool，会检查越界并抛出异常）安全地查看开关状态
set() / set(i, true)将所有位设为 1，或设置某一位为 1把所有开关拨到“开”
reset() / reset(i)将所有位设为 0，或重置某一位把所有开关拨到“关”
flip() / flip(i)翻转所有位，或翻转某一位把开关状态反过来
count()返回 1 的个数统计有多少个开关是“开”的
any()是否有任何位为 1是否至少有一个开关开着
none()是否所有位为 0是否所有开关都关着
all()是否所有位为 1是否所有开关都开着
to_string()转换为字符串（如 "1010"）把开关状态写下来
to_ulong() / to_ullong()转换为无符号整数（若位数超过则抛异常）把开关状态当做一个数字

小提示：test(i) 比 operator[] 更安全，因为 operator[] 不会检查下标范围，越界会导致未定义行为；而 test 会抛出 std::out_of_range 异常。建议养成用 test 的习惯。

位运算：集合操作

bitset 支持 &（与）、|（或）、^（异或）、~（取反），这让我们可以像操作数学集合一样操作位集。

std::bitset<8> bs3("11110000");  // 代表集合 {4,5,6,7}
std::bitset<8> bs4("00111100");  // 代表集合 {2,3,4,5}

auto bs_and = bs3 & bs4;  // 交集: 00110000 → {4,5}
auto bs_or  = bs3 | bs4;  // 并集: 11111100 → {2,3,4,5,6,7}
auto bs_xor = bs3 ^ bs4;  // 对称差: 11001100 → {2,3,6,7}
auto bs_not = ~bs3;       // 补集: 00001111 → {0,1,2,3}

生活中的例子：假设你和同桌都有一张“今天要带的东西”的清单（0表示不带，1表示带），bs3 是你的清单，bs4 是同桌的清单。那么 bs_and 就是你们俩都带的东西（交集），bs_or 是至少一人带的东西（并集），bs_xor 是你俩中正好一人带的东西（对称差）。

时间复杂度

  • 对 32/64 位的 bitset，所有位运算几乎都是 O(1)（编译器优化为单条指令）。
  • 对任意大小（比如 1000 位），内部会拆成多个字，按位运算复杂度为 O(N/word_size)，但仍然非常快。
  • count() 内部使用 CPU 的 POPCNT 指令（现代 CPU 支持），高效统计 1 的个数。

完整 C++ 示例：考勤管理

下面程序模拟一个班级（8个学生）的考勤记录，演示常用操作。

#include <iostream>
#include <bitset>
#include <string>

int main() {
    // 班级有8个学生，学号0~7
    std::bitset<8> attendance;  // 默认全0，表示今天全没来

    // 模拟签到：学号0、2、4、5来了
    attendance.set(0);   // 学号0 签到了
    attendance.set(2);   // 学号2 签到了
    attendance.set(4);   // 学号4 签到了
    attendance.set(5);   // 学号5 签到了

    std::cout << "今日签到情况: " << attendance << std::endl;  // 输出: 00110101 (位0、2、4、5为1)
    std::cout << "来了多少人? " << attendance.count() << std::endl;  // 4人

    // 检查学号3来了没
    if (attendance.test(3)) {
        std::cout << "学号3来了" << std::endl;
    } else {
        std::cout << "学号3没来" << std::endl;
    }

    // 翻转学号0的状态（假设他/她签到后又走了）
    attendance.flip(0);
    std::cout << "学号0离开后: " << attendance << std::endl;  // 位0变为0

    // 集合运算：找出同时签到的学号（其实这里就是自身）
    auto everyone = attendance;  // 复制
    // 假设另一组数据：学号1、2、3、4签到了
    std::bitset<8> other("00011110");  // 学号1,2,3,4
    auto common = attendance & other;  // 同时签到的学号
    std::cout << "两组的共同签到的学号: ";
    for (size_t i = 0; i < common.size(); ++i) {
        if (common.test(i)) {
            std::cout << i << " ";
        }
    }
    std::cout << std::endl;  // 输出: 2 4

    // 转换为整数
    std::cout << "attendance 的整数值: " << attendance.to_ulong() << std::endl;
    // 二进制 00110101 = 十进制 53

    return 0;
}

Python 中模拟 bit set

Python 没有现成的 std::bitset，但可以用整数位运算来模拟。Python 的整数可以任意大，因此非常适合处理大位集。我们可以封装一个简单的 Bitset 类。

class Bitset:
    def __init__(self, n, value=0):
        """n: 位数, value: 初始整数（默认0）"""
        self.n = n
        self.mask = (1 << n) - 1  # 掩码，保留低n位
        self.data = value & self.mask

    def set(self, i, val=True):
        """设置第i位为val（True/False）"""
        if val:
            self.data |= (1 << i)
        else:
            self.data &= ~(1 << i)

    def test(self, i):
        """测试第i位是否为1"""
        return (self.data >> i) & 1 == 1

    def flip(self, i):
        """翻转第i位"""
        self.data ^= (1 << i)

    def count(self):
        """返回1的个数（Python 3.8+推荐用 int.bit_count()）"""
        return self.data.bit_count()  # 更高效
        # return bin(self.data).count("1")  # 备选方法

    def __and__(self, other):
        return Bitset(self.n, self.data & other.data)

    def __or__(self, other):
        return Bitset(self.n, self.data | other.data)

    def __xor__(self, other):
        return Bitset(self.n, self.data ^ other.data)

    def __invert__(self):
        return Bitset(self.n, (~self.data) & self.mask)

    def __str__(self):
        # 高位在左，长度为n
        return f"{self.data:0{self.n}b}"

    def to_int(self):
        return self.data


# 测试：模拟考勤
bs = Bitset(8)  # 8个学生，初始全0
bs.set(0)
bs.set(2)
bs.set(4)
bs.set(5)
print("今日签到:", bs)  # 00110101
print("来了多少人:", bs.count())  # 4

# 集合运算
other = Bitset(8, int("00011110", 2))  # 学号1,2,3,4
common = bs & other
print("共同签到的学号:", [i for i in range(common.n) if common.test(i)])
# 输出: [2, 4]

注意：Python 的 int.bit_count() 是 Python 3.8 引入的，内部使用 CPU 指令，速度极快。如果兼容低版本，可以用 bin(x).count("1")。

新手常犯的错误

  1. 下标方向搞反：字符串初始化时，最左边的字符对应最高位（索引最大），而 bitset 的下标 0 是最低位（最右边）。例如 "101" 中，bs[0] 是 '1'? 不对，是最后一个字符 '1'？实际上 "101" 中索引 0 对应最右边的 '1'（最低位），索引 1 对应中间的 '0'，索引 2 对应最左边的 '1'。很容易混淆。记住：字符串从左到右是高位到低位，下标 0 是最低位（最右边）。

  2. 忘记 bitset 的大小是编译期常量：std::bitset<N> 的 N 必须是常量表达式，不能是变量。如果需要运行时决定位数，可用 std::vector<bool>（但有坑）或 Boost 的 dynamic_bitset。

  3. 用 operator[] 而不检查越界：operator[] 不进行范围检查，越界是未定义行为（可能程序崩溃或奇怪结果）。推荐用 test(i)，它会抛出 std::out_of_range 异常。

  4. 对太大位数调用 to_ulong()：如果位数超过 32（或 64），to_ulong() 会抛出 std::overflow_error。此时可以用 to_string() 或转为字符串后再转大整数（但注意精度）。

  5. Python 中忘记掩码：Python 的整数没有固定位数，取反操作 ~data 会产生无限多的前导 1，必须用掩码截断低 n 位，否则结果会出错。

相关知识点指引

  • std::vector<bool>：它是 C++ 中特殊的 vector，内部压缩存储比特位，但不是真正的容器（不满足容器的全部要求），且性能不一定比 bitset 好。如果位数在运行时才能确定，可以用 vector<bool> 或 deque<bool>，但更推荐 Boost 的 dynamic_bitset。
  • 布隆过滤器：一种基于位集和多个哈希函数的概率数据结构，用于判断一个元素是否可能在集合中。
  • 状态压缩动态规划：最常见的 bitset 应用场景之一。例如，旅行商问题（TSP）中用一个 bitset 表示已访问的城市集合；背包问题中用 bitset 优化可行性判断。
  • 位图（bitmap）：在图形编程和数据库索引中，用位集来快速查询和过滤数据。

掌握 bitset，你就拥有了一把“比特级”的瑞士军刀——既省内存又跑得快，尤其适合处理大量开关状态的场景。下次遇到需要标记的布尔数组时，先想想：“我能不能用 bitset？”

例题精讲

1单选题

关于C++标准库中的bitset，以下哪项描述是正确的？

Abitset的大小在运行时可以动态改变
Bbitset的模板参数必须是编译期常量
Cbitset支持存储任意数量的位，最大为1024
Dbitset的成员函数count()返回bitset中0的个数
2单选题

现有bitset<8> bs("10100110")，执行bs.set(1)后，bs的值变为？注意：位索引从0开始，最右边为第0位。

A10100110
B10100010
C10100111
D10101110
3判断题

bitset<10> bs("1010101010"); int n = bs.count(); 则n的值为5。

4填空题
以下代码使用bitset判断一个整数n是否为奇数，请填空：
bool is_odd(int n) {
    std::bitset<32> bs(n);
    return __;
}
5填空题
以下代码将bitset<8>对象转换成unsigned long long类型，请填空：
std::bitset<8> bs("11110000");
unsigned long long val = ___;
std::cout << val; //输出240