位图（概念）

LXdian_LX

922人浏览 · 2025-09-01 15:42:53

LXdian_LX · 2025-09-01 15:42:53 发布

位图（概念）

第一部分：什么是位图？

核心概念：位图（Bitmap），在C++上下文中通常指的是 std::bitset，它是一种固定大小的、专门用于存储二进制位（0和1）的容器。每个位（bit）可以代表一个状态标志（例如，真/假、是/否、存在/不存在），从而极大地节省内存空间。

关键优势：极致的空间效率。

存储一个布尔值（boolean），使用 bool 类型通常需要至少 1 个字节（8位）。
而使用 std::bitset，一个布尔值只占 1 位。
对比：存储 1000 个状态：
- bool array[1000]：大约消耗 1000 字节。
- std::bitset<1000>：大约消耗 125 字节 (1000 / 8)。

第二部分：C++标准库中的位图 - `std::bitset`

std::bitset 是一个模板类，定义在 <bitset> 头文件中。它的大小在编译时确定，并作为模板参数传入。

1. 包含头文件和基本定义

#include <iostream>
#include <bitset> // 必须包含的头文件
#include <string>

using namespace std;

int main() {
    // 定义一个大小为 8 位的位图，所有位初始化为 0
    bitset<8> b1; 

    // 用一个 unsigned long long 值初始化位图
    // 十进制 10 的二进制是 00001010
    bitset<8> b2(10); // b2: 00001010

    // 用字符串初始化位图
    // 注意：字符串只能包含 '0' 和 '1'
    bitset<8> b3("10101010"); // b3: 10101010
    bitset<8> b4("11110000", 4); // 使用前4个字符 "1111"，所以是 00001111

    return 0;
}

2. 核心成员函数和操作

位图的操作非常丰富，我们分类讲解。

a. 位设置/重置/翻转

bitset<8> bs; // bs: 00000000

// set()：设置位（变为1）
bs.set();      // 所有位设置为1: 11111111
bs.set(3);     // 将第3位（从0开始）设置为1: 00001000
bs.set(3, 0);  // 将第3位设置为0: 00000000 (等效于 reset(3))

// reset()：重置位（变为0）
bs.set();      // 先全设为1: 11111111
bs.reset();    // 所有位重置为0: 00000000
bs.reset(3);   // 将第3位重置为0: 11110111 (如果原来是1)

// flip()：翻转位（0变1，1变0）
bs = bitset<8>(0b01010101); // 用二进制字面量(C++14)初始化: 01010101
bs.flip();     // 所有位翻转: 10101010
bs.flip(3);    // 翻转第3位: 如果原来是0，变为1: 01010101 -> 01011101

// 使用 [] 操作符访问和修改特定位
// 注意：[] 操作符返回的是一个特殊的“代理”类型，但可以像引用一样使用
bs[5] = 1;     // 将第5位设置为1
bool bit = bs[2]; // 获取第2位的值
bs[4].flip();  // 翻转第4位

b. 访问和测试位

bitset<8> bs(0b00001010); // 00001010

// test(pos): 检查第pos位是否为1，会进行越界检查
if (bs.test(3)) { // 第3位是1吗？ 是的
    cout << "Bit 3 is set!" << endl;
}

// operator[]: 访问位，不进行越界检查（更快）
if (bs[1]) { // 第1位是1吗？ 是的 (00001010，从右往左数，第1位是1)
    cout << "Bit 1 is set!" << endl;
}

// all(): 检查是否所有位都是1
cout << "All bits set? " << bs.all() << endl; // false

// any(): 检查是否有任何位是1
cout << "Any bit set? " << bs.any() << endl; // true

// none(): 检查是否没有位是1（全0）
cout << "No bits set? " << bs.none() << endl; // false

// count(): 返回被设置为1的位的个数
cout << "Number of 1s: " << bs.count() << endl; // 2

// size(): 返回位图的总大小（位数）
cout << "Size of bitset: " << bs.size() << endl; // 8

c. 类型转换

bitset<8> bs(0b11001100);

// to_string(): 转换为字符串
string s = bs.to_string(); // "11001100"
// 可以传入字符，定制输出
s = bs.to_string('O', 'X'); // "XXOOXXOO"

// to_ulong() / to_ullong(): 转换为无符号长整型
// 注意：转换的值必须在目标类型的表示范围内
unsigned long num = bs.to_ulong(); // 204
cout << "As unsigned long: " << num << endl;

3. 位运算

std::bitset 重载了所有主要的位运算符，使得操作非常方便，就像操作一个整数一样。

bitset<8> a("00001111");
bitset<8> b("01010101");

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

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

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

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

// 左移 << (空位补0)
c = a << 2; // 00111100
cout << "a << 2 = " << c << endl;

// 右移 >> (空位补0)
c = a >> 2; // 00000011
cout << "a >> 2 = " << c << endl;

// 复合赋值运算符同样支持
a ^= b; // a 现在等于 a ^ b
b <<= 3; // b 左移3位

4. 输入输出流操作

std::bitset 重载了 << 和 >> 操作符，方便进行 I/O 操作。

bitset<8> bs;

// 从输入流读取
cout << "Please enter an 8-bit binary number (e.g., 10101010): ";
cin >> bs; // 会一直读取，直到遇到非 '0'/'1' 字符，或者读满 size() 个字符
cout << "You entered: " << bs << endl;

// 输出到流
cout << "As a string: " << bs.to_string() << endl;

第三部分：实际应用场景

应用1：状态标志系统

替代一堆 bool 变量或者枚举，管理一组开关状态。

