Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Problem Statement
2.1.
Example 1
2.2.
Example 2
3.
Solution Approach
3.1.
Brute Force Approach
3.1.1.
Algorithm
3.1.2.
Implementation in C++
3.2.
C++
3.2.1.
Implementation in Java
3.3.
Java
3.3.1.
Implementation in Python
3.4.
python
3.4.1.
Time Complexity
3.4.2.
Space Complexity
3.5.
Brian Kernighan’s Algorithm
3.5.1.
Algorithm
3.5.2.
Dry Run
3.5.3.
Implementation in C++
3.6.
C++
3.6.1.
Implementation in Java
3.7.
Java
3.7.1.
Implementation in Python
3.8.
python
3.8.1.
Time Complexity
3.8.2.
Space Complexity
3.9.
Checking Each Bit in a Number
3.9.1.
Algorithm
3.9.2.
Implementation in C++
3.10.
C++
3.10.1.
Implementation in Java
3.11.
Java
3.11.1.
Implementation in Python
3.12.
python
3.12.1.
Time Complexity
3.12.2.
Space Complexity
3.13.
Using Built-in Functions
3.13.1.
Implementation in C++
3.14.
C++
3.14.1.
Implementation in Java
3.15.
Java
3.15.1.
Implementation in Python
3.16.
python
3.16.1.
Time Complexity
3.16.2.
Space Complexity
4.
Frequently Asked Questions
4.1.
What is count set bits?
4.2.
What are bitwise operators in C++?
4.3.
Can we use the left shift and right shift for negative numbers?
4.4.
What is Bitwise XOR?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Count Number of Set Bits in an Integer

Author Sahil Setia
2 upvotes

Introduction 

It sometimes becomes necessary to consider data at the bit level. We must work with each data bit separately. We may also need to turn on/off specific data bits to make our task more manageable; we use binary operators. Bitwise operations can be considered an essential topic of Data Structures and Algorithms.

count total set bits

In this blog, we will discuss a fundamental and common problem of binary numbers, which is the Count Number of Set Bits in an Integer. Before diving into the solution, let’s look at the problem statement again. 

Also read - Count Total Set Bits in an Array

Problem Statement

The main task is to count the total number of 1’s in the binary representation of an integer. Simply put, the task is to find the total number of 1’s(set bits) in the integer. 

Example 1

Input

Given Integer (N) = 15

Output

Count of set bits in 15 = 4

Explanation

The binary representation of 15 looks like this:

Example of Count total set bit

15 = 23 + 22 + 21 + 20 = 8 + 4 + 2 + 1 = 15

So, the total number of set bits, i.e., the total number of bits with value one is 4.

Example 2

Input

Given Integer (N) = 25

Output

Count of set bits in 25 = 3

Explanation

The binary representation of 25 looks like this:

Example image of Count total set bit

25 = 24 + 23 + 20  = 16 + 8 + 1 = 25

So, the total number of set bits, i.e., the total number of bits with value one is 3.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Solution Approach

There are numerous approaches to solving this problem, and there are infinite ways of implementing this problem. This problem is the basic building block of the bitwise algorithms, and we will see some common yet effective ways to solve this problem.

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 we go through all the bits of the number and check whether it is set by performing AND operation(with 1). There will be two possibilities which are as follows:

  • 1 AND 1 (Right-most bit) = 1
  • 1 AND 0 (Right-most bit) = 0
     

Algorithm

  1. Call the ‘count_bits()’ function for the corresponding number ‘N’ where N is the given input of which the total set bits have to be counted.
     
  2. Initialize a ‘total’ variable to store the count of the total set bits in the integer.
     
  3. Use a while loop with the condition till N is greater than zero and do the following:
    1. Take AND of the number ‘N’ with 1 to check if the rightmost bit is set and increment the ‘total’ if the bit is set.
       
    2. Shift the number to the right using the right shift operator.
       
  4. Finally, display the output as the value returned by the ‘count_bits()’ function.
     

