Problem overview
The method hammingWeight receives a non-negative integer n and returns how many 1 bits its binary form has. This count is also called the Hamming weight.
For n = 11 the binary form is 1011, which has three 1 bits, so the result is 3. For n = 128, the binary form is 10000000, a single 1 bit, so the result is 1.
The lesson asks for O(k) time, where k is the number of 1 bits in n, and O(1) extra space.
Approach: remove the lowest 1 bit, again and again
The obvious way is to check all the bits: test the last bit, shift right, and repeat until n is 0. That takes one step per bit position, including the 0 bits. This lesson uses a trick that takes one step per 1 bit only.
Look at what subtracting 1 does to a number in binary. The lowest 1 bit turns into 0, every 0 below it turns into 1, and the bits above it stay the same. For example, 12 is 1100 and 11 is 1011. If you combine the two with a bitwise AND, which keeps a bit only where both numbers have a 1, you get 1000. The bits above the lowest 1 match in both numbers and survive. The lowest 1 bit and everything below it disagree and vanish.
So n & (n - 1) is n with its lowest 1 bit removed. Repeating it until n is 0 takes exactly as many rounds as n has 1 bits, and counting the rounds gives the answer.
Step by step
- Start a counter. Create
countand set it to 0. It will count the bits as they are removed. - Loop while
n != 0. Each pass removes one 1 bit, sonbecomes 0 right after its last 1 bit is removed. - Remove the lowest 1 bit. Set
n = n & (n - 1). This is the key line of the lesson. - Count it. Add 1 to
countin the same pass. - Return
countafter the loop.
The solution in Python
class Solution:
def hammingWeight(self, n: int) -> int:
count = 0
while n != 0:
n = n & (n - 1)
count += 1
return count
Python details worth knowing
- The parentheses are optional here, but worth keeping. In Python,
-binds tighter than&, son & n - 1means the same thing. The parentheses make the intent clear, and the order matters when+is involved:6 & 1 + 1means6 & (1 + 1), which is 2, not(6 & 1) + 1. - Python integers have no fixed width. There is no 32-bit overflow here, and
n - 1never wraps. The loop would work for numbers far beyond 31 bits too. - The loop condition could be written
while n:since 0 is false and every other integer is true. The lesson keepsn != 0because it says exactly what is meant.
Trace on n = 11
Running the solution with n = 11 (1011 in binary), n takes these values after each pass:
| Pass | n in binary after the pass | count |
|---|---|---|
| 1 | 1010 | 1 |
| 2 | 1000 | 2 |
| 3 | 0 | 3 |
The loop stops, and the method returns 3.
Complexity
Time: each pass removes one 1 bit, so the loop runs k times, where k is the number of 1 bits. For the lesson's values that is at most 31 passes. So the time is O(k). A number like 128 needs one pass even though it has eight bits.
Space: only count and n are kept, so the extra space is O(1).
Edge cases and common mistakes
- Zero. The loop never runs, and the method returns
0. - A power of two. There is one 1 bit, so the loop runs once. For
n = 128the result is1. - All bits set. For
n = 2147483645(thirty-one bits, all but one of them 1) the loop runs 30 times and the result is30. - Forgetting to update
n. Writingn & (n - 1)without assigning it back leavesnunchanged and the loop never ends. - Mixing up the operators.
&is bitwise AND. The wordandis logical and gives a different kind of result.
Testing
These results come from running the solution:
| n | Result |
|---|---|
| 0 | 0 |
| 11 | 3 |
| 128 | 1 |
| 2147483645 | 30 |
