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

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个称为nums的数字数组。我们必须检查是否存在num的任何子集，其按位与是2的幂。

因此，如果输入类似于nums = [22，25，9]，则输出将为True，作为子集{22，9}，二进制形式为{10110，1001}这两个的AND为10000 = 16这是2的幂。

为了解决这个问题，我们将遵循以下步骤-

  • MAX：= 32考虑最大有32位数字

  • 定义功能 solve()。这将需要数字

  • 如果nums的大小为1，则

    • 当nums [0]为2的幂时返回true，否则返回false

  • 总计：= 0

  • 对于介于0到MAX-1之间的i

    • 总计：=总计OR 2 ^ i

  • 对于介于0到MAX-1之间的i

    • 返回True

    • 如果nums [j] AND（2 ^ i）不为零，则

    • ret：= ret AND nums [j]

    • ret：=总计

    • 对于范围0到nums大小的j，执行

    • 如果ret是2的幂

    • 返回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

    以上是 检查Python中任何子集的按位与是否为2的幂 的全部内容， 来源链接： utcz.com/z/321388.html

    回到顶部