Number of 1 Bits
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Return how many bits are 1 in the binary form of a number.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What does n - 1 look like in binary compared with n?
- Hint 2How can you remove only the lowest set bit?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A row of light bulbs, some on. You want to count the lit ones. Each turn you switch off exactly the rightmost lit bulb and count one. When no bulb is lit you are done. The trick n AND (n - 1) is a one-line way of switching off the rightmost lit bulb.
- The obvious way
Check each of the 32 bits one by one: O(32).
- The key insight
While n is not 0: set n = n AND (n - 1) and add one to the count. The loop runs once per set bit.
- The algorithm
- count = 0.
- While n is not 0: n = n AND (n - 1).
- count + 1 each time.
- Return count.
Watch it run
Examplen = 11 (binary 1011)
1011 has three lit bulbs. Switch off the rightmost: 1010. Count 1.
n = 1010, count 1
Where people slip
- In Java the input is a signed int; this loop still works for negative numbers because it never shifts.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def hamming_weight(n):
count = 0
while n:
n &= n - 1 # switch off the rightmost lit bulb
count += 1
return countNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.