Count Number of Set Bits in an Integer

Ishita Chawla
Last Updated: May 19, 2022
Difficulty Level :
MEDIUM

Introduction 

It sometimes becomes necessary to consider data at the bit level, and we must work with each data bit separately. We may also need to turn on/off specific data bits, and to make our task more manageable; we use binary operators. There are six leading binary operators to easily perform operations and manipulate data bits.

Bitwise operations can be considered an essential topic in Data Structure and Algorithms. In this blog, we will be discussing a fundamental and common problem of binary numbers, which is counting the total number of set bits in the binary representation of a given integer. 

Problem Statement

The task is to find the count of the total number of 1’s in the binary representation of an integer, or simply the number of set bits. 

For example:

  1. N = 7
    Binary representation of 7 = 111
    Number of set bits = 3 (Number of 1’s)
     
  2. N = 16
    Binary representation of 16 = 10000
    Number of set bits = 1 (Number of 1’s)
     
  3. N = 31
    Binary representation of 31 = 11111
    Number of set bits = 5 (Number of 1’s)

 

We will try to solve this problem using four different approaches to get a better understanding of concepts.

Brute Force Approach

The naive approach uses a simple loop and a right shift operator and considers every integer bit. A counter is maintained subsequently to keep track of the number of set bits.

This means that we go through all the number bits and check whether it is set or not by performing AND operation(with ). 

1 AND 1 (Right-most bit) = 1

1 AND 0 (Right-most bit) = 0

If the bit is set, we increment the counter by 1. Then we shift the bits towards the right and repeat the above operation till the number becomes 0

Implementation in C++

/* C++ program to count the number of set bits in the binary representation of a positive integer.*/

#include <bits/stdc++.h>
using namespace std;

// Function to calculate the number of set bits.
int countBits(int n)
{
    // Initialising a variable count to 0.
    int count = 0;
    while (n)
    {
        // If the last bit is 1, count will be incremented by 1 in this step.
        count += n & 1;

        // Using the right shift operator.
        // The bits will be shifted one position to the right.
        n >>= 1;
    }
    return count;
}

int main()
{
    // Taking user input.
    int n;
    n=15;

    // Calling the function.
    cout << "The number of bits :" << countBits(n);
    return 0;
}

Output:

The number of bits : 4

Implementation in Python

# count the bits
def count(n):
   count = 0
   while (n):
      count += n & 1
      n >>= 1
   return count
# main
n = 15
print("The number of bits :",count(n))

Output:

The number of bits : 4

Implementation in Java


// Java program to Count set
// bits in an integer
import java.io.*;
 
class countSetBits {
    /* Function to get no of set
    bits in binary representation
    of positive integer n */
    static int countSetBits(int n)
    {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
 
    // driver program
    public static void main(String args[])
    {
        int i = 15;
        System.out.print("The number of bits : ");
        System.out.println(countSetBits(i));
    }
}

Output:

The number of bits : 4

Time Complexity

O(log(N)), where ‘N’ is the given number.

Since there is log(N) bits in a number and we are going through all the bits one by one, the time complexity of this approach is O(log(N)).

Using the built-in Functions

Implementation in C++

GCC provides a built-in function __builtin_popcount(N) to count the number of set bits in a positive integer, N.

/* C++ program to count the number of set bits in the binary representation of a positive integer.*/

#include <bits/stdc++.h>
using namespace std;
int main()
{
    // Taking user input.
    int n = 15;
    // Using the function.
    cout << "The number of bits " << __builtin_popcount(n) << endl;
    return 0;
}

Output:

The number of bits : 4

Implementation in Python

# Python program to demonstrate __builtin_popcount()
print("The number of bits :",bin(15).count('1'));

Output:

The number of bits : 4

Implementation in Java


// java program to demonstrate
// __builtin_popcount()

import java.io.*;

class Bitset {

