Kiểm tra chia hết cho lũy thừa 2 không dùng phép toán (Python)

Bài toán: Cho x và n, kiểm tra x có chia hết cho 2^n không, không dùng phép chia, nhân, trừ.

Quan sát bitwise

x chia hết cho 2^n ⟺ n bit thấp nhất của x đều là 0.
Mask (1 << n) - 1 tạo ra n bit 1 cuối (ví dụ n=3 → 0b111).
x & mask == 0 ⟺ n bit cuối của x đều 0.

Triển khai Python

def solve(x, n):
    return (x & ((1 << n) - 1)) == 0

# Test
print(solve(32, 5))   # True: 32 = 2^5, binary 100000, 5 bit cuối = 00000
print(solve(24, 3))   # True: 24 = 8*3, chia hết 2^3
print(solve(24, 4))   # False: 24 không chia hết 16

Kết quả

True

Giải thích

• 1 << n dịch bit 1 sang trái n vị trí = 2^n.
• (1 << n) - 1 tạo mask n bit 1 (ví dụ n=3 → 0b111 = 7).
• x & mask lấy n bit thấp nhất của x.
• Kết quả 0 ⟺ x chia hết cho 2^n.
• Chỉ dùng bitwise AND, shift, trừ 1 (hằng số).