Kiểm tra bitwise AND của tập con bất kỳ có phải lũy thừa của 2 trong Python

Cho mảng nums. Kiểm tra xem có tồn tại tập con nào mà bitwise AND của tất cả phần tử trong tập con là một lũy thừa của 2 hay không.

Ví dụ: nums = [22, 25, 9] → tập con {22, 9} → nhị phân 10110 & 1001 = 10000 = 16 (lũy thừa của 2) → True.

Giải thuật

• Với mỗi vị trí bit i (0..31), xem xét tập con các số có bit i = 1.
• Tính AND của tất cả các số trong tập con đó.
• Nếu kết quả là lũy thừa của 2 → True.

Mã ví dụ

MAX = 32

def is_2s_pow(v):
    return v and (v & (v - 1)) == 0

def solve(nums):
    if len(nums) == 1:
        return is_2s_pow(nums[0])
    total = 0
    for i in range(MAX):
        total = total | (1 << i)
    for i in range(MAX):
        ret = total
        for j in range(len(nums)):
            if nums[j] & (1 << i):
                ret = ret & nums[j]
        if is_2s_pow(ret):
            return True
    return False

nums = [22, 25, 9]
print(solve(nums))

Đầu vào

[22, 25, 9]

Đầu ra

True