Solution Review: Count Set Bits Or Number of 1 bit's

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

Solution review

We saw an algorithm to solve this problem in the previous lesson. Let’s see how to solve this more efficiently 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,

• The while loop runs twice if a number has 2 set bits.
• The while loop runs four times if a number has 4 set bits.

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

Java

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));
    }
}

Python

def CountSetBits(n):
    count=0
    while n > 0:
        n &= (n - 1)
        count+=1
    return count

number=125
print('SetBit Count is : ', CountSetBits(number))

JavaScript

const CountSetBits = (n) => {
    let count = 0;
    
    while (n > 0) {
        n &= (n - 1);
        count++;
    }

    return count;
}

console.log ('SetBit Count is', CountSetBits (125));

C++

#include <iostream>
using namespace std;

int helper(int n){
    int count = 0;
    
    while (n > 0){
        n &= (n - 1);
        count++;
    }

    return count;
}

int main() {
    int number = 125;
    cout << "SetBit count is : " << helper(number);
}

TypeScript

export const CountSetBits = (n: number): number => {
    let count: number = 0;

    while (n > 0) {
        n &= (n - 1);
        count++;
    }

    return count;
}

console.log('SetBit Count is', CountSetBits(125));

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, the 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) or O(1).

Space complexity: O(1) extra space

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

Lookup table approach

This approach is considered one of the fastest, using a lookup table.

Why is the below algorithm faster than previous approaches?

• Lookup-based approach.
• This approach requires a 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, with four chunks.
• We have 8 bits in each chunk. Then the range is from 0 - 255 (0 to 2⁷).
• So, we may need to count set bits from o to 255 in individual chunks.

Java

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));
    }
}

Python

def CountSetBits(n):
    table = [0] * 256
    table[0] = 0

    for i in range(1, 256):
        table[i] = (i & 1) + table[i >> 1] 

    res = 0
    for i in range(4): 
        res += table[n & 0xff] 
        n >>= 8 

    return res

n=125
print ('SetBit Count is', CountSetBits (n))

JavaScript

const CountSetBits = (n) => {
    const table = [];
    table[0] = 0;

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

    let res = 0; 
    for (let i = 0; i < 4; i++) { 
        res += table[n & 0xff]; 
        n >>= 8; 
    } 

    return res;
}

console.log ('SetBit Count is', CountSetBits (125));

C++

#include <iostream>
using namespace std;

int helper(int n){
    int table[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;
}

int main() {
    int number = 125;
    cout << "SetBit count is : " << helper(number);
    return 0;
}

TypeScript

export const CountSetBits = (n: number): number => {
    const table: number[] = [];
    table[0] = 0;

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

    let res: number = 0; 
    for (let i: number = 0; i < 4; i++) { 
        res += table[n & 0xff]; 
        n >>= 8; 
    } 

    return res;
}

console.log('SetBit Count is', CountSetBits(125));

Explanation

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

table[0] = 0;
for (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 for each i^th 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) 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). No additional space is allocated.