Kiểm tra một số có là bù 1 của số khác không (Python)

Bài toán: Cho hai số x và y, kiểm tra xem một có phải bù 1 (bitwise NOT) của số kia không. Bù 1: đảo tất cả bit (0→1, 1→0).

Quan sát

x là bù 1 của y ⟺ x XOR y có tất cả bit = 1 ⟺ x XOR y = 2^k - 1 (dạng 111...1).
Số dạng 2^k - 1 thỏa mãn: (n + 1) & n == 0.

Triển khai Python

def all_one(n):
    if n == 0:
        return False
    return ((n + 1) & n) == 0

def solve(x, y):
    return all_one(x ^ y)

# Test
print(solve(9, 6))   # True: 9=1001, 6=0110, XOR=1111
print(solve(5, 2))   # False: 5=101, 2=010, XOR=111 (nhưng độ dài bit khác?)

Kết quả

True

Giải thích

• x ^ y tính XOR bitwise.
• all_one kiểm tra kết quả có dạng 2^k - 1 (tất cả bit 1) bằng cách check (n+1) & n == 0.
• Lưu ý: Cách này giả định cùng độ dài bit. Với Python int vô hạn, 5 (101) và 2 (010) XOR = 111 (7) → all_one(7)=True, nhưng thực tế 5 không phải bù 1 của 2 nếu xét cùng độ dài bit.