ตรวจสอบว่ามี subset ใดที่ bitwise AND เป็นกำลังของ 2 หรือไม่ ใน Python

ปัญหา

ให้อาร์เรย์ nums ตรวจสอบว่ามี subset ใดที่ bitwise AND ของสมาชิกทั้งหมดเป็นกำลังของ 2 (1,2,4,8,...) หรือไม่

ตัวอย่าง

nums = [22, 25, 9]
22 = 10110₂, 9 = 01001₂
Subset {22, 9}: 10110 & 01001 = 00000? รอ... 22=10110, 9=01001 → AND=00000? ไม่ใช่
ลองใหม่: 22=10110, 25=11001 → AND=10000=16 (2⁴) → True

แนวคิดการแก้ปัญหา

สำหรับแต่ละบิต i (0-31):

1. พิจารณา subset ของตัวเลขที่มีบิต i = 1
2. คำนวณ AND ของ subset นี้
3. ถ้าผลลัพธ์เป็นกำลังของ 2 → True

โค้ดตัวอย่าง

def is_power_of_two(x):
    return x > 0 and (x & (x - 1)) == 0

def solve(nums):
    if len(nums) == 1:
        return is_power_of_two(nums[0])
    
    # ลองทุกบิตเป็น "บิตที่ตั้งค่าในผลลัพธ์"
    for bit in range(32):
        mask = 1 << bit
        # subset ของตัวเลขที่มีบิตนี้ = 1
        subset_and = (1 << 32) - 1  # all 1s (32-bit)
        for num in nums:
            if num & mask:
                subset_and &= num
        if is_power_of_two(subset_and):
            return True
    return False

print(solve([22, 25, 9]))  # True (22 & 25 = 16)

อินพุต / เอาต์พุต

Input:  [22, 25, 9]
Output: True