Grokking Bit Manipulation for Coding Interviews/

...

/

Solution Review: Count Set Bits

Solution Review: Count Set Bits

This review provides a detailed analysis to solve the count set bits

We'll cover the following...

Solution review

We saw an algorithm to solve this problem in the previous lesson. Let’s see how to solve this in a more efficient way using Briann’s Algorithm.

Brian Kernighan’s algorithm

This is a faster execution than the previous naive approach.

In this approach, we count only the set bits. So,

  • If a number has 2 set bits, then the while loop runs two times.

  • If a number has 4 set bits, then the while loop runs four times.

For example, let us consider the example n = 125 and calculate using this algorithm.

class CountSetBit {
    private static int helper(int n) {
        int count = 0;
        while (n > 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }
    public static void main(String[] args) {
        int number = 125;
        System.out.println("SetBit Count is : " + helper(number));
    }
}

Explanation

         n  = 40    => 00000000 00000000 00000000 00101000
      n - 1 = 39    => 00000000 00000000 00000000 00100111
-----------------------------------------------------------
(n & (n - 1)) = 32  => 00000000 00000000 00000000 00100000   
-----------------------------------------------------------

Now n is 32, so we can calculate this to:

         n  = 32    => 00000000 00000000 00000000 00100000
      n - 1 = 31    => 00000000 00000000 00000000 00011111
-----------------------------------------------------------
(n & (n - 1)) = 0   => 00000000 00000000 00000000 00000000   
-----------------------------------------------------------

Time and space complexities

Time complexity: O(Set Bit count) / O(1) in simple terms

The time taken is proportional to set bits in binary ...