Q1: How do you count the number of set bits (1s) in an integer using Brian Kernighan's Algorithm?
Brian Kernighan's Algorithm repeatedly clears the lowest set bit of an integer n using the bitwise operation n = n & (n - 1). Each iteration flips the rightmost set bit to 0, running in $O(k)$ time where $k$ is the number of set bits.
Brian Kernighan's Bit Counting
public class BitCount {
public static int countSetBits(int n) {
int count = 0;
while (n != 0) {
n = n & (n - 1); // Clears rightmost set bit
count++;
}
return count;
}
}💡 Flips the lowest set bit in each iteration until the number becomes zero.
Key Takeaways
n & (n - 1)clears the rightmost set bit in $O(1)$ time.- Total iterations equal the count of set bits rather than total bits ($32$ or $64$).
Knowledge Check
What is the result of applying n & (n - 1) to n = 12 (binary 1100)?