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

Bitset Optimization

huunguyen Updated Tháng sáu 2, 2026

Bitset là cấu trúc dữ liệu lưu một mảng $N$ bit dưới dạng đóng gói (mỗi máy 64 bit lưu 64 phần tử trong một word). Nhờ vậy mọi phép toán theo bit — AND, OR, XOR, NOT, dịch bit, đếm bit — chạy trên cả $N$ phần tử cùng lúc theo từng word, tốn $O (N / 64)$ thay vì $O (N)$ . Đây là kỹ thuật tối ưu hằng số 64 lần: nó không đổi độ phức tạp tiệm cận về mặt lý thuyết, nhưng biến một thuật toán $O (N^{2})$ hay $O (N^{3})$ "suýt TLE" thành $O (N^{2} / 64)$ hay $O (N^{3} / 64)$ đủ nhanh để qua bài. Các ứng dụng kinh điển: kiểm tra tổng con đạt được (subset-sum reachability), bao đóng bắc cầu trên đồ thị, nhân ma trận boolean, đếm tam giác trong đồ thị dày.

Ý tưởng / Trực giác

Câu hỏi cốt lõi: vì sao lại nhanh hơn 64 lần?

CPU 64-bit xử lý một lệnh AND/OR/XOR trên hai thanh ghi 64 bit trong một chu kỳ, bất kể 64 bit đó mang ý nghĩa gì. Nếu ta nhồi 64 giá trị boolean của bài toán vào một word, thì một lệnh máy duy nhất đã làm xong 64 phép toán logic của bài toán. Trình biên dịch trải bitset<N> thành $⌈ N / 64 ⌉$ word liên tiếp, nên một phép a & b trên bitset<N> chỉ là một vòng lặp $⌈ N / 64 ⌉$ lệnh máy — đó chính là hệ số $1 / 64$ .

Hai "phép thuật" hay dùng nhất:

Dịch bit = tịnh tiến tập hợp. Nếu bit $s$ của dp đánh dấu "tổng $s$ đạt được", thì dp << x đẩy mọi tổng $s$ thành $s + x$ . Vậy dp |= dp << x nghĩa là: "giữ mọi tổng cũ, đồng thời thêm tuỳ chọn cộng $x$ vào mỗi tổng cũ" — chính là bước chuyển của DP tổng con, nhưng làm cho tất cả các tổng trong một lệnh.
AND/OR/đếm trên tập đỉnh. Nếu reach[u] là bitset các đỉnh đến được từ $u$ , thì gộp các tập con của những đỉnh kề chỉ là reach[u] |= reach[v]. Đây là cách tính bao đóng bắc cầu (transitive closure) cực gọn.

Điều kiện để bitset ăn tiền: đối tượng phải đánh chỉ số được thành 0..N-1 (tổng tiền, đỉnh đồ thị, chỉ số cột...) và phép cập nhật phải diễn đạt được bằng AND/OR/XOR/shift. Khi đó bài toán "song song hoá theo bit" được.

Ví dụ chạy tay: tổng con đạt được

Xét tập đồng xu ${1, 3, 2}$ , ta muốn biết những tổng nào tạo được. Dùng dp với bit $s = 1$ nghĩa là "tổng $s$ đạt được". Khởi tạo dp = ...0001 (chỉ tổng $0$ đạt được). Bit viết từ phải (bit 0) sang trái:

chỉ số bit:        7 6 5 4 3 2 1 0
dp ban đầu:        0 0 0 0 0 0 0 1     (chỉ tổng 0)

Thêm xu $x = 1$ : tính dp << 1 rồi OR vào dp.

dp        =        0 0 0 0 0 0 0 1
dp << 1   =        0 0 0 0 0 0 1 0     (tổng 0 -> 1)
dp |= ... =        0 0 0 0 0 0 1 1     (đạt {0,1})
                                ^ ^

Thêm xu $x = 3$ : dp << 3 đẩy mỗi tổng lên thêm 3.

