Given an integer, count its set bits.

For example,

**Input: ** n = -1 (11..1111)

**Output: **The number of set bits in -1 is 32

**Input: ** n = 16 (00001000)

**Output: **The number of set bits in 16 is 1

A simple solution would be to consider every bit (set or unset) till last set bit in a number and maintain a counter to count set bits.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> #include <bitset> using namespace std; // Naive solution to count number of set bits in n int numOfSetBits(int n) { int count = 0; for (; n; n >>= 1) count += (n & 1); // check last bit return count; } // main function int main() { int n = 16; cout << n << " in binary is " << bitset<8>(n) << endl; cout << "The number of set bits in " << n << " is " << numOfSetBits(n) << endl; return 0; } |

`Output:`

16 in binary is 00010000

The number of set bits in 16 is 1

*The naive approach requires one iteration per bit, until no more bits are set. So on a 32-bit word with only the high set, it will go through 32 iterations.*

We can use **Brian Kernighan’s algorithm** to improve performance of above naive algorithm. The idea is to consider only set bits of the integer by turning off the rightmost set bit of given number after considering it, so next iteration of loop will consider next rightmost bit.

We know that the expression (n & (n-1)) will turn off the rightmost set bit of given number. (n-1) will have all the bits flipped after the rightmost set bit of n (including the rightmost set bit).

So (n & (n-1)) will result in last bit flipped of n.

For example, consider number 52 which is equal to 00110100 in binary and its total set bits are 3.

**1st iteration of loop: n = 52**

00110100 & (n)

00110011 (n-1)

~~~~~~~~

00110000

**2nd iteration of loop: n = 48**

00010000 & (n)

00101111 (n-1)

~~~~~~~~

00100000

**3nd iteration of loop: n = 32**

00100000 & (n)

00011111 (n-1)

~~~~~~~~

00000000 (n = 0)

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <iostream> #include <bitset> using namespace std; // Function to count number of set bits in n int numOfSetBits(int n) { // stores the total bits set in n int count = 0; for (; n; count++) n = n & (n - 1); // clear the least significant bit set return count; } // main function int main() { int n = -1; cout << n << " in binary is " << bitset<32>(n) << endl; cout << "The number of set bits in " << n << " is " << numOfSetBits(n) << endl; return 0; } |

`Output:`

-1 in binary is 11111111111111111111111111111111

The number of set bits in -1 is 32

*Brian Kernighan’s method goes through as many iterations as there are set bits. So if we have a 32-bit word with only the high bit set, then it will only go once through the loop.*

GCC also provides a built-in function int **__builtin_popcount** (unsigned int n) that returns the number of set bits in n.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 |
#include <iostream> using namespace std; // main function int main() { int n = 16; cout << "The number of set bits in " << n << " is " << __builtin_popcount (n) << endl; return 0; } |

`Output:`

The number of set bits in 16 is 1

GCC also provides two other built-in function int __builtin_popcountl (unsigned long) and int __builtin_popcountll (unsigned long long) similar to __builtin_popcount, except their argument type is unsigned long and unsigned long long respectively.

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

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> #include <bitset> using namespace std; // main function int main() { int n = 30; bitset<8> bs(n); cout << "The number of set bits in " << n << " (" << bs << ") is " << bs.count() << endl; return 0; } |

`Output:`

The number of set bits in 30 (00011110) is 4

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

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

This is a really crappy algorithm I designed one that can count 32 bits in 17 instructions maximum, constant time.

prove it nerd