List of binary numbers: How many positions have a one and zero

Question

I have a list of integers, e.g. i=[1,7,3,1,5] which I first transform to a list of the respective binary representations of length L, e.g. b=["001","111","011","001","101"] with L=3.

Now I want to compute at how many of the L positions in the binary representation there is a 1 as well as a zero 0. In my example the result would be return=2 since there is always a 1 in the third (last) position for these entries. I want to compute this inside a function with a numba decorator. Currently my code is:

@nb.njit
def count_mixed_bits_v2(lst):
    andnumber = lst[0] & lst[1]
    ornumber = lst[0] | lst[1]
    for i in range(1, len(lst)-1):
        andnumber = andnumber & lst[i+1]
        ornumber = ornumber | lst[i+1]
    xornumber = andnumber ^ ornumber
    result = 0
    while xornumber > 0:
       result += xornumber & 1
       xornumber = xornumber >> 1
    return result

First I take the AND of all numbers, ans also the OR of all numbers, then the XOR of those two results will have a 1 where the condition is fulfilled. In the end I count the number of 1's in the binary representation. My code seems a bit lengthy and I'm wondering if it could be more efficient as well. Thanks for any comment!

Edit: Without the numba decorator the following function works:

def count_mixed_bits(lst):
    xor = reduce(and_, lst) ^ reduce(or_, lst)
    return bin(xor).count("1")

(Credit to trincot)

Answer 1

I don't know numba, but here's a little rewrite:

• Shorter variable names like and_, using the underscore as suggested by PEP 8 ("used by convention to avoid conflicts with Python keyword") and as done by operator.and_.
• Yours crashes if the list has fewer than two elements, I start with neutral values instead.
• Looping over the list elements rather than the indexes.
• Using augmented assignments like &=.
• In the result loop, drop the last 1-bit so you only have as many iterations as there are 1-bits.

def count_mixed_bits(lst):
    and_, or_ = ~0, 0
    for x in lst:
        and_ &= x
        or_ |= x
    xor_ = and_ ^ or_
    result = 0
    while xor_ > 0:
       result += 1
       xor_ &= xor_ - 1
    return result

Answer 2

I only see a few micro optimisations:

• Iterate the list instead of a range, so that you don't have to do another lookup with list[i+1]
• Use more assignment operators, such as &=, |= and >>=
• It is not needed to use lst[1] in andnumber = lst[0] & lst[1]. It can be just andnumber = lst[0]

So:

def count_mixed_bits_v2(lst):
    andnumber = ornumber = lst[0]
    for value in lst:
        andnumber &= value
        ornumber |= value
    xornumber = andnumber ^ ornumber
    result = 0
    while xornumber > 0:
       result += xornumber & 1
       xornumber >>= 1
    return result

This visits the first list value again (in the first iteration), even though it is not necessary. But that probably does not really hurt performance, and keeps the code simple.