dp        =        0 0 0 0 0 0 1 1     ({0,1})
dp << 3   =        0 0 0 1 1 0 0 0     ({3,4})
dp |= ... =        0 0 0 1 1 0 1 1     ({0,1,3,4})
                         ^ ^   ^ ^

Thêm xu $x = 2$ : dp << 2.

dp        =        0 0 0 1 1 0 1 1     ({0,1,3,4})
dp << 2   =        0 1 1 0 1 1 0 0     ({2,3,5,6})
dp |= ... =        0 1 1 1 1 1 1 1     ({0,1,2,3,4,5,6})
                     ^ ^ ^ ^ ^ ^ ^

Kết quả: mọi tổng từ $0$ đến $6$ đều đạt được. Bỏ bit $0$ đi, các tổng dương tạo được là ${1, 2, 3, 4, 5, 6}$ , đếm bằng dp.count() - 1 = 6. Mỗi xu chỉ tốn một phép << và một phép |= trên toàn bộ bitset, tức $O (MAXSUM / 64)$ cho mỗi xu.

Cài đặt

Các thao tác 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 (về 0)
a.flip(5);      // đảo bit 5
a[5] = 1;       // gán trực tiếp; a[5] đọc giá trị bit 5
a.count();      // đếm số bit 1  (popcount toàn bộ)
a.any();        // có bit nào = 1 không?
a.none();       // tất cả = 0?
a.all();        // tất cả = 1?
a.size();       // kích thước cố định (= MAXN)

c = a & b;      // AND theo bit
c = a | b;      // OR
c = a ^ b;      // XOR
c = ~a;         // NOT (đảo mọi bit)
c = a << k;     // dịch trái k bit (mỗi tổng +k)
c = a >> k;     // dịch phải k bit

Ứng dụng 1: Subset-sum / Knapsack feasibility — $O (N W / 64)$

// Đếm các tổng tạo được từ tập {a[0..n-1]}, mỗi phần tử dùng <= 1 lần.
const int MAXSUM = 100000;
bitset<MAXSUM + 1> dp;
dp[0] = 1;                       // tổng 0 luôn đạt được (chọn rỗng)
for (int x : a)
    dp |= (dp << x);             // thêm tuỳ chọn cộng x vào MỌI tổng cũ
// dp[s] == 1  <=>  tổng s đạt được
cout << dp.count() - 1;          // số tổng DƯƠNG khác nhau (bỏ tổng 0)

Lưu ý thứ tự: vì ta xử lý từng phần tử với một bitset duy nhất theo chiều dp |= dp << x, mỗi phần tử tự động chỉ được cộng một lần (khác với knapsack không giới hạn). Không cần lặp ngược như DP mảng vì phép dịch tạo bản sao tức thời.

Ứng dụng 2: Bao đóng bắc cầu trên DAG — $O (n \cdot m / 64)$

// reach[u] = tập đỉnh đến được từ u (kể cả u). Duyệt theo thứ tự topo ĐẢO.
const int N = 50005;
vector<int> g[N];
bitset<N> reach[N];

void solve(int n, vector<int>& topo) {  // topo: thứ tự topo xuôi
    for (int i = n - 1; i >= 0; --i) {   // xử lý đỉnh "sau" trước
        int u = topo[i];
        reach[u][u] = 1;                 // u đến được chính nó
        for (int v : g[u])
            reach[u] |= reach[v];        // gộp tập đến được của các đỉnh kề
    }
    for (int u = 0; u < n; ++u)
        cout << reach[u].count() << ' '; // số đỉnh đến được từ u
}

Ứng dụng 3: Nhân ma trận boolean — $O (N^{3} / 64)$

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

void mat_mul_bool() {
    bitset<N> BT[N];                     // chuyển vị B để truy cập theo HÀNG
    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();  // C[i][j] = OR_k (A[i][k] & B[k][j])
}

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

