Bitset Optimization

Wiki › Cấu trúc dữ liệu

huunguyen · Last updated 8, Tháng 4, 2026, 16:12

Bitset là cấu trúc dữ liệu lưu mảng bit, cho phép thực hiện các phép toán bitwise trên $N$ bit trong $O (N / 64)$ — tăng tốc nhiều thuật toán từ $O (N^{2})$ lên $O (N^{2} / 64)$ .

Cơ bản

#include <bitset>
const int MAXN = 1000;
bitset<MAXN> a, b, c;

a.set(5);       // đặt bit 5 = 1
a.reset(5);     // xóa bit 5
a.flip(5);      // đảo bit 5
a[5];           // đọc bit 5
a.count();      // đếm số bit 1
a.any();        // có bit nào = 1 không
a.none();       // tất cả = 0?
a.size();       // kích thước (= MAXN)

c = a & b;      // AND
c = a | b;      // OR
c = a ^ b;      // XOR
c = a << k;     // shift trái k bit
c = a >> k;     // shift phải k bit

Ứng dụng 1: Subset DP — $O (2^{N} \cdot N / 64)$

Kiểm tra tập các số nguyên có thể tạo ra từ tập con:

// Đếm số giá trị tổng có thể đạt được từ tập {a[0],...,a[n-1]}
// (mỗi phần tử dùng tối đa 1 lần), tổng <= MAXSUM
const int MAXSUM = 1e5;
bitset<MAXSUM+1> dp;
dp[0] = 1;
for (int x : a)
    dp |= (dp << x);
// dp[s] = 1 nếu có thể đạt tổng s
cout << dp.count();   // số tổng khác nhau có thể đạt được

Ứng dụng 2: Shortest Path — Bitset BFS

BFS trên đồ thị dày với $N \leq 10^{4}$ :

const int N = 1000;
bitset<N> adj[N];   // adj[u] = tập đỉnh kề của u

vector<int> bfs(int src) {
    vector<int> dist(N, -1);
    bitset<N> visited, frontier;
    visited[src] = frontier[src] = 1;
    dist[src] = 0;

    while (frontier.any()) {
        bitset<N> next;
        for (int u = frontier._Find_first(); u < N; u = frontier._Find_next(u))
            next |= adj[u];
        next &= ~visited;
        visited |= next;
        frontier = next;
        for (int u = next._Find_first(); u < N; u = next._Find_next(u))
            dist[u] = dist[/* prev */ 0] + 1;   // cần track thêm
    }
    return dist;
}

Ứng dụng 3: Matrix Multiplication — $O (N^{3} / 64)$

Nhân ma trận boolean:

const int N = 1000;
bitset<N> A[N], B[N], C[N];

void mat_mul_bool() {
    // B^T để cache-friendly
    bitset<N> BT[N];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (B[i][j]) BT[j][i] = 1;

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            C[i][j] = (A[i] & BT[j]).any();
}

Ứng dụng 4: Bipartite Matching — $O (N M / 64)$

Hopcroft-Karp với bitset tăng tốc augmenting path:

// adj[u] là bitset các đỉnh bên phải kề với u
// Tìm matching bằng cách duyệt augmenting paths hiệu quả hơn

Ứng dụng 5: Knapsack — $O (N W / 64)$

// 0/1 Knapsack: có thể đạt trọng lượng nào?
const int W = 1e6;
bitset<W+1> dp;
dp[0] = 1;
for (int i = 0; i < n; i++)
    dp |= (dp << w[i]);
// dp[w] = 1 nếu có subset có tổng trọng lượng = w

Ứng dụng 6: Đếm tam giác trong đồ thị — $O (N^{3} / 64)$

long long count_triangles(int n, bitset<N> adj[]) {
    long long cnt = 0;
    for (int u = 0; u < n; u++)
        for (int v = u+1; v < n; v++)
            if (adj[u][v])
                cnt += (adj[u] & adj[v]).count();
    return cnt / 3;
}

`_Find_first()` và `_Find_next()`

GCC extension để duyệt các bit 1 hiệu quả:

bitset<N> bs;
for (int i = bs._Find_first(); i < N; i = bs._Find_next(i)) {
    // xử lý bit i
}

Lưu ý: _Find_first() và _Find_next() là GCC extension, không có trong C++ chuẩn.

Kích thước phải là compile-time constant

// KHÔNG được:
int n; cin >> n;
bitset<n> bs;   // lỗi: n không phải hằng số lúc biên dịch

// Phải dùng:
const int MAXN = 1e5;
bitset<MAXN> bs;

Độ phức tạp

Thao tác	Không bitset	Dùng bitset
Knapsack $O (N W)$	$O (N W)$	$O (N W / 64)$
Nhân ma trận boolean $N \times N$	$O (N^{3})$	$O (N^{3} / 64)$
BFS đồ thị dày	$O (N^{2})$	$O (N^{2} / 64)$
Subset sum tồn tại	$O (N W)$	$O (N W / 64)$

Khi nào dùng Bitset?

Bài toán bitwise trên tập hợp lớn.
Knapsack với $W$ lớn nhưng $N W / 64$ vừa.
Đồ thị dày $N \leq 5000$ cần BFS/nhân ma trận.
Tăng tốc hằng số 64x cho thuật toán $O (N^{2})$ hoặc $O (N^{3})$ .

Bình luận

Không có bình luận tại thời điểm này.