Implementation in C++

  • C++

C++

/* 
   C++ program to count the number of set bits
   in the given integer.
*/

#include <iostream>
using namespace std;

// Function which calculates the set bits
int count_bits(int n){
  
   // Initialising a variable to count the total.
   int total = 0;
  
   while (n){
      
       // If the last bit is 1, increment the total
       if((n&1)>0){
           ++total;
       }

       // Right shift the value of n
       n >>= 1;
   }
   return total;
}

int main(){
  
   // Given integer
   int N = 15;

   // Calling the function.
   cout << "Count of set bits in " << N<<" = "<<count_bits(N);
   return 0;
}


Output

Output image

Implementation in Java

  • Java

Java

public class MyClass {
  
   // Function which calculates the set bits
   static int count_bits(int n){
      
       // Initialising a variable to count the total.
       int total = 0;
      
       while (n>0){
          
           // If the last bit is 1, increment the total
           if((n&1)>0){
               ++total;
           }
  
           // Right shift the value of n
           n >>= 1;
       }
       return total;
   }

   // Driver program
   public static void main(String args[]){
      
       // Given integer
       int N = 15;
      
       System.out.print("Count of set bits in ");
       System.out.print(N+(" = "));
      
       // Calling the function
       System.out.println(count_bits(N));
   }
}


Output

Output image

Implementation in Python

  • python

python

# Count the Set bits
def count_bits(n):
  # Initialising a variable to count the total.
  total = 0
 
  while (n):
     
     # If the last bit is 1, increment the total
     total += n & 1
    
     # Right shift the value of n
     n >>= 1
    
  return total

# Main Function
# Given integer
N = 15

# Calling the function
print("Count of set bits in ", N," = ",count_bits(N))


Output

Output image

Time Complexity

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

Explanation: Since there are 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)).

Space Complexity

O(1)

Explanation: Since the initialization of a variable to store the count of set bits takes up a constant space, the space complexity is O(1).

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, all the set bits become unset after the Xth execution of the loop. 
 

Algorithm

  1. Call the ‘count_bits()’ function for the corresponding number ‘N,’ where N is the given input of which the total set bits have to be counted.
     
  2. Initialize a ‘total’ variables to store the count of the total set bits in the integer.
     
  3. Use a while loop with condition till N is greater than zero and do the following:
    1. Take AND of the number ‘N’ with ‘N - 1’ and increment the ‘total’ on each iteration.
       
  4. Finally, display the output as the value returned by the ‘count_bits()’ function.
     

Dry Run

Initially, N = 15

Dry run image 1

Before looking at the process, let’s see how the AND operator works as shown in the table below.

Dry run image 2
  • N = 15, N - 1 = 14, N = 15 & 14 = 14, total = 1
Dry run image 3

So, AND of N and N - 1 will be equal to “1 1 1 0” in binary form which is equivalent to 14 in decimal form. Similarly, for the next steps we will calculate AND in this manner.

  • N = 14, N - 1 = 13, N = 14 & 13 = 12, total = 2
Dry run image 4
  • N = 12, N - 1 = 11, N = 12 & 11 = 8, total = 3
Dry run image 5
  • N = 8, N - 1 = 7, N = 8 & 7 = 0, total = 4
Dry run image 6
  • Finally, the ‘total’ value is equal to 4 and is displayed as the output.
     

Implementation in C++

  • C++

C++

/* 
   C++ program to count the number of set bits
   in the given integer.
*/

#include <iostream>
using namespace std;

// Function which calculates the set bits
int count_bits(int n){
  
   // Initialising a variable to count the total.
   int total = 0;
  
   while (n){
      
       // Taking AND of N with N - 1
       n = n & (n - 1);
      
       // Increment total on each iteration.
       ++total;

   }
   return total;
}

int main(){
  
   // Given integer
   int N = 15;


   // Calling the function.
   cout << "Count of set bits in " << N<<" = "<<count_bits(N);
   return 0;
}