const int N = 1000;
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();  // số đỉnh w kề CẢ u và v
    return cnt / 3;                                // mỗi tam giác đếm 3 lần
}

Duyệt các bit 1 nhanh: `_Find_first` / `_Find_next`

GCC cung cấp hai hàm phi chuẩn để nhảy thẳng tới bit 1 tiếp theo (dùng lệnh đếm số 0 đầu word), giúp duyệt mọi bit 1 trong $O (N / 64 + số bit 1)$ thay vì quét từng bit:

bitset<N> bs;
for (int i = bs._Find_first(); i < (int)bs.size(); i = bs._Find_next(i)) {
    // xử lý bit i đang bật
}

Ví dụ BFS trên đồ thị dày, frontier là một bitset:

bitset<N> visited, frontier;
visited[src] = frontier[src] = 1;
while (frontier.any()) {
    bitset<N> nxt;
    for (int u = frontier._Find_first(); u < N; u = frontier._Find_next(u))
        nxt |= adj[u];          // gộp hàng xóm của mọi đỉnh trong frontier
    nxt &= ~visited;            // bỏ đỉnh đã thăm
    visited |= nxt;
    frontier = nxt;             // lớp BFS kế tiếp
}

Độ phức tạp

Đặt $w = 64$ (số bit mỗi word). Một bitset<N> chiếm $⌈ N / w ⌉$ word.

Thao tác	Thời gian	Vì sao
`&`, `\|`, `^`, `~`, `<<k`, `>>k`	$O (N / w)$	mỗi word một lệnh máy, có $⌈ N / w ⌉$ word
`count()`, `any()`, `none()`	$O (N / w)$	popcount/so sánh từng word
`_Find_first/next`	$O (N / w)$ xấu nhất	quét word rỗng rồi đếm số 0 đầu word tìm thấy
set/reset/flip/đọc một bit	$O (1)$	chỉ chạm đúng một word

Áp vào các thuật toán:

Bài toán	Không bitset	Dùng bitset
Subset-sum tới $W$ , $N$ phần tử	$O (N W)$	$O (N W / 64)$
Bao đóng bắc cầu ( $n$ đỉnh, $m$ cạnh)	$O (n m)$	$O (n m / 64)$
Nhân ma trận boolean $N \times N$	$O (N^{3})$	$O (N^{3} / 64)$
Đếm tam giác đồ thị dày	$O (N^{3})$	$O (N^{3} / 64)$
BFS đồ thị dày	$O (N^{2})$	$O (N^{2} / 64)$

Bộ nhớ: một bitset<N> tốn $N / 8$ byte. Đây là điểm dễ chết: lưu một mảng bitset<N> r[N] (như bao đóng bắc cầu) tốn $N^{2} / 8$ byte. Với $N = 50000$ thì $N^{2} / 8 \approx 3.1 \times 10^{8}$ byte $\approx 312$ MB — vượt giới hạn bộ nhớ thông thường. Khi đó phải xử lý theo nhóm đỉnh (chia $N$ thành các khối, mỗi khối một lượt) hoặc nén SCC trước để giảm số đỉnh, chứ không thể giữ đồng thời $N$ bitset cỡ $N$ .

Hệ số $1 / 64$ là hằng số, không đổi cấp độ tiệm cận: $O (N^{2} / 64)$ vẫn là $O (N^{2})$ về lý thuyết. Bitset chỉ hữu ích khi $N$ đủ nhỏ để $N^{2} / 64$ hay $N^{3} / 64$ lọt giới hạn thời gian (thường $N \leq 5000$ cho $O (N^{3} / 64)$ , $N \leq 10^{5}$ cho $O (N^{2} / 64)$ ).

⚠️ Lỗi thường gặp

