# 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?

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