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.

Số (0–255):

decimal = 43　binary = 00101011

Bit i:

Sẵn sàng. Thử click một ô bit.

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ẻ.

Dãy số:

res tích luỹ:

0 = 0000

Bấm "XOR bước tiếp" để bắt đầu.

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ạ.

n (1–5):

Tập nền: {0, 1, 2} → 2³ = 8 tập con.