第9.11章: bitvec

概述

::fast_io::bitvec 存放一段动态的位序列，每字节紧凑存放 8 个位。注意 ::fast_io::vector<bool> 每个元素占一个字节（8 位），所以对布尔数据来说 bitvec 在内存上紧凑 8×。

1. 基本用法

#include <fast_io_dsal/bitvec.h>
#include <fast_io.h>

int main() {
    ::fast_io::bitvec bv;

    // Push individual bits
    bv.push_back(true);
    bv.push_back(false);
    bv.push_back(true);

    // Test bits (bounds-checked)
    ::fast_io::io::println("Bit 0: ", bv.test(0zu)); // true
    ::fast_io::io::println("Bit 1: ", bv.test(1zu)); // false

    // Set, reset, flip
    bv.set(1zu);       // Set bit 1 to true
    bv.reset(0zu);     // Set bit 0 to false
    bv.flip(2zu);      // Toggle bit 2

    // Front and back shortcuts
    bv.set_front(true);
    bv.reset_back();
    bool last = bv.pop_back(); // Remove and return the last bit
}

2. 按位运算

::fast_io::bitvec a{true, false, true, true};
::fast_io::bitvec b{true, true, false, true};

// Bitwise AND, OR, XOR
auto c = a & b; // {1, 0, 0, 1}
auto d = a | b; // {1, 1, 1, 1}
auto e = a ^ b; // {0, 1, 1, 0}

// Shifts
auto f = a << 2; // Shift left by 2
auto g = a >> 1; // Shift right by 1

// Complement
auto h = ~a;     // {0, 1, 0, 0}

// In-place compound assignment
a &= b;
a |= b;
a ^= b;
a <<= 3;
a >>= 1;

3. 位检查

::fast_io::bitvec bv{true, false, true, false, false};

bv.popcount();     // 2 (number of set bits)
bv.countl_zero();  // 0 (leading zeros)
bv.countr_zero();  // 0 (trailing zeros)
bv.bit_width();    // 3 (position of highest set bit + 1)
bv.has_single_bit(); // false (not a power of two)
bv.is_all_zero();  // false

// Bulk operations
bv.set_all();   // All bits to 1
bv.reset_all(); // All bits to 0
bv.flip_all();  // Toggle all bits

// Rotation
bv.rotl_assign(2); // Rotate left by 2
bv.rotr_assign(1); // Rotate right by 1

4. 内存效率

要点

• bitvec 存放单个位，每字节紧凑存放 8 个。
• 支持按位运算：&、|、^、<<、>>、~。
• 提供 <bit> 风格的检查：popcount()、countl_zero() 等。
• 对布尔数据而言，比 vector<char> 在内存上紧凑 8×。
• 支持位粒度上的 insert_index() 与 erase_index()。