Counting 1 Bits
Contents
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
\[\begin{split}
\;\;\;\;1111011_2 \\
\frac{\&\;1111010_2}{\;\;\;\;1111010_2} \\
\end{split}\]
\[\begin{split}
\;\;\;\;1111010_2 \\
\frac{\&\;1111001_2}{\;\;\;\;1111000_2} \\
\end{split}\]
\[\begin{split}
\;\;\;\;1111000_2 \\
\frac{\&\;1110111_2}{\;\;\;\;1110000_2} \\
\end{split}\]
\[\begin{split}
\;\;\;\;1110000_2 \\
\frac{\&\;1101111_2}{\;\;\;\;1100000_2} \\
\end{split}\]
\[\begin{split}
\;\;\;\;1100000_2 \\
\frac{\&\;1011111_2}{\;\;\;\;1000000_2} \\
\end{split}\]
\[\begin{split}
\;\;\;\;1000000_2 \\
\frac{\&\;0111111}{\;\;\;\;0000000_2} \\
\end{split}\]
Imports¶
import math
import itertools
Algorithm¶
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¶
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