Example 1
ready- Input
n = 11- Expected
3- Why
- 11 is 1011 in binary, which has three set bits
Number of 1 Bits
25 min · hammingWeight()A permissions mask can pack dozens of yes-or-no flags into one integer. To learn how many permissions are active, you count the switches that are on.
Given a non-negative integer n, return the number of 1s in its binary
representation. A set bit is a binary position whose value is 1.
Keep these details in view:
nis a plain non-negative integer, not a binary string.- Leading zeroes don't change the count.
- The input stays below
2^31, so it fits in a signed 32-bit wire value.
Constraints
0 <= n < 2^31- Equivalently,
0 <= n <= 2_147_483_647.
Hints
Inspect one position
n & 1 tells you whether the lowest bit is set. An unsigned right shift then brings
the next bit into that position.
Skip the zeroes
Subtracting one from a positive binary number flips its lowest 1 to 0 and turns
the zeroes below it into 1s. What survives when you AND the two values?
One set bit per round
Replacing n with n & (n - 1) clears exactly its lowest set bit. Count how many
replacements it takes to reach zero.
Follow-up
Can you make the number of loop iterations depend on the number of set bits rather than on all 32 possible positions?
Visible cases
Examples
Example 2
ready- Input
n = 128- Expected
1- Why
- a power of two has exactly one set bit
Example 3
ready- Input
n = 0- Expected
0- Why
- zero has no set bits
Interview signal
Asked at
AmazonApple
Shift and test
Inspect the lowest bit with n & 1, add that bit to the count, then shift right. Doing
this 32 times covers every position in the 32-bit value, including leading zeroes.
def hamming_weight(n: int) -> int:
count = 0
for _ in range(32):
count += n & 1
n >>= 1
return countTime O(32). Space O(1) — the width is fixed, so this is also constant time.
Clear the lowest 1
There is a sharper move. For a positive number, n - 1 changes the lowest set bit to
zero and flips every lower zero to one. ANDing that result with the original keeps all
higher bits but clears that one lowest set bit:
def hamming_weight(n: int) -> int:
count = 0
while n:
n &= n - 1
count += 1
return countEach round removes one set bit, so the loop runs exactly k times, where k is the
answer. This count is also called the population count (popcount) — the number of
set bits in a value.
Time O(k). Space O(1), with k <= 31 under these input constraints.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
3
Run: visible + custom · Submit: full suite