Ch9.11: bitvec

Overview

A ::fast_io::bitvec stores a dynamic sequence of individual bits, packed 8 per byte. Note that ::fast_io::vector<bool> stores one byte per element (8 bits), so bitvec is 8× more memory-efficient for boolean data.

1. Basic Usage

#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. Bitwise Operations

::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. Bit Inspection

::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. Memory Efficiency

Key takeaways

• bitvec stores individual bits, packed 8 per byte.
• Supports bitwise operations: &, |, ^, <<, >>, ~.
• Provides <bit>-style inspection: popcount(), countl_zero(), etc.
• 8× more memory-efficient than vector<char> for boolean data.
• Supports insert_index() and erase_index() at bit-level granularity.