Lesson 45 — Bit Manipulation
Ba module tương tác: (1) Bit playground — click toggle từng bit, áp dụng trick; (2) XOR single number — animate XOR dồn để tìm số lẻ; (3) Subset enumeration — duyệt bitmask thành các tập con. Đọc lý thuyết ở nút 📖 Đọc README.
1. Bit playground — thao tác trên bit
Click vào ô bit để bật/tắt (toggle). Hoặc nhập một số rồi Nạp. Sau đó áp dụng các bit trick — kết quả hiện ngay dưới dạng nhị phân.
2. XOR single number — tìm số xuất hiện lẻ lần
Nhập dãy số (mọi số đôi một, trừ đúng 1 số lẻ). Bấm XOR từng bước để xem
bộ tích luỹ res ^= v dồn dần — cặp giống nhau khử về 0, còn lại số lẻ.
Thử: XOR cả mảng — các cặp tự triệt tiêu (a⊕a=0), còn lại đúng số xuất hiện lẻ lần: O(n) thời gian, O(1) bộ nhớ.
3. Subset enumeration — bitmask thành tập con
Với n phần tử, mỗi mask trong 0 .. 2ⁿ-1 là một tập con: bit i bật ⟹ phần tử i thuộc tập.
Đổi n rồi Liệt kê, hoặc Bước qua từng mask để thấy ánh xạ.