PythonでサブセットのビットごとのANDが2の累乗であるかどうかを確認します

numsと呼ばれる数値の配列があるとします。ビット単位のANDが2の累乗であるnumのサブセットが存在するかどうかを確認する必要があります。

したがって、入力がnums =[22、25、9]のような場合、出力はTrueになります。サブセット{22、9}として、バイナリ形式は{10110、1001}であり、これら2つのANDは10000=16です。これは2の累乗です。

これを解決するには、次の手順に従います-

• MAX：=最大で32ビットの数値があることを考慮して32
• 関数solve（）を定義します。これには数がかかります
• numsのサイズが1の場合、
  • nums [0]が2の累乗の場合はtrueを返し、それ以外の場合はfalseを返します
• 合計：=0
• 0からMAX-1の範囲のiの場合は
  • 合計：=合計または2 ^ i
• 0からMAX-1の範囲のiの場合は
  • ret：=合計
  • 0からnumsのサイズの範囲のjについては、
    • 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