Output

Output image

Implementation in Java

  • Java

Java

public class MyClass {
  
   // Function which calculates the set bits
   static int count_bits(int n){
      
       // Initialising a variable to count the total.
       int total = 0;
      
        while (n > 0){
          
           // Taking AND of N with N - 1
           n = n & (n - 1);
          
           // Increment total on each iteration.
           ++total;
       }
       return total;
   }

   // Driver program
   public static void main(String args[]){
      
       // Given integer
       int N = 15;
      
       System.out.print("Count of set bits in ");
       System.out.print(N+(" = "));
      
       // Calling the function
       System.out.println(count_bits(N));
   }
}


Output

Output image

Implementation in Python

  • python

python

# Count the Set bits
def count_bits(n):
  # Initialising a variable to count the total.
  total = 0
 
  while (n):
      
      # Taking AND of N with N - 1
      n = n & (n - 1);
      
      # Increment total on each iteration.
      total = total + 1;


  return total

# Main Function
# Given integer
N = 15

# Calling the function
print("Count of set bits in ", N," = ",count_bits(N))


Output

Output image

Time Complexity

O(Total set bits in the integer)

Explanation: The total number of iterations will be the total number of set bits in the integer. In the worst case, all the bits will be set and the number can have a maximum of logN bits, and the worst case complexity will be O(logN).

Space Complexity

O(1)

Explanation: Since the initialization of a variable to store the count of set bits takes up a constant space, the space complexity is O(1).

Also see, Euclid GCD Algorithm

Checking Each Bit in a Number

The state of every bit in the number is examined to see if it is set or not. As the number is examined, all the bits of the number are iterated and bitwise AND of the number with a power of 2’s is taken and if the result is not equal to zero, the particular bit in the position is known to be set.

Algorithm

  1. Call the ‘count_bits()’ function for the corresponding number ‘N,’ where N is the given input of which the total set bits have to be counted.
     
  2. Initialize a ‘total’ variables to store the count of the total set bits in the integer.
     
  3. Use a ‘for loop’ to iterate over all the bits and do the following:
    1. Take AND of the number ‘N’ with 2i  where ‘i’ is the current bit to check, and if the AND is greater than zero, that means the current bit is set and increment the ‘total’ on each iteration.
       
  4. Finally, display the output as the value returned by the ‘count_bits()’ function.
     

Implementation in C++

  • C++

C++

/* 
   C++ program to count the number of set bits
   in the given integer.
*/

#include <iostream>
using namespace std;

// Function which calculates the set bits
int count_bits(int n){
  
   // Initialising a variable count to 0.
   int total = 0;
  
   // Iterating over all the bits
   for(int i = 0 ; i < 32 ; i++){
      
       // (1<<i) corresponds to 2 raised to i
       if(n & (1<<i)){
           ++total;
       }
   }
   return total;
}

int main(){
  
   // Given integer
   int N = 15;

   // Calling the function.
   cout << "Count of set bits in " << N<<" = "<<count_bits(N);
   return 0;
}


Output

Output image

Implementation in Java

  • Java

Java

public class MyClass {
  
   // Function which calculates the set bits
   static int count_bits(int n){
      
       // Initialising a variable count to 0.
       int total = 0;
      
       // Iterating over all the bits
       for(int i = 0 ; i < 32 ; i++){
          
           // (1<<i) corresponds to 2 raised to i
           if((n & (1<<i)) > 0){
               ++total;
           }
       }
       return total;
   }

   // Driver program
   public static void main(String args[]){
      
       // Given integer
       int N = 15;
      
       System.out.print("Count of set bits in ");
       System.out.print(N+(" = "));
      
       // Calling the function
       System.out.println(count_bits(N));
   }
}


Output

Output image


Implementation in Python

  • python

python

