The population count (or pop count) algorithm is one of the ideas you might look at and think: "Wow! It's simple yet so genial". This algorithm can be useful to count the number of enabled bits (1, on, active, etc) on a binary sequence (e.g.: 01010110110011).

The algorithm idea

1. The algorithm receives a binary sequence (in our case, we will represent a binary sequence using an integer).

2. We create a variable to count occurrences of bits 1

3. While the inputted sequence is different from zero, we execute the loop

4. In the loop:

   1. We perform a bitwise operation: n AND n-1.

   2. Increment the counter

5. When the loop ends, return count.

It's important to understand what happens inside the loop of step 4. Let's suppose we had inputted n = 5 (which binary is 101). When the loop starts, it will execute the following operations:

1. n = 5 -> (101 AND 100) = 100 | State: n = 4 , count = 1

2. n = 4 -> (100 AND 011) = 000 | State: n = 0, count = 2

3. The result is 2.

Is it magic?! We count the exact number of bits 1 using a few steps. Let's try another example, suppose n = 15 (which binary is 1111):

1. n = 15 -> (1111 AND 1110) = 1110 | State: n = 14 , count = 1

2. n = 14 -> (1110 AND 1101) = 1100 | State: n = 12 , count = 2

3. n = 12 -> (1100 AND 1011) = 1000 | State: n = 8 , count = 3

4. n = 08 -> (1000 AND 0111) = 0000 | State: n = 0 , count = 4

5. The result is 4.

It's amazing! Let's check the code.

The code

The following approach of the pop count algorithm is known as Brian Kernighan's way and the code below does exactly what was described in the previous section.

function popCount(n: number) : number {
   let count = 0;
   while(n) {
     n &= n - 1;
     count++;
   }
   return count;
}
popCount(11); // Returns: 3

using System;

public class Program
{
    public static void Main()
    {
        int result = PopCount(11); // Returns: 3
    }

    public static int PopCount(int n) {
        int count = 0;
        while(n > 0) {
          n &= n - 1;
          count++;
        }
        return count;
    }
}

Conclusion

This kind of algorithm can be useful in some situations we need to count a lot of binary events.

Imagine you have a traffic monitoring system that records the number of vehicles passing through a specific point on a road. Each vehicle is represented by a sensor that can be either activated (represented by "1") or deactivated (represented by "0"). The system needs to count the total number of vehicles that have passed through that point during a specific period.

To perform this count, you can apply the pop count algorithm to the data recorded by the system. By traversing the bits of the binary sequence that represents the presence or absence of vehicles (1 for a present vehicle, 0 for an absent vehicle), you can count the set bits (1) to determine the total number of vehicles that have passed through the monitoring point.