Dùng bit để lưu và xử lý trạng thái

Lan quản lý 4 đèn đánh số từ 0 đến 3. Đèn 0, 2 và 3 đang bật, còn đèn 1 tắt. Thay vì lưu 4 biến riêng, Lan có thể lưu trạng thái trong số 13 và cập nhật từng đèn.

Mỗi bit mang một giá trị theo vị trí

Một bit (binary digit) nhận giá trị 0 hoặc 1. Trong biểu diễn nhị phân của số không âm, vị trí được đếm từ phải sang trái, bắt đầu ở 0. Bit thứ i có trọng số 2 ** i khi bật.

Số 13 có biểu diễn 1101: các trọng số được chọn là 8, 4 và 1. Số 0 có thể viết là 0; thêm số 0 bên trái không đổi giá trị.

Trong bảng, cột bên trái là bit 3, không phải bit 0. Cách viết này giống cách viết số thông thường: hàng đơn vị ở bên phải. Ví dụ sau in dạng nhị phân và trọng số của bit 2.

x = 13
i = 2
print(bin(x))
print(1 << i)

0b1101
4

Tiền tố 0b trong kết quả của bin báo hệ nhị phân. Biểu thức 1 << i dịch bit 1 sang trái i vị trí. Với i = 2, kết quả là 4. Trong Python, 2 ^ i là XOR, không phải lũy thừa; dùng 2 ** i để tính lũy thừa.

AND, OR và XOR kết hợp từng cặp bit

Phép AND (bitwise AND) cho bit 1 khi cả hai bit tương ứng là 1. Phép OR (bitwise OR) cho 1 khi ít nhất một bit là 1. Phép XOR (exclusive OR) cho 1 khi hai bit khác nhau.

Với 13 và 10, viết hai số bằng bốn bit: 1101 và 1010. Chỉ vị trí 3 đều bật, còn ba vị trí có bit khác nhau. Chạy chương trình để đối chiếu ba phép tính.

a, b = 13, 10
print(a & b)
print(a | b)
print(a ^ b)

8
15
7

AND giúp giữ các bit cùng bật; OR gộp các bit đang bật. XOR đánh dấu các vị trí khác nhau. Các phép này xử lý từng vị trí độc lập, không có nhớ sang bit bên cạnh như phép cộng.

Dịch bit thay đổi trọng số theo lũy thừa của hai

Với k không âm, x << k bằng x * 2 ** k. Phép x >> k bằng x // 2 ** k; các bit thấp bị bỏ. Ví dụ với 13, dịch phải hai bước tương ứng chia lấy phần nguyên cho 4.

