Count Set Bits
Count Number of Set Bits in C++
IntermediateTopic: Bitwise Operations Programs
C++ Count Set Bits Program
This program helps you to learn the fundamental structure and syntax of C++ programming.
#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
Understanding Count Set Bits
Count set bits: 1) Loop through bits and count, 2) Brian Kernighan's algorithm: num &= (num-1) clears rightmost set bit, 3) Built-in __builtin_popcount() (GCC). Brian Kernighan's algorithm is efficient: O(number of set bits) instead of O(total bits). Used in bit manipulation problems.
Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.