Chuyển tới nội dung chính

Thao tác bit (Bit Manipulation)

Bạn sẽ học được gì

Máy tính nói chuyện bằng bit — chỉ 0 và 1. Thao tác bit (bit manipulation) là cách bạn "thì thầm" trực tiếp với phần cứng: bật một công tắc, tắt một công tắc, hỏi "công tắc này đang bật không?". Bạn sẽ học AND, OR, XOR, NOT, dịch bit, và một bộ mẹo kinh điển chạy cực nhanh — toàn bộ trong một lệnh CPU.

1. Trực quan: một dãy công tắc đèn​

Hãy tưởng tượng mỗi số nguyên là một dãy công tắc đèn. Đèn bật = 1, đèn tắt = 0. Số 13 trong hệ nhị phân là 1101:

   bit thu:   3   2   1   0
              ┌───┬───┬───┬───┐
   13 = 1101  │ 1 │ 1 │ 0 │ 1 │
              └───┴───┴───┴───┘
   gia tri:    8   4   0   1     ->  8 + 4 + 1 = 13

Bit ở bên phải là bit thứ 0 (giá trị 2^0 = 1), kế bên là bit thứ 1 (giá trị 2), rồi 4, 8... Toàn bộ "ma thuật" của thao tác bit là tác động lên từng công tắc này mà không phải đụng tới các công tắc khác.

2. Bốn toán tử nền tảng​

Mỗi toán tử làm việc trên từng cặp bit ở cùng vị trí:

Toán tửKý hiệuQuy tắcVí dụ (6 = 110, 3 = 011)
AND&cả hai cùng 1 → 16 & 3 = 010 = 2
OR|có ít nhất một 1 → 16 | 3 = 111 = 7
XOR^khác nhau → 16 ^ 3 = 101 = 5
NOT~đảo mọi bit~6 = -7 (xem mục dưới)

Ngoài ra có dịch bit:

  • x << k (dịch trái k): thêm k số 0 vào bên phải → nhân với 2^k. 1 << 3 = 8.
  • x >> k (dịch phải k): bỏ k bit bên phải → chia nguyên cho 2^k. 13 >> 1 = 6.
XOR có ba tính chất vàng

a ^ a = 0 (tự triệt tiêu), a ^ 0 = a (giữ nguyên), và XOR có tính giao hoán. Ba điều này là nền của vô số thủ thuật — ví dụ "tìm số xuất hiện lẻ lần trong mảng".

3. Bước qua: bật/tắt/đảo bit thứ k​

Mẹo cốt lõi: 1 << k tạo một "mặt nạ" chỉ có một bit bật tại vị trí k. Từ đó:

  • Kiểm tra bit k: (x >> k) & 1
  • Bật bit k: x | (1 << k)
  • Tắt bit k: x & ~(1 << k)
  • Đảo bit k: x ^ (1 << k)
🐞 Thao tác trên bit thứ 1 của x = 5 (101)Bước 1/5
1x = 5            # 101
2k = 1
3bit = (x >> k) & 1   # doc bit thu 1
4x = x | (1 << k)     # bat bit thu 1
5x = x ^ (1 << k)     # dao bit thu 1
Biến tại bước này
x5 (101)
👉 x = 5, nhị phân 101. Bit thứ 1 đang là 0.

4. Code chạy thử: bộ mẹo cơ bản​

Đang tải trình chạy code…

Mẹo chẵn lẻ: n & 1 lấy bit thấp nhất. Bit đó là 1 ⇔ n lẻ. Nhanh hơn n % 2 về mặt khái niệm (dù trình biên dịch thường tối ưu giống nhau).

5. Hai mẹo "đỉnh": đếm bit 1 và x & (x-1)​

Có một biểu thức đẹp đến mức đáng nhớ: x & (x - 1) xoá bit 1 thấp nhất của x.

   x      = 1 0 1 1 0 0    (44)
   x - 1  = 1 0 1 0 1 1
   x&(x-1)= 1 0 1 0 0 0    (40)  <- bit 1 thap nhat da bien mat

Vì sao? Trừ 1 sẽ "lật" bit 1 thấp nhất thành 0 và biến mọi bit 0 bên phải nó thành 1. AND với x giữ lại phần cao và xoá đúng cụm đó. Hệ quả: lặp x = x & (x-1) cho tới khi x bằng 0, số lần lặp chính là số bit 1 — vòng lặp chỉ chạy đúng bằng số bit bật (thuật toán Brian Kernighan).

Đang tải trình chạy code…

6. Bitmask: gói cả một tập hợp vào một số nguyên​

Một số nguyên là một tập con: bit thứ i bật ⇔ phần tử i có trong tập. Đây là bitmask — nền của quy hoạch động trên tập (DP bitmask) và là cách lưu "trạng thái nhiều cờ" siêu gọn.

Việc cầnBiểu thức
Tập rỗng0
Thêm phần tử imask | (1 << i)
Bỏ phần tử imask & ~(1 << i)
Có chứa i?(mask >> i) & 1
Hợp / giao hai tậpa | b / a & b
Số phần tửđếm bit 1

Bẫy thường gặp:

  • Ưu tiên toán tử: x & 1 == 0 bị Python hiểu là x & (1 == 0). Luôn đặt ngoặc: (x & 1) == 0.
  • ~x cho số âm: với số nguyên Python (vô hạn bit), ~x luôn bằng -x - 1. ~6 = -7. Đừng bất ngờ khi thấy số âm.
  • Dịch trái lớn: 1 << k với k rất lớn vẫn chạy trong Python nhưng tốn bộ nhớ.

7. Mẫu nhận diện​

  • "Tập con", "bật/tắt cờ", "có/không có trong tập" và n nhỏ (≤ 20) → nghĩ tới bitmask.
  • "Đếm số bit 1", "số xuất hiện lẻ lần", "tìm phần tử cô đơn" → XOR / Kernighan.
  • "Nhân/chia cho luỹ thừa 2", "tròn xuống/lên luỹ thừa 2" → dịch bit.
  • Cần thao tác O(1) trên cờ nhị phân, tiết kiệm bộ nhớ tối đa → thao tác bit.

8. 🎮 Trò chơi: Đọc vị các bit​

🎮 Đọc vị các bitCâu 1/4· Điểm 0· 🔥 0

AND giữ bit chung, OR gộp, XOR đánh dấu khác biệt. Tính nhẩm theo nhị phân nhé!

In ra gì?

print(5 ^ 5)

9. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Để kiểm tra n có lẻ không, biểu thức nào đúng nhất?
2. x << 3 tương đương với phép nào?
3. Biểu thức x & (x - 1) làm gì?

10. Hoàn thành​

…

☑️ Tiếp theo: 3.6.2 — Toán cho lập trình (GCD, sàng số nguyên tố, lũy thừa mod nhanh).