Bitwise AND for all integers in tuple/list

Question

I have the following function, where v is a tuple of integers and hits is an integer. The function uses bitmasks to first check that no set bits are shared by any two integers in the tuple and then check that all set bits in hits are also set among the integers in the tuple

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.

It works, but I feel like there should be a more efficient way to check the first condition than using itertools.combinations(). Instead of having to loop over the array twice, I would like to do it only once, using bitwise AND in a cumlative fashion similar to how I use |= to combine the set bits of the integers in v. I tried the following solution, but it yields too many valid combinations, indicating that the first condition isn't checked properly.

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

I hope it makes sense what I am trying to do. I am quite new to using bit operators and any help would be much appreciated!

user_5304124 · Answer

You didn't supply any code to check if the output is correct, but I believe the following will work. The key idea is that tot stores all of the bits that were are set in previous numbers. If there is any collision, then tot & v[i] will have the repeating bit set and hence will be greater than 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

A note on why your second code sample doesn't work as expected: it only checks for collision in the first two elements of v. If they do collide, then the loop will correctly return False in the first iteration. However, if they don't then tot_and will be equal to 0 and will be 0 for the remainder of the loop as 0 & x = 0 for any x.

Bitwise AND for all integers in tuple/list

1 Answers