Mô phỏng thuật toán Liệt kê mặt nạ con

Submask Enumeration · Nhóm: Bit & Mặt nạ

Với mặt nạ mask cố định, liệt kê mọi mặt nạ con (số mà mỗi bit 1 của nó cũng là bit 1 của mask) bằng vòng lặp sub = (sub-1) & mask cho tới khi về 0.

Ý tưởng

Bắt đầu sub = mask (mặt nạ con lớn nhất, chính là mask).

In sub, rồi nếu sub == 0 thì dừng.

Ngược lại nhảy sub = (sub - 1) & mask để tới mặt nạ con nhỏ hơn kế tiếp, bỏ qua mọi số không phải mặt nạ con.

Vì sao đúng

Phép (sub-1)&mask khéo léo nhảy đúng qua các mặt nạ con giảm dần, nên chỉ duyệt đúng 2^k mặt nạ con (k = số bit 1 của mask) mà không trùng, không sót.

Mã Python

def submasks(mask):
    sub = mask                 # start from the full mask
    while True:
        yield sub              # sub is a submask of mask
        if sub == 0:           # 0 is the last submask
            break
        sub = (sub - 1) & mask  # jump to the next lower submask

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.