class ProcessPermissions {
private:
    bitset<4> flags; // 用4位表示4种权限

public:
    enum Permission {
        Read = 0,   // 第0位
        Write = 1,  // 第1位
        Execute = 2,// 第2位
        Delete = 3  // 第3位
    };

    void grant(Permission p) { flags.set(p); }
    void revoke(Permission p) { flags.reset(p); }
    bool check(Permission p) const { return flags.test(p); }
    void toggle(Permission p) { flags.flip(p); }

    void showPermissions() {
        cout << "Read: " << check(Read) << ", ";
        cout << "Write: " << check(Write) << ", ";
        cout << "Execute: " << check(Execute) << ", ";
        cout << "Delete: " << check(Delete) << endl;
    }
};

int main() {
    ProcessPermissions proc;
    proc.grant(ProcessPermissions::Read);
    proc.grant(ProcessPermissions::Execute);
    proc.showPermissions(); // Read: 1, Write: 0, Execute: 1, Delete: 0

    proc.toggle(ProcessPermissions::Write);
    proc.showPermissions(); // Read: 1, Write: 1, Execute: 1, Delete: 0
    return 0;
}

应用2：埃拉托斯特尼筛法（素数筛）

这是一个经典的算法，用于快速查找所有小于给定数的素数。位图在这里用于高效标记数字是否为合数。

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

const size_t MAX_NUMBER = 1000000;

void findPrimes(int n) {
    if (n > MAX_NUMBER) {
        cerr << "n is too large!" << endl;
        return;
    }

    bitset<MAX_NUMBER+1> isPrime;
    isPrime.set(); // 假设所有数都是素数

    isPrime[0] = isPrime[1] = 0; // 0和1不是素数

    // 筛法核心
    for (size_t i = 2; i <= sqrt(n); ++i) {
        if (isPrime[i]) {
            // 如果i是素数，标记i的所有倍数为非素数
            for (size_t j = i * i; j <= n; j += i) {
                isPrime[j] = 0;
            }
        }
    }

    // 输出所有素数
    cout << "Primes up to " << n << ":\n";
    for (size_t i = 2; i <= n; ++i) {
        if (isPrime[i]) {
            cout << i << " ";
        }
    }
    cout << endl;
}

int main() {
    findPrimes(100);
    return 0;
}

应用3：简单的布隆过滤器（Bloom Filter）概念演示

布隆过滤器是一种概率型数据结构，用于快速判断一个元素绝对不在一个集合中，或者可能在其中。它使用多个哈希函数和一个大位图。

#include <iostream>
#include <bitset>
#include <functional> // for std::hash
using namespace std;

const size_t BLOOM_FILTER_SIZE = 1000;

class SimpleBloomFilter {
private:
    bitset<BLOOM_FILTER_SIZE> filter;

    // 使用两个不同的哈希函数（这里用简单的取模模拟）
    size_t hash1(const string& key) const {
        hash<string> hasher;
        return hasher(key) % BLOOM_FILTER_SIZE;
    }

    size_t hash2(const string& key) const {
        // 一个简单的第二哈希函数，通常应该更复杂
        size_t h = 0;
        for (char c : key) {
            h = (h * 31 + c) % BLOOM_FILTER_SIZE;
        }
        return h;
    }

public:
    void add(const string& key) {
        size_t pos1 = hash1(key);
        size_t pos2 = hash2(key);
        filter.set(pos1);
        filter.set(pos2);
        cout << "Adding '" << key << "', setting bits " << pos1 << " and " << pos2 << endl;
    }

    bool possiblyContains(const string& key) const {
        size_t pos1 = hash1(key);
        size_t pos2 = hash2(key);
        return (filter.test(pos1) && filter.test(pos2));
    }
};

int main() {
    SimpleBloomFilter bf;

    bf.add("hello");
    bf.add("world");

    cout << "Contains 'hello'? " << bf.possiblyContains("hello") << endl; // True
    cout << "Contains 'world'? " << bf.possiblyContains("world") << endl; // True
    cout << "Contains 'foo'? " << bf.possiblyContains("foo") << endl;     // False (可能碰巧为True，这是布隆过滤器的特点)

    return 0;
}

注意：这是一个极度简化的演示，真实的布隆过滤器需要使用更多、质量更高的哈希函数。

第四部分：`std::bitset` 的局限性及替代方案

固定大小：最大的局限性。大小必须在编译时确定。如果你需要一个运行时决定大小的位图，std::bitset 无法满足。
替代方案：
- std::vector<bool>： C++标准库提供了一个对 bool 类型特化的 vector。它内部也使用位存储来节省空间。它是动态大小的。
```
#include <vector>
vector<bool> vb(1000); // 一个动态的、包含1000个布尔值的“位图”
vb[345] = true;
```
  注意：vector<bool> 存在争议，因为它不满足标准容器的所有要求（例如，返回的不是真正的 bool& 引用）。在需要通用容器行为时需谨慎使用。
- boost::dynamic_bitset：来自 Boost 库，提供了 std::bitset 的所有功能，并且大小可以在运行时动态改变。这是最强大的替代方案。
```
#include <boost/dynamic_bitset.hpp>
boost::dynamic_bitset<> dyn_bs(100); // 初始100位
dyn_bs.resize(200); // 调整为200位
```

总结

特性	`std::bitset<N>`	`std::vector<bool>`	`boost::dynamic_bitset<>`
大小	编译时固定	运行时可变	运行时可变
性能	非常高	高	高
功能	丰富	基本（类似vector）	非常丰富（类似bitset）
方便性	需要知道N	动态调整，方便	动态调整，非常方便
标准性	C++标准	C++标准（但有争议）	需要Boost库