Chương trình C++ triển khai Bit Array

Bit Array (mảng bit) là cấu trúc dữ liệu nén lưu trữ từng bit riêng lẻ, tiết kiệm bộ nhớ cực đại. Mỗi phần tử chỉ chiếm 1 bit thay vì 1 byte (char) hoặc 4 byte (int).

Ý tưởng triển khai

• Dùng mảng các unsigned int hoặc uint64_t làm storage.
• Bit thứ i nằm trong word i / WORD_BITS, vị trí i % WORD_BITS.
• Thao tác: get (đọc bit), set (ghi bit), toggle, clear.

Ví dụ mã: Bit Array 4 bit đơn giản

#include <iostream>
#include <cstdint>
using namespace std;

class BitArray {
    static const int BITS = 4;
    uint8_t storage = 0; // 1 byte = 8 bits, dùng 4 bit thấp

public:
    // Lấy bit tại vị trí pos (0-index từ LSB)
    bool getBit(int pos) const {
        return (storage >> pos) & 1;
    }

    // Đặt bit tại pos thành value (0/1)
    void setBit(int pos, bool value) {
        if (value)
            storage |= (1 << pos);   // set bit
        else
            storage &= ~(1 << pos); // clear bit
    }

    // Giá trị nguyên của toàn bộ bit array
    int getValue() const {
        return storage;
    }
};

int main() {
    BitArray ba;
    int val;
    cout << "Nhập giá trị 4-bit (0-15): ";
    cin >> val;

    // Lưu từng bit
    for (int i = 0; i < 4; ++i)
        ba.setBit(i, (val >> i) & 1);

    cout << "Các bit (LSB first): ";
    for (int i = 0; i < 4; ++i)
        cout << ba.getBit(i) << ' ';
    cout << "\nGiá trị khôi phục: " << ba.getValue() << endl;

    return 0;
}

Kết quả mẫu

Nhập giá trị 4-bit (0-15): 6
Các bit (LSB first): 0 1 1 0
Giá trị khôi phục: 6

Ứng dụng thực tế: Bloom filter, bitmap ảnh, bộ lọc bit, nén dữ liệu, bitset flags. C++ STL có std::bitset<N> (kích thước compile-time) và std::vector<bool> (đặc hóa nén bit).