Thao tác bit là gì: toán tử, mẹo và ví dụ

Thao tác bit giải bài toán gì

Một số nguyên là một dãy bit, và nhiều bài toán thực chất xoay quanh các bit đó: quyền tệp như rwx, cờ tính năng, mặt nạ mạng, màu điểm ảnh, tập tùy chọn gọn nhẹ, checksum và hàm băm. Toán tử bitwise cho phép đọc và thay đổi nhiều bit cùng lúc chỉ bằng một phép toán, vừa gọn bộ nhớ vừa rất nhanh.

Các câu hỏi phỏng vấn cũng dùng mẹo bit vì chúng cho lời giải thanh lịch với bộ nhớ O(1), ví dụ tìm số xuất hiện một lần khi mọi số khác xuất hiện hai lần.

Các toán tử

Các ví dụ dùng a = 12 (nhị phân 1100) và b = 10 (nhị phân 1010).

a, b = 12, 10
print(bin(a), bin(b))         # 0b1100 0b1010
print(a & b, a | b, a ^ b)    # 8 14 6
print(~a, a << 1, a >> 2)     # -13 24 3
print(f"{a ^ b:04b}")         # 0110
print(int("1010", 2))         # 10

Thao tác trên một bit

Vị trí bit được đếm từ 0 ở bên phải (bit có trọng số thấp nhất). Mặt nạ 1 << i chỉ có bit i được đặt.

Ví dụ: đếm bit 1

Phương pháp của Brian Kernighan xóa bit 1 thấp nhất cho đến khi hết, nên nó lặp một lần cho mỗi bit 1, không phải mỗi vị trí bit. Lần theo x = 44 (nhị phân 101100):

def count_bits(x):
    count = 0
    while x:
        x &= x - 1        # drop the lowest set bit
        count += 1
    return count

print(count_bits(44))     # 3
print((44).bit_count())   # 3
print((44).bit_length())  # 6

int.bit_count() có từ Python 3.10. int.bit_length() trả về số bit cần để viết số đó ở dạng nhị phân, không tính dấu.

Các mẹo kinh điển trong Python

from functools import reduce
from operator import xor

# Every number appears twice except one: pairs cancel out with XOR.
print(reduce(xor, [4, 1, 2, 1, 2]))   # 4

# Swap two integers without a temporary variable (for illustration only).
x, y = 5, 9
x ^= y; y ^= x; x ^= y
print(x, y)                            # 9 5

# Bitmask as a set: enumerate all subsets of 3 items.
items = ["a", "b", "c"]
for mask in range(1 << len(items)):
    print(mask, [items[i] for i in range(len(items)) if mask >> i & 1])
# 0 []
# 1 ['a']
# 2 ['b']
# 3 ['a', 'b']
# 4 ['c']
# 5 ['a', 'c']
# 6 ['b', 'c']
# 7 ['a', 'b', 'c']

Mask 0 là tập rỗng, 5 (nhị phân 101) là ['a', 'c'], và 7 là cả ba phần tử. Quy hoạch động bitmask dùng cùng ý tưởng này, với mask làm trạng thái, cho bài toán trên tối đa khoảng 20 phần tử, như bài toán người bán hàng (traveling salesman) với đầu vào nhỏ.

Hai mẹo kinh điển nữa: x & 1 bằng 1 với số lẻ, và XOR của mọi số từ 0 đến n với mọi giá trị trong một list sẽ tìm ra số bị thiếu.

Độ phức tạp thời gian và không gian

Bitmask dùng một bit cho mỗi phần tử có thể có, nên một tập 64 cờ nằm gọn trong một số nguyên 64 bit, so với 64 biến boolean riêng hoặc 64 phần tử list.

Lỗi thường gặp

• Số âm: số nguyên Python hoạt động như thể có vô hạn bit dấu, nên ~5 là -6 và bin(-5) là -0b101, không phải chuỗi bù hai. Để xem mẫu 32 bit, hãy che giá trị bằng mask: -5 & 0xFFFFFFFF.
• Dịch phải số âm trong Python là dịch số học: -8 >> 1 là -4, và -1 >> 10 vẫn là -1.
• Tràn số ở các ngôn ngữ có độ rộng cố định: trong Java hoặc C, 1 << 31 trên int 32 bit trở thành số âm hoặc không xác định; hãy dùng kiểu 64 bit và 1L << 40 hoặc 1ULL << 40.
• Nhầm toán tử logic với toán tử bitwise: and và or (&&, || trong các ngôn ngữ họ C) trả về giá trị đúng/sai, còn & và | làm việc từng bit.
• Khả năng đọc: thay x * 2 bằng x << 1 không mang lại lợi ích tốc độ nào với trình biên dịch hiện đại hay trong Python, mà còn làm code khó đọc hơn.

Ứng dụng thực tế

• Quyền tệp Unix: chmod 754 đặt ba nhóm 3 bit (rwx = 4 + 2 + 1).
• Mạng: mặt nạ mạng con IPv4, trong đó ip & mask cho địa chỉ mạng của một khối CIDR.
• Cờ và tùy chọn: re.IGNORECASE | re.MULTILINE của Python và enum.Flag kết hợp các tùy chọn bằng OR.
• Đồ họa và màu sắc: một giá trị RGB 24 bit đóng gói đỏ, xanh lục và xanh lam thành (r << 16) | (g << 8) | b.
• Cấu trúc dữ liệu và thuật toán: Bloom filter, bitset, cây Fenwick (dùng i & -i), băm và checksum.
• Bài phỏng vấn: single number, counting bits, power of two, reverse bits, missing number, tập con bằng bitmask, tổng hai số nguyên không dùng +.