Given an unsigned 32-bit integer n, return how many of its bits are 1 (this count is also called the Hamming weight). In the tests n is passed as a plain non-negative number between 0 and 2^32 minus 1.
1011 in binary, which has three 1 bits.11111111111111111111111111111101: every bit except one is set.- 0 <= n <= 2^32 - 1 (an unsigned 32-bit value)
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The simple approach checks all 32 bits: test n & 1, then shift right. That is fine, but there is a classic trick. Subtracting 1 from n flips the lowest 1 bit to 0 and all the 0 bits below it to 1, so n & (n - 1) removes exactly the lowest set bit. Repeating this until n is 0 runs once per 1 bit. Java note: Java has no unsigned int, so a value like 4294967293 arrives as the negative int -3 with the same 32 bits. The trick still works because n & (n - 1) only looks at bits; if you shift instead, use the unsigned shift >>> so the sign bit does not get copied in.
Algorithm
- Set
count = 0. - While
n != 0: don &= n - 1andcount += 1. - Return
count.
O(k), where k is the number of 1 bits (at most 32)Space: O(1)n >> 1 and a check n > 0 never handles negative inputs correctly: >> keeps the sign bit, and -3 > 0 is false. Use n != 0 together with >>> or the n & (n - 1) trick.class Solution: def hammingWeight(self, n: int) -> int: count = 0 while n: n &= n - 1 # clear the lowest set bit count += 1 return count