Counting 1 Bits¶

Many times you need to count the number of ones or zeros in a number. Let's take as example $123_{10} = 1111011_2$. There are 6 ones and 1 zero.

You can place a single bit mask and run over the number and count non-zero results. But with that solution you loop over ones and zeros.

x & (1 << k)

It is possible to count only the ones and ignoring the zeros, meaning only performing 6 iteration instead of 7

Solution¶

Bitwise and of value and value-1 value & value-1 until value = 0

$$ \;\;\;\;1111011_2 \\ \frac{\&\;1111010_2}{\;\;\;\;1111010_2} \\ $$ $$ \;\;\;\;1111010_2 \\ \frac{\&\;1111001_2}{\;\;\;\;1111000_2} \\ $$ $$ \;\;\;\;1111000_2 \\ \frac{\&\;1110111_2}{\;\;\;\;1110000_2} \\ $$ $$ \;\;\;\;1110000_2 \\ \frac{\&\;1101111_2}{\;\;\;\;1100000_2} \\ $$ $$ \;\;\;\;1100000_2 \\ \frac{\&\;1011111_2}{\;\;\;\;1000000_2} \\ $$ $$ \;\;\;\;1000000_2 \\ \frac{\&\;0111111}{\;\;\;\;0000000_2} \\ $$

Imports¶

In [13]:

import math
import itertools

import math import itertools

Algorithm¶

In [14]:

def count_of_1bits(value):
    n = 0
    print("0b{:b}".format(value))
    while value:
        # Bitwise and of value and value-1
        value &= value - 1
        print("0b{:b}".format(value))
        n += 1
    return n

def count_of_1bits(value): n = 0 print("0b{:b}".format(value)) while value: # Bitwise and of value and value-1 value &= value - 1 print("0b{:b}".format(value)) n += 1 return n

Test¶

In [15]:

value = 0b1111011
number_of_ones = count_of_1bits(value)
print("There are {} one's in 0b{:b}".format(number_of_ones, value))

value = 0b1111011 number_of_ones = count_of_1bits(value) print("There are {} one's in 0b{:b}".format(number_of_ones, value))

0b1111011
0b1111010
0b1111000
0b1110000
0b1100000
0b1000000
0b0
There are 6 one's in 0b1111011