Competitive Programming: Count Set Bits in an Integer

Hello everyone ... 

Here we are going to solve a Competitive Programming problem related to Bit Manipulation.

Problem Statement

Given a positive integer N, print count of set bits in it.

Examples

Input:
N = 6
Output:
2
Explanation:
Binary representation is '110' 
So the count of the set bit is 2.

Input:
8
Output:
1
Explanation:
Binary representation is '1000' 
So the count of the set bit is 1.

Problem Link: https://practice.geeksforgeeks.org/problems/set-bits0143/1 

Solution

Approach 1

In this approach, we will loop through all the bits of a given integer and check if the bit is set. If it is, then we will increment the count.

To loop through the bits of an integer, we will iterate from LSB (Least Significant Bit) to MSB(Most Significant Bit), i.e, from Right to Left. In each iteration, we will increment the count by 1 if LSB (i.e. last bit) is set and then we will perform the Right Shift operation on the given integer by 1 time.

C++ Code

Time Complexity

Since we are iterating through all bit, the Time Complexity is O(k), where k is the number of bits in an integer.

Approach 2

We can use Brian Kernighan’s algorithm to improve the above naive algorithm’s performance. 

Before going to the actual approach, let's understand the following statement

Subtracting 1 from a decimal number flips all the bits after the rightmost set bit, including the rightmost set bit itself.

Decimal (n)	Binary
10	1010
10 - 1 = 9	1001
9 - 1 = 8	1000
8 - 1 = 7	0111
7 - 1 = 6	0110

Now we can use the expression n & (n-1) to turn off the rightmost set bit of a number n.

So, the idea is to only iterate through the set bits of an integer, and in each iteration, we will turn off the rightmost set bit. We can keep track of the number of iterations which is equal to the number of set bits of an integer.

C++ Code

Time Complexity

Since we are only iterating through the set bits of an integer, the Time Complexity is O(k), where k is the number of set bits of an integer.

Approach 3

We can also use the following GCC built-in functions to get the count of set bits in an integer

• __builtin_popcount for int 
• __builtin_popcountl for long int
• __builtin_popcountll for long long

C++ Code

Approach 4

We can also use std::bitset::count that returns the total number of set bits in a bitset.

C++ Code

References

• https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

Hopefully, you enjoyed this blog post and learned something new. If you want to share anything or if you have any doubts or suggestions please comment below. 

Your Task

To sharp your brain, I would like to ask a couple of questions depending on what we learned in this blog

Question 1: Given a non-negative integer n. The task is to check if n is a power of 2.

Hint: Think about how the expression n & (n-1) works.

Question 2: You are given two numbers A and B. The task is to count the number of bits needed to be flipped to convert A to B.

Hint: Think about how you can leverage the power of bitwise XOR operation.

Let me know your answers in the comments below.

Thank you, guys. 

Have a nice day and stay tuned for new blog posts. Bye ...👋