Phép Toán Bit & Biểu Diễn Trạng Thái

1. Khái niệm & 6 phép toán BIT cơ bản

Máy tính biểu diễn tất cả dữ liệu dưới dạng chuỗi nhị phân (gồm các bit $0$ và $1$). Phép toán bit (Bitwise Operations) là các thao tác tác động trực tiếp lên từng bit của thanh ghi CPU, đạt tốc độ thực thi nhanh nhất trong mọi câu lệnh phần mềm.

1.1. Bảng chân trị của 6 phép toán BIT trong C++

1.2. Các tính chất đại số quan trọng của phép XOR ($\oplus$)

• Tính tự triệt tiêu: $A \oplus A = 0$.
• Phần tử trung hòa: $A \oplus 0 = A$.
• Giao hoán & Kết hợp: $A \oplus B = B \oplus A$ và $(A \oplus B) \oplus C = A \oplus (B \oplus C)$.
• Đổi giá trị 2 biến không cần biến phụ: a ^= b; b ^= a; a ^= b;.

2. 4 thao tác thao tác BIT chuẩn thi đấu

Quy ước đánh số các bit từ phải sang trái, bắt đầu từ bit $0$ (bit có trọng số nhỏ nhất $2^0$).

2.1. Kiểm tra BIT thứ $k$ có đang bật (bằng 1) hay không:

bool is_set = (mask >> k) & 1;

// Hoặc: bool is_set = (mask & (1LL << k)) != 0;

2.2. Bật BIT thứ $k$ (gán thành 1):

mask = mask | (1LL << k);
// Viết gọn: mask |= (1LL << k);

2.3. Tắt BIT thứ $k$ (gán thành 0):

mask = mask & ~(1LL << k);
// Viết gọn: mask &= ~(1LL << k);

2.4. Đảo BIT thứ $k$ ($0 \to 1, 1 \to 0$):

mask = mask ^ (1LL << k);
// Viết gọn: mask ^= (1LL << k);

Ví dụ minh họa 1: Thao tác trên số $N = 13 = 1101_2$

3. Các tuyệt kỹ BIT & hàm nội tại CPU (builtin functions)

3.1. Kiểm tra một số nguyên dương có phải là lũy thừa của 2

Một số $N > 0$ là lũy thừa của 2 ($2^k$) khi và chỉ khi trong biểu diễn nhị phân của nó có đúng duy nhất một bit 1:

bool is_power_of_two = (n > 0) && ((n & (n - 1)) == 0);

3.2. Lấy BIT 1 nhỏ nhất (lowest set BIT / lowbit)

Dùng trong cấu trúc Fenwick Tree và giải thuật bit:

long long lowbit = x & (-x);

3.3. Các hàm nội tại tối ưu hóa phần cứng trong gcc/clang:

• __builtin_popcount(unsigned int x) / __builtin_popcountll(unsigned long long x): Đếm số lượng bit 1 trong $\mathcal{O}(1)$ chu kỳ CPU.
• __builtin_clz(x) / __builtin_clzll(x): Đếm số lượng bit 0 liên tiếp ở đầu (Count Leading Zeros).
• __builtin_ctz(x) / __builtin_ctzll(x): Đếm số lượng bit 0 liên tiếp ở cuối (Count Trailing Zeros).

4. Kỹ thuật mặt nạ BIT (bitmask & subset enumeration)

Mặt nạ bit (Bitmask) là kỹ thuật dùng một số nguyên $N$ bit để biểu diễn một tập hợp con gồm các phần tử được chọn từ tập $N$ phần tử:

• Bit thứ $i = 1 \implies$ Phần tử thứ $i$ được chọn.
• Bit thứ $i = 0 \implies$ Phần tử thứ $i$ không được chọn.

4.1. Duyệt toàn bộ $2^N$ tập con (vét cạn nhị phân):

int n = 4;
for (int mask = 0; mask < (1 << n); ++mask) {
    for (int i = 0; i < n; ++i) {
        if ((mask >> i) & 1) {

            // Phần tử i thuộc tập con hiện tại
        }
    }
}

4.2. Duyệt tất cả tập con (submasks) của một mask trong $\mathcal{O}(3^N)$:

for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {

    // sub là một tập con hợp lệ của mask
}

Ví dụ minh họa 2: Biểu diễn tập con của tập 3 phần tử $S = \{A_0, A_1, A_2\}$

Với $N = 3$, có $2^3 = 8$ mặt nạ bit từ $0$ đến $7$:

5. Mẫu cài đặt chuẩn thi đấu (competitive template)

Mẫu 1: Vét cạn tập con bằng mặt nạ BIT (subset sum)

# include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long target_s;
    if (!(cin >> n >> target_s)) return 0;

    vector<long long> a(n);

    for (int i = 0; i < n; ++i) {
        cin >> a[i];

    }

    bool found = false;
    int total_masks = (1 << n);

    for (int mask = 0; mask < total_masks; ++mask) {
        long long current_sum = 0;
        for (int i = 0; i < n; ++i) {
            if ((mask >> i) & 1) {

                current_sum += a[i];
            }
        }
        if (current_sum == target_s) {
            found = true;
            break;
        }
    }

    cout << (found ? "YES\n" : "NO\n");
    return 0;
}

6. Các bẫy lỗi lập trình kinh điển (bug traps)

1. Bẫy thứ tự ưu tiên toán tử (Operator Precedence Bug): Trong C++, các phép toán bit &, |, ^ có độ ưu tiên thấp hơn các phép toán so sánh ==, !=, <, >. * Lỗi sai: if (mask & (1 << k) != 0) sẽ bị hiểu thành if (mask & ((1 << k) != 0)) $\implies$ Sai kết quả! * Cú pháp chuẩn: if ((mask & (1 << k)) != 0) hoặc if ((mask >> k) & 1).

2. Bẫy tràn số khi dịch bit quá 31: Hằng số 1 mặc định là số nguyên 32-bit có dấu. Biểu thức 1 << 40 sẽ gây tràn số và lỗi hành vi không xác định (Undefined Behavior). * Quy tắc bắt buộc: Luôn viết 1LL << k khi $k \ge 31$.

7. Ranh giới áp dụng: Khi nào nên & không nên dùng?

• KHI NÀO ÁP DỤNG:
• Kích thước tập hợp nhỏ: $N \le 20$ ($2^{20} \approx 10^6$ phép tính) hoặc $N \le 24$ ($2^{24} \approx 1.6 \cdot 10^7$ phép tính).
• Cần tối ưu bộ nhớ trạng thái và tốc độ truy vấn tập hợp $\mathcal{O}(1)$.
• KHI NÀO THẤT BẠI:
• Khi $N \ge 30$ ($2^{30} \approx 10^9$ phép tính $\implies$ TLE). Lúc này bắt buộc phải dùng:
• Chia đôi tập hợp (Meet-in-the-middle) khi $N \le 40$ ($\mathcal{O}(2^{N/2}) = 2^{20} \approx 10^6$).
• Quy hoạch động hoặc Thuật toán Tham lam nếu bài toán có cấu trúc con tối ưu.