数组子集的按位与
Bitwise and of subsets of an array
任何人都可以提示如何解决这个问题吗？
给定一个数组 A。是否存在数组 A 的任何子集，如果我们对该子集的所有元素执行与操作，则输出应该是二的幂。
我想过生成幂集并求解，但它的复杂度非常差 (2^n)。
提前致谢。
你可以换个角度看：选2的幂。我们可以生成它吗？
这个问题很容易回答。从设置了与 2 的幂对应的位的集合中取出所有项目。计算所有这些的 AND。通过构造，结果必须设置了我们寻找的位，但它可能有也可能没有设置任何其他位。如果它还有其他位，那么选择其他一些（较小的 - 你不能选择任何额外的项目，因为它们没有设置目标位）子集也不起作用，它只能有 更多 个错误位设置，因为取消设置位的可能性较小。
只需对 2 的所有可能的幂执行此操作，这仅与集合中最大整数中的位数一样多。
任何人都可以提示如何解决这个问题吗？
给定一个数组 A。是否存在数组 A 的任何子集，如果我们对该子集的所有元素执行与操作，则输出应该是二的幂。
我想过生成幂集并求解，但它的复杂度非常差 (2^n)。
提前致谢。
你可以换个角度看：选2的幂。我们可以生成它吗？
这个问题很容易回答。从设置了与 2 的幂对应的位的集合中取出所有项目。计算所有这些的 AND。通过构造，结果必须设置了我们寻找的位，但它可能有也可能没有设置任何其他位。如果它还有其他位，那么选择其他一些（较小的 - 你不能选择任何额外的项目，因为它们没有设置目标位）子集也不起作用，它只能有 更多 个错误位设置，因为取消设置位的可能性较小。
只需对 2 的所有可能的幂执行此操作，这仅与集合中最大整数中的位数一样多。