bitset - C++程序设计

bitset 概述

bitset 是固定长度的位序列容器，用于高效的位操作。

bitset 的特点

固定长度（编译时确定）
每个元素是一个 bit（0或1）
位操作极其高效
内存占用小（8个bit占用1字节）

常用场景

状态标记：标记多个状态
布尔数组：快速查询元素是否存在
位运算：位图算法
子集枚举：枚举所有子集

bitset 基本用法


#include <bitset>
using namespace std;

int main() {
    // 创建 bitset
    bitset<8> b1;           // 8位，全为0
    bitset<8> b2(10);       // 8位，值为10（00001010）
    bitset<8> b3("10101");  // 8位，值为"00010101"
    bitset<8> b4(string("11100011"));

    // 访问位
    cout << b2[0] << endl;   // 0（最低位）
    cout << b2[1] << endl;   // 1
    cout << b2[2] << endl;   // 0

    // 修改位
    b1.set(0);      // 设置第0位为1
    b1.set(1, 0);   // 设置第1位为0
    b1.reset(2);    // 设置第2位为0
    b1.flip(3);     // 翻转第3位

    // 设置所有位
    b1.set();       // 全部设为1
    b1.reset();     // 全部设为0
    b1.flip();      // 翻转所有位

    // 输出
    cout << b1 << endl;  // 输出二进制表示

    // 转换为数值
    unsigned long val = b1.to_ulong();

    // 计数
    int count = b1.count();   // 1的个数
    int size = b1.size();     // 总位数

    // 检查
    bool any = b1.any();      // 是否有1
    bool none = b1.none();    // 是否全为0
    bool all = b1.all();      // 是否全为1

    return 0;
}

位运算操作


bitset<8> a("00110101");  // 53
bitset<8> b("01011010");  // 90

// 按位与
bitset<8> c = a & b;
cout << c << endl;  // 00010000

// 按位或
c = a | b;
cout << c << endl;  // 01111111

// 按位异或
c = a ^ b;
cout << c << endl;  // 01101111

// 按位取反
c = ~a;
cout << c << endl;  // 11001010

// 左移
c = a << 2;
cout << c << endl;  // 11010100

// 右移
c = a >> 2;
cout << c << endl;  // 00001101

// 复合赋值
a &= b;  // a = a & b
a |= b;  // a = a | b
a ^= b;  // a = a ^ b
a <<= 2;
a >>= 2;

bitset 可视化

点击按钮观察位操作效果：

输入(0-255):

当前值: 42

位操作

操作历史：

bitset 应用示例

1. 判断素数（埃拉托斯特尼筛法）


bitset<100001> prime;  // 标记是否为素数

void sieve(int n) {
    prime.set();  // 初始化全为1（假设都是素数）
    prime[0] = prime[1] = 0;  // 0和1不是素数

    for (int i = 2; i * i <= n; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                prime[j] = 0;  // 标记为合数
            }
        }
    }
}

int main() {
    sieve(100);

    for (int i = 2; i <= 100; i++) {
        if (prime[i]) {
            cout << i << " ";
        }
    }
    // 输出 2 3 5 7 11 ... 97

    return 0;
}

2. 子集枚举


// 枚举 {1, 2, 3} 的所有子集
vector nums = {1, 2, 3};
int n = nums.size();

for (int mask = 0; mask < (1 << n); mask++) {
    bitset<3> b(mask);

    cout << "{";
    for (int i = 0; i < n; i++) {
        if (b[i]) {
            cout << nums[i] << " ";
        }
    }
    cout << "}" << endl;
}

// 输出:
// {}
// {1 }
// {2 }
// {1 2 }
// {3 }
// {1 3 }
// {2 3 }
// {1 2 3 }

3. 布尔数组



            4. 位掩码
            
                
// 使用 bitset 作为状态掩码
bitset<8> mask;

// 设置第0位为1
mask |= bitset<8>(1);  // 00000001

// 设置第3位为1
mask |= bitset<8>(8);  // 00001001

// 检查第0位是否为1
if (mask & bitset<8>(1)) {
    cout << "第0位是1" << endl;
}

// 清除第0位
mask &= ~bitset<8>(1);  // 00001000

// 切换第3位
mask ^= bitset<8>(8);  // 00000000



        
            bitset vs vector
            
                
                    
                        特性
                        bitset
                        vector
                    
                
                
                    长度 编译时固定 运行时可变
                    位运算 支持（& | ^ ~） 不支持
                    内存占用 固定 可变
                    性能 更高 稍低
                    适用场景 已知固定长度 未知长度
                
            

            
                选择建议
                
                    长度固定：使用 bitset
                    长度未知/可变：使用 vector
                    需要位运算：使用 bitset
                
            
        

        
            性能对比
            bitset 比 bool 数组快很多，因为：
            
                位压缩：8个bool压缩为1字节
                位操作：CPU原生支持位运算
                缓存友好：占用空间小，缓存命中率高
            

            
                
// 方法1：使用 bool 数组
bool visited[100000];

// 方法2：使用 bitset
bitset<100000> visited_bs;

// 性能测试
for (int i = 0; i < 100000; i++) {
    visited[i] = true;      // 较慢
    visited_bs[i] = true;   // 更快
}

特性	bitset	vector
长度	编译时固定	运行时可变
位运算	支持（& \| ^ ~）	不支持
内存占用	固定	可变
性能	更高	稍低
适用场景	已知固定长度	未知长度