Set bits are the 1s present in the binary representation of a number. Counting set bits is a common problem in computer science, especially in fields such as cryptography, error detection, and low-level programming. In this article, we will explore three approaches: simple bitwise shifting, Brian Kernighan’s algorithm, and the built-in GCC function.
Understanding The Problem
Every integer in C can be represented in binary form. For example, the decimal number 5 is 101 in binary, which has two set bits. The goal is to count the number of 1s in the binary representation using different methods.
Program 1: Using Bitwise Operators and Shifting
In this approach, we check each bit individually by performing an AND with 1 and then right-shifting the number until it becomes zero.
#include <stdio.h>
int main() {
int n, count = 0;
printf("Enter an integer: ");
scanf("%d", &n);
while (n > 0) {
if (n & 1) {
count++;
}
n = n >> 1;
}
printf("Number of set bits: %d\n", count);
return 0;
}This method checks each bit one by one, incrementing the count when a 1 is found. It is straightforward and easy to understand for beginners.
Program 2: Using Brian Kernighan’s Algorithm
This method removes the lowest set bit in each iteration using n = n & (n - 1). The loop runs only as many times as there are set bits.
#include <stdio.h>
int main() {
int n, count = 0;
printf("Enter an integer: ");
scanf("%d", &n);
while (n > 0) {
n = n & (n - 1);
count++;
}
printf("Number of set bits: %d\n", count);
return 0;
}By clearing the lowest set bit in every iteration, this method is faster than checking all bits individually, especially for numbers with fewer set bits.
Program 3: Using GCC Built-in Function
GCC provides a built-in function __builtin_popcount() to count the number of set bits directly. This approach is extremely concise and efficient.
#include <stdio.h>
int main() {
int n;
printf("Enter an integer: ");
scanf("%d", &n);
int count = __builtin_popcount(n);
printf("Number of set bits: %d\n", count);
return 0;
}Here, the compiler handles all the bit manipulation internally. This is the easiest and fastest method if your compiler supports it.
FAQs
Q1: Which method is fastest?
The GCC built-in function is usually the fastest, followed by Brian Kernighan’s algorithm. The bitwise shifting method is slower for numbers with many bits.
Q2: Are these methods portable?
The first two methods work on all standard C compilers. The built-in function is compiler-specific (GCC/Clang).
Q3: Can negative numbers be handled?
For unsigned integers, all three methods work reliably. For signed numbers, results may vary depending on how the compiler handles right shifts.
Conclusion
Counting set bits can be done in multiple ways, from manual bitwise operations to compiler-provided built-in functions. Understanding all three approaches helps in learning low-level binary operations, algorithm optimization, and writing efficient C programs.
References & Additional Resources
- C Programming Tutorial – Introduces C basics including operators and bitwise logic.
- GeeksforGeeks – Count Set Bits – Explains multiple methods for counting set bits.
- TutorialsPoint – Bitwise Operators in C – Detailed explanation of bitwise operators with examples.