   // Driver code
   public static void main(String[] args)
   {

       System.out.print("The number of bits : ");
       System.out.println(Integer.bitCount(15));
   }
}

Output:

The number of bits : 4

Time Complexity

The time complexity of this method is O(N), where ‘N’ is the number of bits in the given integer.

Using Standard Libraries

We can also use bitset::count(), an inbuilt STL in C++ that returns the count of the total number of set bits in an integer.

Implementation in C++

/* C++ program to count the number of set bits in the binary representation of a positive integer.*/
#include <bits/stdc++.h>
using namespace std;

int main()
{
    // Taking user input.
    int n=15;
    // Initialisation of a bitset.
    bitset<8> bs(n);

    // Function to count the number of set bits.
    cout << "The number of set bits is " << bs.count() << endl;
    return 0;
}

Output:

The number of bits : 4

Implementation in Python

def countSetBits(num): 
    # output will be like bin(11)=0b1101 
    binary = bin(num) 
    setBits = [ones for ones in binary[2:] if ones=='1']       
    print ("The number of bits : ",len(setBits)) 
   
# Driver program 
if __name__ == "__main__": 
   num = 15
   countSetBits(num)

Output:

The number of bits : 15

Time Complexity

The time complexity of this method is O(N), where ‘N’ is the number of bits in the given integer.

Brian Kernighan’s Algorithm

The algorithm states that the bitwise AND of 2 numbers, i.e., N and (N-1) unsets the rightmost set bit of the original number N. We use a while loop to unset the rightmost set bit of the integer in every iteration. One thing that should be kept in mind is that the number of times the loop executes equals the number of set bits in that integer. So we keep track of the number of set bits using a pointer.  

According to the above explanation, if there are X set bits in the number, then all the set bits become unset after the Xth execution of the loop. 

Let us understand this with the help of an example.

Example

Let us consider a number, N = 5

Let us assume a variable, count = 0

 

Initially,

N = 5 (101)

count = 0

 

Step 1:

N = 5 (101)

N - 1 = 4 (100)

→ N = N & (N - 1)

        = 5 & 4 (101 & 100)

        = 4 (100)

count = 1  

 

Step 2:

N = 4

N - 1 = 3

→ N = N & (N - 1)

        = 4 & 3 (100 & 011)

        = 0 

count = 2

 

Since N becomes 0, the loop will no longer be executed. 

Thus the number of set bits in 5 is 2.

Implementation in C++

/* C++ program to count the number of set bits in the binary representation of a positive integer.*/

#include <bits/stdc++.h>
using namespace std;

// Function to calculate the number of set bits.
int countBits(int n)
{
    // Initialising a variable count to 0.
    int count = 0;
    while (n)
    {
        n = n & (n - 1);
        count++;
    }
    return count;
}
int main()
{
    // Taking user input.
    int n = 15;
    // Calling the function.
    cout << "The number of bits : " << countBits(n);
    return 0;
}

Output:

The number of bits : 4

Implementation in Python

def countsetbits(A):
    count = 0       
    while(A!=0):
        A = A & (A-1)    
        count = count+1  
    return(count)       
 
n = 15
print("The number of bits : ",countsetbits(n))

Output:

The number of bits : 4

Implementation in Java

// Java implementation for recursive
// approach to find the number of set
// bits using Brian Kernighan Algorithm
import java.io.*;
 
class Bitset {
 
    // recursive function to count set bits
    public static int countSetBits(int n)
    {
 
        // base case
        if (n == 0)
            return 0;
        else
            return 1 + countSetBits(n & (n - 1));
    }
 
    // Driver function
    public static void main(String[] args)
    {
 
        // get value from user
        int n = 15;
               System.out.print("The number of bits : ");
        // function calling
        System.out.println(countSetBits(n));
    }
}

Output:

The number of bits : 4

Time Complexity

O(log(N)), where ‘N’ is the given number.

Since there can be at most log N set bits in a number, the time complexity of this approach is O(log N).

FAQs

Why do we use Brian Kernighan’s Algorithm?

It is one of the important bit manipulation algorithms used to count the number of set bits in an integer.

What are set bits?

In a binary representation of an integer, the bits with the value ‘1’ are known as set bits.

Which inbuilt STL in C++ returns the count of the total number of set bits in an integer?

The bitset::count() is an inbuilt STL in C++ that returns the count of the total number of set bits in an integer.

Conclusion

This article discusses one of the most frequently asked coding interview questions, commonly referred to as counting the number of set bits in an integer. Questions related to Bit Manipulation are pretty tricky but easy to solve.

These questions are asked during various coding contests as well as placement tests. In this article, we discussed one such problem, "counting the number of set bits in an integer" along with various possible approaches to solve it.

One important variation of this problem is Finding the lone set bit. Other famous bit related problems are Flip the given bits and Toggle K bits. If you are looking for a curated list of problems on bit manipulation, here’s your one-stop destination. Don't forget to try them out because it is a rigorous practice that allows us to hone our skills.

To practice more such problems, Codestudio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think