algorithm – The most efficient methods for finding units in binary form of a number

Question:

You are given a binary number, for example 10011010.
What efficient methods are there to find out the number of bits in this number, in which the value is TRUE?

I only came up with two:

  1. Number & 1 and if equal to 1, then increase the counter, and then shift the number by one to the right.
  2. Create a lookup table in which the index is numbers from 0 to 255, and the value is the number of ones in this number.

What other methods are there?

Answer:

The most efficient method is as follows: while a number (it must be interpreted as an unsigned number in order to count all units), say n , is not equal to zero, perform the following operation

n &= n - 1;

and accordingly increase the unit counter by one.

The principle is as follows. Let's say there is one in the number 1

0b00100000

If you subtract 1 from this number, you get

0b00011111

Now, if we apply the binary AND operation, we get

0b00100000
&
0b00011111
==========
0b00000000

The number became equal to 0, therefore it contained only one 1, since this operation was performed only once.

Using the same methods that you indicated, you will have to shift either the number itself or the unit 6 times to get to the unit in the original number, and 6 times you will have to perform a comparison with the unit. And the lookup table is completely inapplicable for numbers that take up more than one byte. Moreover, it still takes up memory space for such a simple task.

Scroll to Top