Mô phỏng thuật toán Kiểm tra luỹ thừa của 2

Power of Two (n & (n-1)) · Nhóm: Bit & Mặt nạ

Một số dương là luỹ thừa của 2 khi và chỉ khi nhị phân của nó có đúng một bit 1; phép n & (n-1) xoá bit 1 thấp nhất, kết quả 0 nghĩa là chỉ có một bit 1.

Ý tưởng

Loại ngay n ≤ 0 vì số không dương không bao giờ là luỹ thừa của 2.

Tính n & (n-1): phép trừ 1 lật bit 1 thấp nhất thành 0 và bật mọi bit thấp hơn nó.

Nếu n & (n-1) == 0 thì n chỉ có một bit 1 nên là luỹ thừa của 2; khác 0 thì không phải.

Vì sao đúng

AND giữ lại bit chung của n và n-1; nếu n chỉ có một bit 1 thì bit đó đã bị n-1 xoá, không còn bit chung, cho ngay kết quả 0 trong thời gian hằng số.

Mã Python

def is_power_of_two(n):
    if n <= 0:                 # non-positive is never a power of two
        return False
    return (n & (n - 1)) == 0  # clearing the lowest set bit gives 0

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