Number of 1 Bits

Easy#191bit by bit

You get a positive integer. Count how many of its bits are 1. Our example: n = 90 = 1011010 — the answer is 4.

191 Number of 1 BitsWalkthrough · 1×

Example: n = 90 = 1011010. Each round clears the lowest 1 of n with n & (n - 1) and counts it.

n= 901011010mn - 1—countfound—
a 1 bita 0 bitthe lowest 1 of na bit that n - 1 flippedthe 1 that & just cleareda counted one

n = 90 = 1011010: 7 bits. No ones counted yet

01/19
restart · back · play · step
Speed
1function hammingWeight(n):
2 count = 0
3 while n != 0:
4 m = n - 1
5 n = n & m // clears the lowest 1
6 count = count + 1
7 return count
state
n
90 = 1011010
m
–
count
0
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Subtracting 1 borrows from the lowest 1: that 1 becomes 0, the zeros under it become 1s, and every bit above it stays the same. So n & (n - 1) is n with exactly its lowest 1 cleared.
  2. Each round clears one 1 and counts it, and the loop stops at 0, when no ones are left. So count ends equal to the number of ones.
  3. The loop runs once per 1, not once per bit: 90 has 7 bits, but the run takes 4 rounds. Reading the bits one by one would take 7, and 32 on LeetCode.

Complexity

Time O(k), where k is the number of ones: one round per 1, at most 32 on LeetCode. Memory O(1): two numbers and the count.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.