Number of 1 Bits
You get a non-negative integer n. Write n in binary and return how many of its digits are 1. This count is also called the number of set bits, the population count or the Hamming weight. For example, 6 is 110 in binary, so it has two 1 bits.
Function
- ninteger
- a non-negative integer that fits in a signed 32-bit int
- Returnsinteger
- the number of 1 digits in the binary form of n
Constraints
0 ≤ n ≤ 231-1
Examples
- Input
- n = 11
- Output
- 3
- Explanation
- 11 is
1011in binary, which is 8 + 2 + 1. Three of its four binary digits are 1, so the answer is 3.
- Input
- n = 128
- Output
- 1
- Explanation
- 128 is 2^7, written
10000000: a single 1 followed by zeros, so the answer is 1.
- Input
- n = 2147483645
- Output
- 30
- Explanation
- 2^31-1 = 2147483647 is thirty-one 1 bits in a row. 2147483645 is that number minus 2, which turns off the bit worth 2 and leaves 30 ones.
Follow-up
If this function ran millions of times, how could you count the bits of a 32-bit number with four lookups in a table of 256 precomputed counts?
Hints
Open them one at a time. Each one gives away a little more.
Look only at the last binary digit of
n. How can you read it without turningninto a string, and how do you then bring the next digit into last place?n & 1(orn % 2) is the last bit, and a right shift by one (or a division by 2 rounded down) removes it. Add up the last bits untilnis 0.For a shorter loop, use
n & (n-1): it isnwith its lowest 1 bit turned off. Count how many times you can apply it beforenreaches 0. The loop then runs once per 1 bit instead of once per binary digit.
Solution
Visit the binary digits of n without building a string. Reading the last bit and shifting it away takes one step per binary digit, up to 31. Clearing the lowest 1 bit with n & (n-1) takes one step per 1 bit, exactly as many as the answer.
Check the last bit and shift right
Intuition
n & 1 is the last binary digit of n: 1 when n is odd, 0 when it is even. Add it to the count. Then n >> 1 drops that digit and moves the next one into last place; for a non-negative number that is division by 2, rounded down. For 11, 1011, the last bits read 1, 1, 0 and 1 as n shrinks to 0: three 1 bits.
The loop stops when n is 0, so it never visits leading zeros: about log2(n) steps, 8 for 128 and at most 31. It stores only n and the count.
Algorithm
- Start a counter at 0.
- While
nis greater than 0, addn & 1to the counter. - Shift
nright by one bit. - When
nreaches 0, return the counter.
def hammingWeight(n):
count = 0
while n > 0:
count += n & 1 # the last bit is 1 or 0
n >>= 1 # drop the last bit
return countClear the lowest set bit with n & (n-1)
Intuition
Subtracting 1 turns the lowest 1 bit into 0 and every 0 below it into 1, and leaves the bits above unchanged. So n & (n-1) keeps the upper bits and clears the lowest 1 bit: 12 is 1100, 11 is 1011, and 1100 & 1011 is 1000.
Each step removes exactly one 1 bit, so the number of steps until n is 0 is the answer. 128 takes 1 step instead of 8, though 2^31-1 still takes 31. Lua 5.1 has no bit operators, so its version finds the lowest 1 bit by halving and subtracts it; the loop still runs once per 1 bit.
Algorithm
- Start a counter at 0.
- While
nis not 0, replacenwithn & (n-1). - Add 1 to the counter after each replacement.
- Return the counter.
def hammingWeight(n):
count = 0
while n != 0:
n &= n - 1 # turn off the lowest 1 bit
count += 1
return count
Pitfalls and edge cases
- Looping while
n > 1. The loop stops before the last 1 bit and returns 0 forn = 1. - Dividing with a float. In JavaScript, Lua and R,
11 / 2is 5.5 and the remainders that follow are fractions. Round down withMath.floor,math.flooror%/%, or shift instead. - Writing
n & 1in Lua 5.1. It has no bit operators, so the code does not compile; usen % 2andmath.floor(n / 2).
Frequently asked questions3
What is the time complexity of Number of 1 Bits?
The shift loop runs once per binary digit: O(log n), at most 31 steps here. The n & (n-1) loop runs once per 1 bit: O(k), where k is the answer. Both use O(1) extra space.
Is there a built-in function that counts set bits?
Most languages have one, often backed by a single processor instruction: Integer.bitCount in Java, __builtin_popcount in GCC, bits.OnesCount in Go, count_ones in Rust and int.bit_count in Python 3.10 and later. In an interview, write the loop and mention the built-in.
What is the difference between Hamming weight and Hamming distance?
The Hamming weight of a number is how many of its binary digits are 1, which is what this problem returns. The Hamming distance between two numbers is how many bit positions they differ in: count the 1 bits of a ^ b, since XOR sets exactly the positions where they differ.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def hammingWeight(n):
# Write code hereTest #1
Test #2
Test #3
Argument
n = 11
Expected Output
3