Search⌘ K
AI Features
Home
Courses
Grokking Bit Manipulation for Coding Interviews

Solution Review: Count Set Bits

Explore efficient methods to count set bits in integers, focusing on Brian Kernighan's algorithm and a lookup table approach. Understand how these methods improve time complexity compared to naive solutions while keeping space usage minimal. This lesson helps you apply bitwise AND operations to optimize bit counting for coding interviews.

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 representation.

So, time taken is O(SetBit Count).

The run time depends on the number of set bits in n. In the worst case, all bits in n are 1-bits. In the case of a 32-bit integer, the run time is O(32)O(32) or O(1)O(1).

Space complexity: O(1) extra space

The space complexity is O(1)O(1). No additional space is allocated.

Lookup table approach

This approach is considered to be one of the fastest, as it uses a lookup table.

Why below algorithm is faster than previous approaches?

  • Lookup based approach.
  • This approach requires an O(1) time solution to count the set bits.
  • However, this requires some preprocessing.
  • So, we divide our 32-bit input into 8-bit chunks, so there are four chunks.
  • We have 8 bits in each chunk, then the range is from 0 - 255 (0 to 272^{7}-1).
  • So, we may need to count set bits from o to 255 in individual chunks.
class CountSetBit {
    private static int helper(int n) {
        int[] table = new int[256];
        table[0] = 0;
        
        for (int i = 1; i < 256; i++) {
            table[i] = (i & 1) + table[i >> 1]; // i >> 1 equals to i/2
        }
        int res = 0; 
        for (int i = 0; i < 4; i++) { 
            res += table[n & 0xff]; 
            n >>= 8; 
        } 
        
        return res;
    }
    public static void main(String[] args) {
        int number = 125;
        System.out.println("SetBit Count is : " + helper(number));
    }
}

Explanation

In the below code snippet, we are storing the set bit count value in the lookup table.

table[0] = 0;
for (int i = 1; i < 256; i++) {
  table[i] = (i & 1) + table[i >> 1]; // i >> 1 equals to i/2
}

We are initializing the table with the set bit count per each ith place.

Algorithm:

  • Initialize table[0] with 0.
  • Loop through, in the range from 1 to 256
    • for i = 1,
      • table[1] = (1 & 1) + table[1 / 2] => table[1] = 1 + table[0]; => table[1] = 1.
      • table[2] = (2 & 1) + table[2 / 2] => table[2] = 0 + table[1]; => table[2] = 1.
      • table[3] = (3 & 1) + table[3 / 2] => table[3] = 1 + table[1]; => table[3] = 2. so on…
  • Initialize int res = 0.
  • Loop through, in the range from 0 to 3
    • To check on each of the 4 8-bit chunks using res += table[n & 0xff];
    • Shift n by 8 bits (n >>= 8), we do this to get the second last 8 bits…
    • End loop.
  • Return res.

Time and space complexities

Time complexity: O(1) in simple terms

This requires an O(1)O(1) time solution to count the set bits in each of the 8-bit chunks.

Space complexity: O(1) extra space

The space complexity is O(1)O(1). No additional space is allocated.