Skip to content

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

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. This is a faster execution than the previous naive approach.

Gopi Gorantala
Gopi Gorantala
4 min read

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 27).
  • 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 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) 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.

Coding Interview QuestionsData Structures and AlgorithmsBit Manipulation

Gopi Gorantala Twitter

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Comments


Related Posts

Members Public

Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Leetcode 217: Contains Duplicate
Members Public

Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Leetcode 121: Best Time To Buy and Sell Stock
Members Public

Bit Manipulation Course Overview

Overview In this course, you will learn how to solve problems using bit manipulation, a powerful technique that can be used to optimize your algorithmic and problem-solving skills. This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG companies. To kick things