C++
#include <iostream>
#include <bitset>
using namespace std;
// Method 1: Using loop
int countSetBits1(int num) {
int count = 0;
while (num) {
count += num & 1;
num >>= 1;
}
return count;
}
// Method 2: Using Brian Kernighan's algorithm
int countSetBits2(int num) {
int count = 0;
while (num) {
num &= (num - 1); // Clears the rightmost set bit
count++;
}
return count;
}
// Method 3: Using built-in function (GCC)
int countSetBits3(int num) {
return __builtin_popcount(num);
}
int main() {
int numbers[] = {12, 15, 255, 1024, 7};
cout << "Counting set bits:" << endl;
for (int num : numbers) {
cout << "\nNumber: " << bitset<16>(num) << " (" << num << ")" << endl;
cout << "Method 1: " << countSetBits1(num) << " set bits" << endl;
cout << "Method 2: " << countSetBits2(num) << " set bits" << endl;
cout << "Method 3: " << countSetBits3(num) << " set bits" << endl;
}
return 0;
}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
This program teaches you how to Count Set Bits (number of 1s) in a number in C++. Counting set bits is a common operation in bit manipulation problems. Multiple methods are available, with Brian Kernighan's algorithm being particularly efficient.
1. What This Program Does
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.
2. Header Files Used
-
#include <iostream>
- Provides cout and cin for input/output operations.
-
#include <bitset>
- Provides bitset for binary representation display.
3. 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
4. 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)
5. 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
6. 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
7. 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
8. 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
9. return 0;
This ends the program successfully.
Summary
- Count set bits: number of 1s in binary representation.
- Method 1: loop through bits - O(total bits), simple and portable.
- Method 2: Brian Kernighan's algorithm - O(set bits), efficient and recommended.
- Method 3: __builtin_popcount() - hardware optimized, GCC/Clang specific.
- Understanding set bit counting enables efficient bit manipulation.
- Essential for bit manipulation problems, cryptography, and optimization.
This program is fundamental for learning efficient bit manipulation, understanding algorithm optimization, and preparing for advanced bit manipulation problems in C++ programs.