Count Set Bits in C++
Count Number of Set Bits in C++.
IntermediateBitwise Operations ProgramsExample 3 of 5
count-set-bits.cpp
1#include <iostream>2#include <bitset>3using namespace std;45// Method 1: Using loop6int countSetBits1(int num) {7 int count = 0;8 while (num) {9 count += num & 1;10 num >>= 1;11 }12 return count;13}1415// Method 2: Using Brian Kernighan's algorithm16int countSetBits2(int num) {17 int count = 0;18 while (num) {19 num &= (num - 1); // Clears the rightmost set bit20 count++;21 }22 return count;23}2425// Method 3: Using built-in function (GCC)26int countSetBits3(int num) {27 return __builtin_popcount(num);28}2930int main() {31 int numbers[] = {12, 15, 255, 1024, 7};3233 cout << "Counting set bits:" << endl;34 for (int num : numbers) {35 cout << "\nNumber: " << bitset<16>(num) << " (" << num << ")" << endl;36 cout << "Method 1: " << countSetBits1(num) << " set bits" << endl;37 cout << "Method 2: " << countSetBits2(num) << " set bits" << endl;38 cout << "Method 3: " << countSetBits3(num) << " set bits" << endl;39 }4041 return 0;42}
Output
Counting set bits: Number: 0000000000001100 (12) Method 1: 2 set bits Method 2: 2 set bits Method 3: 2 set bits Number: 0000000000001111 (15) Method 1: 4 set bits Method 2: 4 set bits Method 3: 4 set bits Number: 0000000011111111 (255) Method 1: 8 set bits Method 2: 8 set bits Method 3: 8 set bits Number: 0000010000000000 (1024) Method 1: 1 set bits Method 2: 1 set bits Method 3: 1 set bits Number: 0000000000000111 (7) Method 1: 3 set bits Method 2: 3 set bits Method 3: 3 set bits
What's going on
The program demonstrates different methods to count set bits:
Method 1: Loop through all bits
Method 2: Brian Kernighan's algorithm (efficient)
Method 3: Built-in function (GCC)
Counting set bits is essential for many bit manipulation problems.
Header Files Used
1.#include <iostream>
Provides cout and cin for input/output operations.
2.#include <bitset>
Provides bitset for binary representation display.
Understanding Set Bits
Set Bit Concept
:
Set bit: bit with value 1
Clear bit: bit with value 0
Count set bits: number of 1s
Also called "population count" or "Hamming weight"
Applications
:
Bit manipulation problems
Cryptography
Error detection
Algorithm optimization
Method 1: Loop Through Bits
Algorithm
:
int count = 0;
while (num) {
count += num & 1; // Check rightmost bit
num >>= 1; // Shift right
}
How it works
:
Checks each bit from right to left
Counts bits that are 1
Shifts number right each iteration
Stops when number becomes 0
Time Complexity
: O(total bits)
Method 2: Brian Kernighan's Algorithm
Algorithm
:
int count = 0;
while (num) {
num &= (num - 1); // Clears rightmost set bit
count++;
}
How it works
:
num & (num - 1) clears rightmost set bit
Each iteration removes one set bit
Counts iterations until num becomes 0
More efficient than method 1
Time Complexity
: O(number of set bits)
Why Efficient
:
Only iterates for set bits
Skips clear bits
Fewer iterations for sparse numbers
Method 3: Built-in Function
Using __builtin_popcount()
:
int count = __builtin_popcount(num);
How it works
:
GCC built-in function
Hardware-optimized
Single instruction on many CPUs
Fastest method
Note
:
GCC/Clang specific
May not be portable
Use compiler-specific features
When to Use Each Method
Method 1 (Loop)
:
Simple and clear
Works everywhere
Easy to understand
Good for learning
Method 2 (Brian Kernighan's)
:
More efficient
O(set bits) instead of O(total bits)
Recommended for production
Good balance of efficiency and portability
Method 3 (Built-in)
:
Fastest performance
Hardware optimized
GCC/Clang only
Use when performance critical
Important Considerations
Efficiency
:
Brian Kernighan's: O(set bits)
Loop method: O(total bits)
Built-in: hardware optimized
Choose based on requirements
Portability
:
Loop: portable everywhere
Brian Kernighan's: portable
Built-in: compiler-specific
Consider portability needs
Edge Cases
:
Handle negative numbers (signed)
Zero: returns 0
Maximum value: all bits set
Test with various inputs
return 0;
This ends the program successfully.