Counting the number of 1 bits in a binary number (also know as the Hamming Weight) is a fundamental problem in computer science. It’s a basic operation often used in error detection, network routing, cryptography. The task is simple: given an integer, count how many bits are set to 1 in its binary representation.
Brute Force Approach
public int hammingWeight(int n) {
int count = 0;
for (int i = 0; i < 32; i++) { // Assuming a 32-bit integer
if ((n & 1) == 1) { // Check if the last bit is 1
count++;
}
n >>= 1; // Shift bits to the right
}
return count;
}- Initialize a count variable to store the number of 1 bits encountered during the iteration.
- Loop 32 times (once for each bit in the 32-bit integer.
- Check if the last bit is 1 using bitwise AND
This approach systematically inspects each bit, counting the ones. While straightforward, it takes O(32) operations for a 32-bit integer, regardless of how many 1 bits are present.
Optimized Algorithm
The optimized approach uses a bit manipulation trick to remove the least significant 1 bit in each iteration. This drastically reduces the number of operations needed.
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n = n & (n - 1); // Remove the least significant 1 bit
count++;
}
return count;
}- Initializes a variable count to track number of 1 bits.
- Starts a loop
- Remove least significant 1 bit
- Subtracting 1 from n flips all the bits after the least significant 1, including 1 itself.
- Performing n & (n – 1) removes this least significant 1 bit by “zeroing it out”.
- Update n with the result, effectively reducing the binary number by one 1 bit.
Why is n & (n – 1) Useful?
1. Efficiently Removes the Least Significant 1:
• Instead of checking every bit in the number, this operation directly removes the rightmost 1.
2. Counts 1 Bits:
• By repeatedly applying n & (n – 1) in a loop, you can count how many 1s are in a number’s binary representation (Hamming weight).
3. Simplifies Many Algorithms:
• Useful in problems involving bit manipulation, like:
• Subset generation.
• Checking if a number is a power of two.
• Binary toggling and masking.
Conclusion
The n & (n – 1) algorithm is a masterpiece of computational efficiency. It elegantly solves the problem of counting 1 bits by focusing only on the meaningful parts of the binary representation, skipping redundant checks. Its design aligns perfectly with LeetCode’s emphasis on clarity, efficiency, and space optimization. This algorithm not only highlights the power of bit manipulation but also teaches an important lesson: understanding the underlying structure of data (in this case, binary representation) can unlock surprisingly simple and efficient solutions to complex problems. Mastering this concept opens the door to solving a wide range of algorithmic challenges!
