在 Python 中检查任何子集的按位与是否为 2 的幂
pythonserver side programmingprogramming
假设我们有一个名为 nums 的数字数组。我们必须检查是否存在按位与为 2 的幂的 nums 子集。
因此，如果输入为 nums = [22, 25, 9]，则输出将为 True，因为子集 {22, 9} 的二进制形式为 {10110, 1001}，这两个的 AND 为 10000 = 16，即 2 的幂。
为了解决这个问题，我们将遵循以下步骤 −
- MAX := 32 考虑到最大有 32 位数字
- 定义一个函数solve()。这将需要 nums
- 如果 nums 的大小为 1，则
- 当 nums[0] 是 2 的幂时返回 true，否则返回 false
- total := 0
- 对于范围在 0 到 MAX - 1 内的 i，执行
- total := total OR 2^i
- 对于范围在 0 到 MAX - 1 内的 i，执行
- ret := total
- 对于范围在 0 到 nums 的大小内的 j，执行
- 如果 nums[j] AND (2^i) 非零，则
- ret := ret AND nums[j]
- 如果 nums[j] AND (2^i) 非零，则
- 如果 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
