In this blog post, I will teach you how to write C/C++ Program to count set bits in an Integer. After reading this post you able to write an efficient program to count the number of 1s in the binary representation of an integer.
Examples,
Input : n = 9 Output : 2 Binary representation of 9 is 1001 and has 2 set bits Here's a simple ASCII representation of 9 (an 8-bit integer): 7 6 5 4 3 2 1 0 (Bit position) +---+---+---+---+---+---+---+---+ | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | (Example bit values) +---+---+---+---+---+---+---+---+
Input : n = 23 Output : 4 Binary representation of 23 is 00010111 and has 4 set bits Here's a simple ASCII representation of an 8-bit integer: 7 6 5 4 3 2 1 0 (Bit position) +---+---+---+---+---+---+---+---+ | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | (Example bit values) +---+---+---+---+---+---+---+---+
Let’s see the problem statements for this question.
Problem Statement: Given an integer n, count set bits in “n”.
Disclaimer: Try to solve the problem yourself first otherwise it would be not worth solving this problem.
Naive approach:
This is the easiest way to count the number of 1’s in the given integer. In naive approach requires one iteration per bit until no more bits are set. In the iteration check bit, if a bit is set, then increment the set bit count. Consider the below program,
/*
C program to count number of
set bits in a given integer.
*/
#include<stdio.h>
//Function return count of the set bits.
unsigned int countSetBits(unsigned int n)
{
unsigned int CountSetBits = 0;
while (n)
{
CountSetBits += n & 1;
n >>= 1;
}
return CountSetBits;
}
// C Program to validate function countSetBits
int main()
{
unsigned int i = 9;
printf("%d", countSetBits(i));
return 0;
}
Output: 2
How the above C program works:
- Initialize a variable CountSetBits to 0 .
- Use a while loop to iterate through each bit of the integer.
- In each iteration, perform (
n & 1) and if the least significant bit is set, then increment the count. - Right shift the “n” by 1 bit to check the next bit in next iteration.
- Repeat steps 3-4 until all bits have been checked.
If you do not want to use the loop, then you can use the recursive approach. You have to follow the same concept in recursive approach.
/*
C program of recursive approach to find the
number of set bits in binary representation
of positive integer n
*/
#include<stdio.h>
/*
Recursive Function
return count of the set bits.
*/
unsigned int countSetBits(unsigned int n)
{
// base case
if (n == 0)
return 0;
else
// if last bit set add 1 else add 0
return (n & 1) + countSetBits(n >> 1);
}
// C Program to validate function countSetBits
int main()
{
unsigned int i = 23;
printf("%d", countSetBits(i));
return 0;
}
Output: 4
Brian Kernighan’s Algorithm:
Brian Kernighan’s Algorithm is an optimize way for counting the number of set bits in an integer.
Now you are thinking why I am saying this.
I am saying “Brian Kernighan’s Algorithm” is an excellent approach to get count of the set bits because in this algorithm the number of iterations required is equal to the number of set bits in the integer, rather than the total number of bits.
So, if there are only a few 1’s in the given integer, then this algorithm will run significantly faster compared to the traditional naive approach where we are checking each bit individually.
Why There are following steps need to do in Brian Kernighan’s Algorithm.
- Initialize count = 0.
- If integer n is not zero.
- Perform bitwise operation and assign the value back to the n.
These bitwise operations clear the least significant. n &= (n – 1);
- Increment count by 1.
- . Again, go to step 2.
- Perform bitwise operation and assign the value back to the n.
- If there are no set bits remaining, then return count.
#include<stdio.h>
/*
Function Count set bits using the Brian
Kernighan’s Algorithm
*/
unsigned int countSetBits(int n)
{
//count accumulates the total bits set in n
unsigned int count = 0;
while (n)
{
n &= (n - 1);//clear the least significant bit set
count++;
}
return count;
}
// C Program to validate function countSetBits
int main()
{
unsigned int i = 52;
printf("%d", countSetBits(i));
return 0;
}
Output: 3
How the above C program works:
In the above example code, I have taken 52 as an input integer number, which is 00110100 in binary. Let’s see how the above code behave in each iteration.
1st iteration of the loop: n = 52 00110100 & (n) 00110011 (n-1) ~~~~~~~~ 00110000 2nd iteration of the loop: n = 48 00110000 & (n) 00101111 (n-1) ~~~~~~~~ 00100000 3rd iteration of the loop: n = 32 00100000 & (n) 00011111 (n-1) 00000000 (n = 0) //End of iteration
If you want, you can also implement Brian Kernighan’s Algorithm recursively. Consider the below example C Code.
#include<stdio.h>
/*
Recursive Function Count set bits using the Brian
Kernighan’s Algorithm
*/
unsigned int countSetBits(unsigned int n)
{
// base case
if (n == 0)
return 0;
else
return 1 + countSetBits(n & (n - 1));
}
// C Program to validate function countSetBits
int main()
{
unsigned int i = 23;
printf("%d", countSetBits(i));
return 0;
}
Output: 4
Counting bits set by lookup table:
Both above mentioned solutions have the worst-case time complexity of O(log(n)). But using the lookup table you can count bits in O (1) time.
#include<stdio.h>
// C Program to count number of set bits
// using lookup table in O(1) time
// Generate a lookup table for 32 bit integers
#define B2(n) n, n + 1, n + 1, n + 2
#define B4(n) B2(n), B2(n + 1), B2(n + 1), B2(n + 2)
#define B6(n) B4(n), B4(n + 1), B4(n + 1), B4(n + 2)
/*
Lookup table to store the total number of
bits set for each index in the table.
*/
const unsigned char lookuptable[256]
= { B6(0), B6(1), B6(1), B6(2) };
/*
Function to count the total
number of set bits in `n` using a lookup table
*/
unsigned int countSetBits(int n)
{
// first chunk of 8 bits from right
unsigned int count = lookuptable[n & 0xff] +
// second chunk from right
lookuptable[(n >> 8) & 0xff] +
// third and fourth chunks
lookuptable[(n >> 16) & 0xff]
+ lookuptable[(n >> 24) & 0xff];
return count;
}
// C Program to check function countSetBits
int main()
{
unsigned int i = 23;
printf("%d", countSetBits(i));
return 0;
}
Output: 4
Time Complexity: O(1)
Auxiliary Space: O(1)
Using GCC Built-in Function __builtin_popcount:
GCC also provides the inbuilt function to count set bits. This function name is __builtin_popcount(). Consider the below C program.
#include<stdio.h>
// C Program to count number of set bits
// using __builtin_popcount
int main()
{
unsigned int i = 23;
printf("%d", __builtin_popcount(i));
return 0;
}
Output: 4
Using std::bitset::count function:
If you are writing the C++ program to count the set bits, then you can also use std::bitset::count. It returns the total number of set bits in a bitset. Consider the below C++ code.
/**
C++ Program to count number of set bits
using the std::bitset::count
*/
#include <iostream>
#include <bitset>
int main()
{
int n = 23;
std::bitset<8> c(n);
std::cout << c.count() << std::endl;
return 0;
}
Output: 4
Counting bits set in 32-bit words using 64-bit instructions:
This approach requires a 64-bit CPU with fast modulus division to be efficient. This method takes 15 operations. The code counts the set bits in the given unsigned 32-bit integer “n” with the help of mathematical operation using the predefined magic numbers.
#include<stdio.h>
/*
Function to Counting bits set
in 32-bit words using 64-bit instructions:
*/
unsigned int countSetBits(unsigned int n)
{
unsigned int c = 0;
const unsigned long long int MAGIC_NUMBER_1= 0x1001001001001ULL;
const unsigned long long int MAGIC_NUMBER_2= 0x84210842108421ULL;
c = ((n & 0xfff) * MAGIC_NUMBER_1 & MAGIC_NUMBER_2) % 0x1f;
c += (((n & 0xfff000) >> 12) * MAGIC_NUMBER_1 & MAGIC_NUMBER_2) % 0x1f;
c += ((n >> 24) * MAGIC_NUMBER_1 & MAGIC_NUMBER_2) % 0x1f;
return c;
}
// C Program to check function countSetBits
int main()
{
unsigned int i = 15;
printf("%d", countSetBits(i));
return 0;
}
Output: 4
Counting bits set, in parallel:
This also best method for counting set bits in a 32-bit integer.
#include<stdio.h>
/*
Function to Counting bits set,
in parallel:
*/
unsigned int countSetBits(unsigned int n)
{
unsigned int cnt = 0;
// reuse n (input) as temporary container
n = n - ((n >> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
cnt = ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
return cnt;
}
// C Program to check function countSetBits
int main()
{
unsigned int i = 15;
printf("%d", countSetBits(i));
return 0;
}
Output: 4
Recommended Post
- How to set, clear or toggle a single bit in C/C++?
- Turn off the rightmost set bit.
- Count set bits using the lookup table.
- Macros for Bit Manipulation in C/C++.
- 5 Ways to Check if Two Integers have Opposite Signs.
- C Program to Find whether a given integer is a power of three or not.
- Operator Precedence And Associativity In C.
- Operators in C language
References: https://graphics.stanford.edu/~seander/bithacks.html