檢查 Python 中任何子集的按位與運算結果是否為 2 的冪

Python 伺服器端程式設計程式設計

假設我們有一個名為 nums 的數字陣列。我們必須檢查是否存在任何 nums 的子集，其按位與運算結果是 2 的冪。

因此，如果輸入類似於 nums = [22, 25, 9]，則輸出將為 True，因為子集 {22, 9} 的二進位制形式為 {10110, 1001}，這兩個數的與運算結果為 10000 = 16，它是 2 的冪。

為了解決這個問題，我們將遵循以下步驟：

MAX := 32 （假設最多為 32 位數）
定義一個函式 solve()。它將接收 nums 作為引數。
如果 nums 的大小為 1，則：
- 如果 nums[0] 是 2 的冪，則返回 true，否則返回 false。
total := 0
對於 i 從 0 到 MAX - 1：
- total := total OR 2^i
對於 i 從 0 到 MAX - 1：
- ret := total
- 對於 j 從 0 到 nums 的大小：
  - 如果 nums[j] AND (2^i) 不為零，則：
    - ret := ret AND nums[j]
- 如果 ret 是 2 的冪，則：
  - 返回 True
返回 False

讓我們看下面的實現來更好地理解：

示例

線上演示

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

Arnab Chakraborty

更新於：2020-12-30

286 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習