Number of 1 Bits - Video Solutions

Problem Overview: Given a 32-bit unsigned integer n, count how many bits are set to 1 in its binary representation. This count is often called the Hamming weight. The task focuses on efficient bit-level operations rather than converting the number to a string or using high-level utilities.

Approach 1: Iterative Bit Check (Time: O(32) ~ O(1), Space: O(1))

This method inspects each bit of the integer one by one. Use a loop while n > 0. Check the least significant bit with n & 1. If the result is 1, increment the counter. Then right-shift the number using n >> 1 to move the next bit into position. The algorithm performs at most 32 iterations for a 32-bit integer, so the runtime is effectively constant. This approach is straightforward and easy to implement during interviews when demonstrating basic bit manipulation skills.

Approach 2: Clear the Least Significant Set Bit using n & (n - 1) (Time: O(k), Space: O(1))

The expression n & (n - 1) removes the lowest set bit from a number. Each operation reduces the number of 1 bits by exactly one. Repeatedly apply this operation until n becomes 0, counting how many times it runs. If the integer contains k set bits, the loop runs exactly k times. This makes the algorithm faster when the number contains only a few set bits. The trick relies on binary arithmetic properties and is a classic technique in bit manipulation and divide and conquer-style bit reduction problems.

Recommended for interviews: Interviewers usually expect the n & (n - 1) solution. It demonstrates deeper understanding of binary representations and efficient bit tricks. The iterative bit check still shows solid fundamentals and is often a good first explanation. Moving from the basic bit scan to the optimized clearing trick signals strong problem-solving ability with low-level operations.