x = 13
print(x << 2)
print(x >> 2)
print(13 // 4)

52
3
3

Số bước dịch âm gây ValueError. Đoạn sau cố ý tạo lỗi để bạn thấy điều kiện này.

print(5 << -1)

ValueError: negative shift count

Khi dữ liệu cho chỉ số i, cần bảo đảm i >= 0 trước khi tạo 1 << i. Số nguyên Python có độ dài thay đổi, nên một phép dịch rất lớn cũng có chi phí bộ nhớ và thời gian.

Mặt nạ giúp kiểm tra hoặc thay đổi đúng một bit

Mặt nạ (mask) là số có các bit được chọn để xác định vị trí cần thao tác. Với i = 1, mặt nạ 1 << i là 0010 nếu nhìn trong bốn bit. Trên trạng thái 13, bit 1 đang tắt.

Nếu x & mask khác 0, bit đó đang bật. Muốn lấy riêng giá trị 0 hoặc 1, dùng (x >> i) & 1. Lưu ý kết quả x & mask khi bật có thể là 2, 4 hoặc một trọng số khác, không nhất thiết là 1.

Đoạn sau đọc trạng thái và chỉ số bit. Mỗi lệnh thay đổi được áp dụng độc lập lên x ban đầu.

13 1

x, i = map(int, input().split())
mask = 1 << i
print((x >> i) & 1)
print(x | mask)
print(x & ~mask)
print(x ^ mask)

0
15
13
15

OR bật bit đã chọn và giữ các bit khác. AND với ~mask tắt bit đó, vì các vị trí khác vẫn được giữ. XOR đảo trạng thái: chạy hai lần với cùng mặt nạ sẽ khôi phục giá trị ban đầu. Bật hai lần hoặc tắt hai lần không làm bit đổi thêm.

Trong Python, ~mask bằng -mask - 1, chứ không phải số dương chỉ gồm bốn bit. Phép x & ~mask vẫn tắt đúng vị trí khi x không âm. Nếu cần đảo toàn bộ trong đúng w bit, dùng x ^ ((1 << w) - 1) với 0 <= x < 1 << w.

x, w = 5, 4
print(~x)
print(x ^ ((1 << w) - 1))

-6
10

Một mask biểu diễn tập vị trí được chọn

Nếu chỉ số của một món đồ là i, bit i bật biểu thị món đó được chọn. Chẳng hạn 1011 biểu thị các chỉ số 0, 1 và 3. Hai món có cùng giá trị vẫn là hai vị trí khác nhau.

Đếm số bit bật của số không âm bằng bit_count(). Với số âm, phương thức này đếm bit 1 trong trị tuyệt đối, không đếm một dãy bit dấu vô hạn. Bài này quy định mask không âm.

items = [5, 2, 7, 4]
mask = 0b1011
chosen = [items[i] for i in range(len(items)) if mask & (1 << i)]
print(chosen)
print(mask.bit_count())
print(sum(chosen))

[5, 2, 4]
3
11

Mỗi vòng chỉ kiểm tra một chỉ số nên với 4 món cần 4 lần kiểm tra. Với n món, cách đọc này cần O(n) phép kiểm tra và tối đa O(n) bộ nhớ cho danh sách kết quả. Mặt nạ 0 biểu diễn tập rỗng; mask có bit ngoài n cần được kiểm tra nếu đề không cho phép.

Với hai mask trên cùng tập vị trí, a & b là giao và a | b là hợp. Kiểm tra a có nằm trong b bằng (a & b) == a. Bài 3 trình bày cách duyệt toàn bộ tập con; ở đây ta chỉ dùng biểu diễn đó.

XOR triệt tiêu các cặp bằng nhau

Giả sử mỗi mã trong một danh sách xuất hiện hai lần, trừ đúng một mã xuất hiện một lần. Ta cần tìm mã đó mà không lưu bảng đếm. Vì x ^ x == 0 và x ^ 0 == x, mỗi cặp tự triệt tiêu. XOR có tính giao hoán và kết hợp, nên vị trí hai bản sao không ảnh hưởng kết quả.

Mã 5 không có cặp nên còn lại sau khi các cặp 6 và 3 bị triệt tiêu. Mã đơn lẻ có thể bằng 0; không được lấy 0 làm dấu hiệu không có đáp án. Chương trình sau đọc đúng n mã.

5
6 3 6 5 3

n = int(input())
values = list(map(int, input().split()))
answer = 0
for x in values:
    answer ^= x
print(answer)

5

Mỗi mã được xử lý một lần. Với 10 000 mã có kích thước cố định, cần khoảng 10 000 phép XOR và O(1) trạng thái tích lũy. Danh sách đọc vào trong ví dụ chiếm O(n) bộ nhớ. Nếu có nhiều mã xuất hiện lẻ lần, kết quả chỉ là XOR của chúng, không xác định được từng mã.

Giả sử có đúng hai mã khác nhau xuất hiện một lần, còn các mã khác xuất hiện hai lần. Gọi XOR của toàn bộ danh sách là r. Các cặp vẫn triệt tiêu, nên r là XOR của hai mã cần tìm. Vì chúng khác nhau, r khác 0 và có ít nhất một bit bật.

Chọn một bit bật trong r. Hai mã cần tìm khác nhau tại bit đó, nên nằm ở hai nhóm khác nhau. Mỗi cặp mã bằng nhau lại nằm trong cùng một nhóm và tiếp tục triệt tiêu. XOR riêng từng nhóm cho hai đáp án.

Trong ví dụ sau, r & -r chọn bit bật thấp nhất của r. Mục tiếp theo giải thích vì sao phép này hoạt động.

values = [2, 7, 2, 5, 9, 9]
r = 0
for x in values:
    r ^= x
bit = r & -r
first = second = 0
for x in values:
    if x & bit:
        first ^= x
    else:
        second ^= x
print(*sorted([first, second]))

5 7

Với dữ liệu này, XOR của hai mã cần tìm là 7 ^ 5 = 2. Bit có trọng số 2 bật ở 7 và tắt ở 5. Hai số 2 thuộc cùng một nhóm; hai số 9 cũng thuộc cùng một nhóm. Hai lượt duyệt mỗi lượt cần n phép xử lý, nên thời gian là O(n) với các mã có kích thước cố định. Ngoài danh sách đầu vào, chỉ cần vài biến tích lũy.

Điều kiện đúng hai mã khác nhau là thiết yếu. Nếu chỉ có một mã lẻ lần hoặc có ba mã lẻ lần, phép chia hai nhóm không bảo đảm trả về những mã cần tìm. Mã bằng 0 vẫn hợp lệ và có thể là một trong hai đáp án.

Bit bật thấp nhất giúp tách và xóa trạng thái

Với x > 0, x & -x giữ lại đúng bit 1 thấp nhất. Ví dụ 12 là 1100, nên bit thấp nhất có trọng số 4. Phép x & (x - 1) xóa đúng bit đó.

Tại sao? Khi trừ 1, bit 1 thấp nhất thành 0 và các bit thấp hơn nó thành 1. Những bit cao hơn không đổi. AND với x giữ phần cao và xóa bit thấp nhất.

x = 12
print(x & -x)
print(x & (x - 1))

4
8

Một số dương là lũy thừa của 2 khi và chỉ khi có đúng một bit bật. Vì vậy kiểm tra x > 0 and (x & (x - 1)) == 0. Điều kiện dương là cần thiết: số 0 cũng cho kết quả AND bằng 0 nhưng không phải lũy thừa của 2.

for x in [0, 1, 6, 8, 16]:
    print(x, x > 0 and (x & (x - 1)) == 0)

0 False
1 True
6 False
8 True
16 True

Bạn cũng có thể lặp bằng cách xóa bit thấp nhất cho tới khi x == 0. Số vòng bằng số bit bật, không phải giá trị của x. Với mask có tối đa 20 bit, vòng lặp chạy tối đa 20 lần.

Duyệt submask chỉ xét các bit có sẵn

Một mặt nạ con (submask) của mask chỉ bật những bit đã bật trong mask. Ví dụ mask = 1010 có bốn submask: 1010, 1000, 0010, 0000. Không được chọn bit 0 hay bit 2 vì chúng không có trong mask ban đầu.

Bắt đầu bằng sub = mask. Với sub > 0, đặt sub = (sub - 1) & mask. Phép trừ tìm giá trị nhỏ hơn; AND bỏ những bit không thuộc mask. Kết quả là submask lớn nhất nhỏ hơn sub, nên dãy giảm và không bỏ sót submask nào.

mask = 0b1010
sub = mask
while True:
    print(format(sub, "04b"))
    if sub == 0:
        break
    sub = (sub - 1) & mask

1010
1000
0010
0000

Nếu mask = 0, vòng trên in 0 một lần rồi dừng. Không cập nhật tiếp sau 0: trong Python, (-1) & mask trả lại mask và vòng có thể lặp mãi. Nếu chỉ cần submask khác 0, dùng điều kiện while sub: và xử lý 0 riêng khi cần.

Mask có k bit bật có đúng 2 ** k submask vì mỗi bit được chọn hoặc bỏ. Với k = 16, có 65 536 trạng thái. Nếu tính tổng bằng cách kiểm tra cả 16 bit ở từng trạng thái, cần tối đa khoảng một triệu lần kiểm tra. Không nên áp dụng cách này cho 30 bit bật mà chưa tính ngân sách.

Xét một bài chọn thiết bị: điểm theo chỉ số là [5, -2, 7, 4], và chỉ các vị trí trong mask 1011 đang sẵn sàng. Ta cần chọn đúng hai vị trí, tổng điểm không vượt 6 và lớn nhất có thể. Các lựa chọn hợp lệ là {0, 1}, {0, 3} và {1, 3}. Tổng tương ứng là 3, 9 và 2; tổng 9 vượt giới hạn, nên đáp án là 3.

Đoạn sau duyệt các submask, lọc số bit và tính điểm. Dấu None phân biệt chưa có lựa chọn với tổng bằng 0. Điều này quan trọng khi mọi điểm đều âm hoặc không có cách chọn.

points = [5, -2, 7, 4]
mask, need, limit = 0b1011, 2, 6
best = None
sub = mask
while True:
    if sub.bit_count() == need:
        total = sum(points[i] for i in range(len(points))
                    if sub & (1 << i))
        if total <= limit and (best is None or total > best):
            best = total
    if sub == 0:
        break
    sub = (sub - 1) & mask
print(best if best is not None else "NONE")

3

Mọi lựa chọn chỉ dùng thiết bị sẵn sàng đều là một submask, và vòng lặp xét mỗi submask đúng một lần. Bộ lọc loại các lựa chọn sai số lượng hoặc vượt giới hạn. Khi cập nhật, best giữ tổng lớn nhất trong các lựa chọn hợp lệ đã xét. Vì vậy kết quả sau vòng lặp là tối ưu; nếu không có ứng viên thì in NONE.

Với n = 16 và mọi thiết bị sẵn sàng, có 65 536 submask. Cách tính tổng trên kiểm tra tối đa 16 vị trí cho mỗi submask đúng số lượng. Cận O(n * 2 ** k) là khoảng một triệu lượt kiểm tra trong trường hợp này. Bộ nhớ phụ không tăng theo số submask, ngoài danh sách điểm đầu vào.

Lỗi thường gặp

Tóm tắt

• 1 << i tạo mặt nạ cho bit i; kết hợp AND, OR, XOR để kiểm tra và cập nhật.
• bit_count() đếm bit 1 của trị tuyệt đối; mask trong bài là số không âm.
• XOR triệt tiêu các cặp, còn x & -x tách bit bật thấp nhất của số dương.
• (sub - 1) & mask chuyển tới submask nhỏ hơn; cần dừng khi gặp 0.
• Ước lượng số trạng thái trước khi chọn thuật toán.

Kiểm tra nhanh

Đọc thêm

• Python: phép toán bit và phương thức của số nguyên.
• CP-Algorithms: duyệt các submask.