# Count the Set bits
def count_bits(n):
  
   # Initialising a variable count to 0.
   total = 0
  
   # Iterating over all the bits
   for i in range(64):
      
       # (1<<i) corresponds to 2 raised to i
       if (n & (1<<i)) > 0:
           total = total + 1
 
   return total

# Main Function
# Given integer
N = 15

# Calling the function
print("Count of set bits in ",N," = ",count_bits(N))


Output

Output image

Time Complexity

O(1)

Explanation: Iterating over all the bits take in total of 32 iterations,i.e. constant iterations take place hence, the time complexity of the above code is O(1). 

Space Complexity

O(1)

Explanation: Since the initialization of a variable to store the count of set bits takes up a constant space, the space complexity is O(1).

Using Built-in Functions

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

Implementation in C++

  • C++

C++

/* 
   C++ program to count the number of set bits
   in the given integer.
*/

#include <iostream>
using namespace std;

// Function which calculates the set bits
int count_bits(int n){
  
   // Calling the builtin pop count method
   int total = __builtin_popcount(n);
   return total;
}

int main(){
  
   // Given integer
   int N = 15;

   // Calling the function.
   cout << "Count of set bits in " << N<<" = "<<count_bits(N);
   return 0;
}


Output

Output image

 

Implementation in Java

  • Java

Java

public class MyClass {
  
   // Function which calculates the set bits
   static int count_bits(int n){
      
       // Calling the builtin pop count method
       int total = Integer.bitCount(n);
       return total;
   }

   // Driver program
   public static void main(String args[]){
      
       // Given integer
       int N = 15;
      
       System.out.print("Count of set bits in ");
       System.out.print(N+(" = "));
      
       // Calling the function
       System.out.println(count_bits(N));
   }
}


Output

Output image

 

Implementation in Python

  • python

python

# Count the Set bits
def count_bits(n):

   # Calling the builtin pop count method
   total = bin(n).count('1')
   return total

# Main Function
# Given integer
N = 15

# Calling the function
print("Count of set bits in ",N," = ",count_bits(N))


Output

Output image

Time Complexity

O(Total set bits in the integer)

Explanation: The total number of iterations will be the total number of set bits in the integer. In the worst case, all the bits will be set and the number can have a maximum of logN bits, and the worst case complexity will be O(logN).

Space Complexity

O(1)

Explanation: Since the initialization of a variable to store the count of set bits takes up a constant space, the space complexity is O(1).

Must read decimal to binary c++, Strong number in c

Check out this problem - First Missing Positive 

Frequently Asked Questions

What is count set bits?

Count set bits is a computing operation that includes counting the number of binary 1s (set bits) in a binary representation of a number or data structure, such as an integer or a bit array. It is also known as population count or Hamming weight.

What are bitwise operators in C++?

The operators used to alter the bits of a number are known as bitwise operators. Bitwise operators are operations on numbers at the binary level that can be used to set, shift, or remove bits.

Can we use the left shift and right shift for negative numbers?

Negative numbers should not be handled using the left and right shift operators. In C and C++, if the second operand is a negative number, the result is undefined behavior.

What is Bitwise XOR?

It is also called Exclusive OR. It takes two numbers as input operands and does Bitwise XOR on every corresponding bit of two numbers. If both bits are different, the bitwise OR operator returns 1. Otherwise, it produces a value of 0.

Conclusion

In this blog, we discussed a problem to Count Number of Set Bits in an Integer and saw the various approaches we can use to solve the problem. We saw the algorithm for the approaches and implemented the solution in three different languages, C++, Java, and Python.

Recommended Reading:

Also check out the Interview guide for Product Based Companies as well as some of the Popular interview problems from top tech companies like Amazon, Adobe, Google, Uber, Microsoft, etc.

Refer to our guided pathways on Code studio to learn more about Competitive ProgrammingJavaScriptSystem DesignDSA C++etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.

Happy Coding!

Previous article
Lucky Alive Person in a Circle
Next article
Gray Code
Live masterclass