Count Set Bits
Counting the number of 1 bits (set bits) in an integer is a common operation. There are several methods, from simple loops to built-in methods and the famous Brian Kernighan's algorithm.
1. Loop through bits (O(number of bits))
int count = 0;
for (int i = 0; i < 32; i++) {
if ((n & (1 << i)) != 0) count++;
}
2. Brian Kernighan's Algorithm (O(number of set bits))
Repeatedly clear the lowest set bit: n &= (n-1).
int count = 0;
while (n != 0) {
n &= (n - 1);
count++;
}
3. Using Integer.bitCount (Java built-in)
int count = Integer.bitCount(n);
Two Minute Drill
- Brian Kernighan's algorithm runs in O(number of set bits).
- Integer.bitCount uses native implementation (fast).
- Counting set bits is used in many combinatorial problems.
Need more clarification?
Drop us an email at career@quipoinfotech.com