对元组/列表中的所有整数进行按位与

Question

我有以下函数，其中 v 是整数元组，hits 是整数。该函数使用位掩码首先检查元组中的任何两个整数是否共享任何设置位，然后检查命中中的所有设置位是否也在元组中的整数之间设置

def noCollisionsBin(v, hits): 
    for x, y in itertools.combinations(v,2):    
        if (x & y): #if any 2 integers share set bits, they are overlapping
            return False
    tot = 0
    for i in v:
        tot |= i

    return (tot & hits) == hits #if all set bits of "hits" are set in the integers combined, the configuration is valid.

它可以工作，但我觉得应该有更多比使用 itertools.combinations() 更有效地检查第一个条件。我不想循环数组两次，而是只想执行一次，以类似于我使用 |= 组合 v 中整数的设置位的方式使用按位 AND 累积方式。我尝试了以下解决方案，但它产生了太多有效组合，表明第一个条件没有正确检查。

def noCollisionsBin(v, hits):
    tot_and = v[0]
    tot = v[0]
    for i in range(1,len(v)):
        tot |= v[i]
        tot_and &= v[i]
        if tot_and:
            return False
    
    return (tot & hits) == hits

我希望我所做的事情是有意义的。我对使用位运算符很陌生，任何帮助将不胜感激！

Answer 1

您没有提供任何代码来检查输出是否正确，但我相信以下内容会起作用。
关键思想是 tot 存储先前数字中设置的所有位。
如果发生任何碰撞，则 tot & v[i] 将设置重复位，因此将大于 0。

def noCollisionsBin(v, hits):
    tot = 0
    for i in range(len(v)):
        if tot & v[i] > 0:
            return False
        tot |= v[i]
    return (tot & hits) == hits

---

关于为什么第二个代码示例不能按预期工作的说明：
它仅检查 v 的前两个元素中的冲突。
如果它们确实发生碰撞，则循环将在第一次迭代中正确返回 False。
但是，如果不这样做，则 tot_and 将等于 0，并且在循环的剩余部分中将为 0，如 0 &对于任何x，x = 0。