Kích thước phải là hằng số biên dịch (compile-time constant). bitset<n> với n đọc từ input sẽ không biên dịch được. Phải khai báo const int MAXN = 1e5; bitset<MAXN> bs; cho cỡ tối đa rồi chỉ dùng phần đầu.
```
int n; cin >> n;
bitset<n> bad;        // LỖI biên dịch: n không phải hằng số
bitset<MAXN> good;    // ĐÚNG: cỡ cố định, dùng n bit đầu
```
Tràn bộ nhớ với mảng bitset lớn. bitset<50000> r[50000] $\approx 312$ MB — MLE ngay. Luôn nhân thử $N \times N / 8$ byte trước khi khai báo. Nếu vượt, chia khối hoặc nén SCC.
Dịch trái làm "tràn" mất bit cao. dp << x đẩy các bit vượt quá chỉ số $N - 1$ biến mất lặng lẽ (không cảnh báo). Nếu tổng có thể đạt tới $W$ , bitset phải có kích thước $\geq W + 1$ ; khai báo thiếu sẽ ra kết quả sai mà không lỗi runtime.
Quên bit tổng 0 hoặc đếm thừa. Trong subset-sum, dp[0] = 1 ban đầu là tổng rỗng. Nếu đề hỏi "các tổng dương" thì kết quả là dp.count() - 1; quên trừ 1 là sai. Ngược lại nếu cần cả tổng 0 thì đừng trừ.
_Find_first / _Find_next là extension của GCC, không có trong C++ chuẩn và không tồn tại trên MSVC. Dùng trên trình chấm khác GCC sẽ lỗi biên dịch — khi đó tự duyệt từng word hoặc dùng __builtin_ctzll.
Nhầm << của bitset với dịch số nguyên. a << k trên bitset trả về một bitset mới (không sửa a); muốn cập nhật tại chỗ phải viết a <<= k hoặc a = a << k. Viết a << k; rồi tưởng a đã đổi là một lỗi âm thầm.
Trộn kiểu khi gán từ bit. a[i] trả về một proxy reference, không phải bool thuần. Gán int x = a[i]; thì ổn, nhưng truyền a[i] vào template suy luận kiểu có thể ra bitset::reference thay vì bool, gây lỗi khó hiểu; ép bool(a[i]) khi cần.

Biến thể / Mở rộng

Knapsack đếm số cách không dùng bitset trực tiếp được, vì OR chỉ trả lời "có/không", không cộng số cách. Khi đề hỏi đếm (thường kèm modulo) phải quay lại DP mảng số nguyên; bitset chỉ giải bài tồn tại / liệt kê tổng.
Reachability trên đồ thị có chu trình: nén thành phần liên thông mạnh (SCC) thành DAG trước, rồi chạy bao đóng bằng bitset trên DAG — giảm số đỉnh và đảm bảo thứ tự topo. Xem thêm Quy hoạch động trên đồ thị.
LCS / so khớp chuỗi bit-song song (thuật toán Myers, Hunt–Szymanski): dùng bitset biểu diễn cột bảng DP để tính khoảng cách chỉnh sửa trong $O (N M / 64)$ — biến thể nâng cao của ý tưởng "dịch bit = tịnh tiến".

Bài tập luyện

Các Tổng Tiền (moneysums) — (Trung cấp) Bài nhập môn kinh điển: liệt kê mọi tổng con đạt được bằng đúng một dòng dp |= dp << x.
Những Ngọn Núi (mountain) — (Kỳ cựu) Đếm cặp đỉnh "nhìn thấy nhau" sau mỗi cập nhật; tăng tốc kiểm tra cản tầm nhìn theo cặp bằng bitset, $O (N^{2} Q / 64)$ .
Đếm đỉnh có thể đến được (reachnode) — (Chuyên gia) Bao đóng bắc cầu trên DAG: mỗi đỉnh giữ một bitset các đỉnh đến được, gộp bằng |=; chú ý chia khối để không MLE.
Truy vấn khả năng đến được (reachqry) — (Chuyên gia) Nén SCC thành DAG rồi tính reachability bằng bitset để trả lời nhiều truy vấn $a \to b$ trong $O (n m / 64)$ .