Get the the number of zeros and ones of a binary number in Python

Question

I am trying to solve a binary puzzle, my strategy is to transform a grid in zeros and ones, and what I want to make sure is that every row has the same amount of 0 and 1.

Is there a any way to count how many 1s and 0s a number has without iterating through the number?

What I am currently doing is:

def binary(num, length=4):
    return format(num, '#0{}b'.format(length + 2)).replace('0b', '')

n = binary(112, 8)
// '01110000'
and then
n.count('0')
n.count('1')

Is there any more efficient computational (or maths way) of doing that?

Answer 1

What you're looking for is the Hamming weight of a number. In a lower-level language, you'd probably use a nifty SIMD within a register trick or a library function to compute this. In Python, the shortest and most efficient way is to just turn it into a binary string and count the '1's:

def ones(num):
    # Note that bin is a built-in
    return bin(num).count('1')

You can get the number of zeros by subtracting ones(num) from the total number of digits.

def zeros(num, length):
    return length - ones(num)

Demonstration:

>>> bin(17)
'0b10001'
>>> # leading 0b doesn't affect the number of 1s
>>> ones(17)
2
>>> zeros(17, length=6)
4

Answer 2

If the length is moderate (say less than 20), you can use a list as a lookup table.

It's only worth generating the list if you're doing a lot of lookups, but it seems you might in this case.

eg. For a 16 bit table of the 0 count, use this

zeros = [format(n, '016b').count('0') for n in range(1<<16)]
ones = [format(n, '016b').count('1') for n in range(1<<16)]

20 bits still takes under a second to generate on this computer

Edit: this seems slightly faster:

zeros = [20 - bin(n).count('1') for n in range(1<<20)]
ones = [bin(n).count('1') for n in range(1<<20)]