Khóa học Python từ Cơ bản đến Nâng cao

Bài 15.1 - Thao tác bit set trong Python

Bit set là kỹ thuật dùng để lưu trữ và thao tác trên tập hợp các số nguyên nhỏ bằng cách sử dụng các thao tác bit. Đây là một công cụ cực kỳ mạnh mẽ khi xử lý các bài toán tổ hợp, đồ thị, hoặc tối ưu.

1. Ý tưởng bit set là gì?

Thay vì dùng list hoặc set, chúng ta có thể dùng số nguyên nhị phân để biểu diễn tập hợp. Mỗi bit đại diện cho một phần tử:

• Bit thứ 0 bật → phần tử 0 có mặt.
• Bit thứ 1 bật → phần tử 1 có mặt.

Ví dụ:

bitset = 0b10101  # tức là các phần tử 0, 2, 4 có mặt trong tập

2. Thêm một phần tử vào bitset

def add_to_set(s, x):
    return s | (1 << x)

s = 0
s = add_to_set(s, 3)  # thêm phần tử 3
print(bin(s))  # 0b1000

Giải thích: Dùng toán tử | để bật bit thứ x.

3. Xoá một phần tử khỏi bitset

def remove_from_set(s, x):
    return s & ~(1 << x)

s = add_to_set(0, 3)
s = remove_from_set(s, 3)
print(bin(s))  # 0b0

Giải thích: Dùng ~(1 << x) để tạo mặt nạ có tất cả các bit là 1 trừ bit x.

4. Kiểm tra phần tử có trong bitset

def is_in_set(s, x):
    return (s >> x) & 1

s = add_to_set(0, 2)
print(is_in_set(s, 2))  # True
print(is_in_set(s, 3))  # False

Giải thích: Dịch phải x lần và lấy bit cuối cùng.

5. Duyệt tất cả phần tử trong bitset

def print_set(s, n):
    for i in range(n):
        if is_in_set(s, i):
            print(i, end=' ')

s = 0
s = add_to_set(s, 0)
s = add_to_set(s, 2)
s = add_to_set(s, 5)
print_set(s, 8)  # 0 2 5

Giải thích: Duyệt từng bit và in ra nếu bit đó bật.

6. Một số thao tác nâng cao

• Đếm số lượng phần tử trong tập:

  print(bin(s).count('1'))
  

• Kiểm tra tập con: ```python def is_subset(a, b): return (a & b) == a

a là tập con của b nếu mọi bit bật trong a đều có trong b

- **Hợp, giao, hiệu:**
```python
a | b  # hợp
a & b  # giao
a & ~b # hiệu

Kết luận

Bit set là công cụ gọn gàng, mạnh mẽ, rất đáng học trong lập trình thuật toán. Khi bạn cần lưu trữ các tập con của tập nhỏ (ví dụ từ 0 đến 20), việc dùng số nguyên nhị phân sẽ giúp tiết kiệm bộ nhớ và tăng hiệu năng đáng kể!

💡 Bit set thường dùng trong các bài toán kiểu "xét mọi tập con", "tối ưu hoá truy vết", hoặc "DP với trạng thái là tập".

#HappyCoding cùng FullhouseDev! 🚀