Giao diện
Bit Manipulation ⚡
Mỗi phép toán bitwise hoàn thành trong đúng một chu kỳ CPU. Không allocation, không branch prediction miss, không cache miss — chỉ là logic gate thuần túy trên silicon. Đó là lý do Linux kernel dùng bitmask cho quyền truy cập file, TCP/IP dùng XOR cho checksum, và RSA dùng lũy thừa modular cho mọi kết nối HTTPS trên hành tinh.
Nắm vững Bit Manipulation không chỉ giúp bạn giải nhanh hơn trong competitive programming — nó thay đổi cách bạn tư duy về dữ liệu. Khi hiểu rằng một số nguyên 64-bit có thể biểu diễn bất kỳ tập con nào của 64 phần tử, bạn mở ra một thế giới thuật toán mà mảng boolean không bao giờ chạm tới được.
Lộ trình học
Chủ đề Bit Manipulation được chia thành 3 bài học theo thứ tự từ nền tảng đến nâng cao. Bạn nên bắt đầu từ Bitmasking vì đây là bài xây dựng trực giác về cách biểu diễn tập hợp bằng bit, sau đó đến XOR Tricks để khám phá sức mạnh của phép XOR, và cuối cùng là Lũy thừa nhanh — nơi bit manipulation gặp đại số tuyến tính và mật mã học.
Bitmasking ──→ XOR Tricks ──→ Lũy thừa nhanh
(nén tập hợp, (tính chất đối xứng, (nhân nhanh, ma trận,
liệt kê, tìm phần tử, Fibonacci O(log n),
DP bitmask) GF(2) basis) RSA, modular inverse)Nội dung
Bitmasking — Nghệ thuật nén tập hợp vào số nguyên
Biến một số nguyên thành tập hợp, liệt kê mọi tập con trong O(2ⁿ), Gosper's hack cho tổ hợp C(n,k), và ứng dụng kinh điển trong Bitmask DP (TSP, phân công công việc). Kèm theo hệ thống phân quyền bitwise kiểu Unix.
Độ khó: Intermediate · Thời gian: ~35 phút
XOR Tricks — Phép toán đối xứng và ứng dụng
Bốn tính chất đại số của XOR, bài toán tìm phần tử xuất hiện 1 lần / thiếu / trùng trong O(n) O(1) space, XOR của dãy [0..n] trong O(1), và chuyên sâu XOR Basis — đại số tuyến tính trên trường GF(2).
Độ khó: Intermediate · Thời gian: ~35 phút
Lũy thừa nhanh — Từ O(n) xuống O(log n)
Binary exponentiation cho a^b mod m, lũy thừa ma trận tính Fibonacci thứ 10¹⁸, nghịch đảo modular bằng Fermat, tổ hợp C(n,k) mod p, và demo RSA encryption. Thuật toán đứng sau mọi kết nối HTTPS.
Độ khó: Intermediate · Thời gian: ~35 phút
Bảng tra nhanh
| Phép toán | Code | Ứng dụng |
|---|---|---|
| Kiểm tra bit i | (n >> i) & 1 | Feature flag đang bật? |
| Bật bit i | n | (1 << i) | Kích hoạt tính năng |
| Tắt bit i | n & ~(1 << i) | Vô hiệu hóa tính năng |
| Đảo bit i | n ^ (1 << i) | Toggle trạng thái |
| Bit 1 thấp nhất | n & (-n) | Fenwick Tree, LSB |
| Xóa bit 1 thấp nhất | n & (n - 1) | Đếm bit, kiểm tra lũy thừa 2 |
| Kiểm tra lũy thừa 2 | n > 0 && (n & (n-1)) == 0 | Memory alignment |
| Mask n bit 1 | (1 << n) - 1 | Tạo bitmask |
🧠 Quiz
Câu 1: Phép toán nào dùng để tắt (clear) bit thứ k trong số n?
- [ ] A) n | (1 << k)
- [x] B) n & ~(1 << k)
- [ ] C) n ^ (1 << k)
- [ ] D) n >> k
💡 Giải thích: Tạo mask có tất cả bit = 1 trừ bit k: ~(1 << k). AND với n → giữ nguyên mọi bit, chỉ tắt bit k. Ví dụ: n = 0b1111, k = 2 → ~(1<<2) = 0b1011 → 0b1111 & 0b1011 = 0b1011.
Câu 2: Fast Exponentiation (lũy thừa nhanh) giảm số phép nhân từ O(n) xuống bao nhiêu?
- [ ] A) O(1)
- [ ] B) O(√n)
- [x] C) O(log n)
- [ ] D) O(n/2)
💡 Giải thích: Thay vì nhân n lần, fast exponentiation chia n thành biểu diễn nhị phân: a^13 = a^8 × a^4 × a^1 (13 = 1101₂). Chỉ cần log₂(n) phép bình phương + đếm bit 1 phép nhân → O(log n).