检查 Python 中任何子集的按位与运算结果是否为 2 的幂

假设我们有一个名为 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 次浏览

开启你的职业生涯

完成课程获得认证

开始学习