Kiểm tra xem bitwise AND của bất kỳ tập hợp con nào có phải là lũy thừa của hai trong Python hay không

Giả sử chúng ta có một mảng số được gọi là nums. Chúng tôi phải kiểm tra xem có tồn tại bất kỳ tập con nào trong số các số có bitwise AND là lũy thừa của hai hay không.

Vì vậy, nếu đầu vào là nums =[22, 25, 9], thì đầu ra sẽ là True, dưới dạng tập con {22, 9} dạng nhị phân là {10110, 1001} AND của hai tập này là 10000 =16 là lũy thừa của 2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• MAX:=32 xem xét có 32 bit số ở mức tối đa
• Xác định một hàm giải quyết (). Quá trình này sẽ mất vài giây
• nếu kích thước của nums là 1, thì
  • trả về true khi nums [0] là lũy thừa của 2, ngược lại là false
• tổng số:=0
• đối với tôi trong phạm vi từ 0 đến MAX - 1, thực hiện
  • tổng số:=tổng số HOẶC 2 ^ i
• đối với tôi trong phạm vi từ 0 đến MAX - 1, thực hiện
  • ret:=tổng số
  • đối với j trong phạm vi 0 đến kích thước của nums, thực hiện
    • nếu nums [j] AND (2 ^ i) khác 0, thì
      • ret:=ret AND nums [j]
  • nếu ret là lũy thừa của 2, thì
    • trả về True
• trả về Sai

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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(0, MAX):
      total = total | (1 << i)
   for i in range(0, MAX):
      ret = total
      for j in range(0, 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