tuple/list 中所有整数的按位与

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 的前两个元素中的碰撞。如果它们发生碰撞，那么循环将在第一次迭代中正确地 return False。但是，如果他们不这样做，那么 tot_and 将等于 0，并且对于循环的其余部分将为 0，因为 0 & x = 0 对于任何 x.

tuple/list 中所有整数的按位与

Bitwise AND for all integers in tuple/list

python

bitwise-operators

bitwise-and