ตรวจสอบว่าระดับบิต AND ของเซตย่อยใดเป็นกำลังสองใน Python

สมมติว่าเรามีอาร์เรย์ของตัวเลขที่เรียกว่า nums เราต้องตรวจสอบว่ามีเซตย่อยของ num ที่มีระดับบิต AND เป็นกำลังสองหรือไม่

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[22, 25, 9] ผลลัพธ์จะเป็น True เนื่องจากเป็นเซตย่อย {22, 9} รูปแบบไบนารีคือ {10110, 1001} AND ของสองตัวนี้คือ 10000 =16 ซึ่งเป็นกำลังของ 2.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• MAX :=32 เมื่อพิจารณาว่ามีตัวเลขสูงสุด 32 บิต
• กำหนดฟังก์ชัน Solve() นี้จะใช้เวลา nums
• ถ้าขนาดของ nums เป็น 1 แล้ว
  • คืนค่า จริง เมื่อ nums[0] เป็นกำลัง 2 มิฉะนั้น เท็จ
• รวม :=0
• สำหรับ i ในช่วง 0 ถึง MAX - 1 ทำ
  • ผลรวม :=ทั้งหมด OR 2^i
• สำหรับ i ในช่วง 0 ถึง MAX - 1 ทำ
  • ret :=ยอดทั้งหมด
  • สำหรับ j ในช่วง 0 ถึงขนาดของ nums ให้ทำ
    • ถ้า nums[j] AND (2^i) ไม่ใช่ศูนย์ ดังนั้น
      • ret :=ret และ nums[j]
  • ถ้า ret เป็นกำลัง 2 แล้ว
    • คืนค่า True
• คืนค่าเท็จ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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))

อินพุต

[22, 25, 9]

ผลลัพธ์

True