# Count Number of Set Bits in an Integer

## 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:**

**N = 7**

Binary representation of**7 = 111**

Number of set bits =**3**(Number of**1**’s)

**N = 16**

Binary representation of**16 = 10000**

Number of set bits =**1**(Number of**1**’s)

**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 **).

**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

*numbers, i.e.,*

**2***and*

**N***unsets the rightmost set bit of the original number*

**(N-1)***. 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.*

**N**According to the above explanation, if there are * X* set bits in the number, then all the set bits become unset after the

*execution of the loop.*

**X**^{th}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.

Comments

## No comments yet

## Be the first to share what you think