Count Set Bits
Count Number of Set Bits in C++
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;
}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
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:
Counting set bits is essential for many bit manipulation problems.
---
2. Header Files Used
---
3. Understanding Set Bits
Set Bit Concept
:
Applications
:
---
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
:
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
:
Time Complexity
: O(number of set bits)
Why Efficient
:
---
6. Method 3: Built-in Function
Using __builtin_popcount()
:
int count = __builtin_popcount(num);
How it works
:
Note
:
---
7. When to Use Each Method
Method 1 (Loop)
:
Method 2 (Brian Kernighan's)
:
Method 3 (Built-in)
:
---
8. Important Considerations
Efficiency
:
Portability
:
Edge Cases
:
---
9. return 0;
This ends the program successfully.
---
Summary
This program is fundamental for learning efficient bit manipulation, understanding algorithm optimization, and preparing for advanced bit manipulation problems in C++ programs.
Let us now understand every line and the components of the above program.
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.
Practical Learning Notes for Count Set Bits
This C++ program is part of the "Bitwise Operations Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.
A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.
For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.