Number of 1 Bits

The problem

A computer stores a whole number in binary: as a row of bits, each 0 or 1. From the right, the bits are worth 1, 2, 4, 8 and so on. n is never negative and fits in 32 bits. Return how many of those 32 bits are 1. When n is 0 no bit is 1, so the answer is 0. When all 32 bits are 1, the answer is 32.

What to write

function solve(n: number): number

Input
n = 11

Output
3

Input
n = 128

Output
1

Constraints

0 ≤ n ≤ 4294967295.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   n has only 32 bits, so even a method that spends one round on every bit takes 32 rounds at most. Speed is not the hard part. The largest n has all 32 bits on. Make sure your method still counts right when the leftmost of the 32, the top bit, is 1.

2. Hint 2: Ask a smaller question

   Write 12 in binary: 1100. Now write 11, which is 12 minus 1: 1011. Which bits changed and which stayed the same? Try 10 and 9 as well: 1010 and 1001. What does subtracting 1 always do to the rightmost 1 and to the 0s on its right?

3. Hint 3: Name the pattern

   AND, written &, compares two numbers bit by bit and keeps a 1 only where both have one. Subtracting 1 flips the rightmost 1, called the lowest 1 bit, and the 0s to its right. So a number AND the number one smaller loses only that bit: 1100 & 1011 = 1000. Questions about single bits signal bit manipulation. Read the lesson on bit manipulation.

4. Hint 4: State the invariant

   The count plus the number of 1 bits still in the working value always equals the number of 1 bits n began with. Each round moves exactly one bit from the value to the count. When the value reaches 0 nothing is left in it, so the count is the answer.

5. Hint 5: Sketch the pseudocode

   Set count to 0 and value to n. While value is not 0: replace value with value AND (value - 1), then add 1 to count. Return count. Test for 0 before every round, the first one too, so that an n of 0 returns 0.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

While the value is not 0, replace it with value & (value - 1), an AND that clears its lowest 1 bit, and add 1 to a count. That is one round for each 1 bit.

The slow way

Look at one place per round: test the lowest bit, the one furthest right, then shift the number one place to the right, which drops that bit and moves every other bit one place right. Stop when the number is 0. It is correct and takes at most 32 rounds. But it spends rounds on 0s as well: 128 has a single 1 bit and takes 8 rounds.

The insight

Subtracting 1 changes only the right end of a number: the rightmost 1, called the lowest 1 bit or lowest set bit, becomes 0, and every 0 to its right becomes 1. 12 is 1100 and 11 is 1011. AND, written &, keeps a 1 only where both numbers have one, so 1100 & 1011 = 1000. Only the lowest 1 bit is gone.

Step by step

1. Start the count of 1 bits at 0. No bit has been counted yet. If n is 0 the loop below never runs, and this 0 is returned as the answer.
2. Copy n into a working value of 32 bits. The loop wears this copy down to 0. For every n inside the limits the copy equals n. Reading 32 bits only matters outside them: without it, a negative number would keep Python's loop running forever.
3. Repeat while the working value still has a 1 bit. A number is 0 exactly when every one of its bits is 0. So a value that is not 0 still holds at least one 1 bit that has not been counted.
4. Clear the lowest 1 bit: AND the value with itself minus 1. Subtracting 1 turns the lowest 1 bit into 0 and the 0s to its right into 1s. AND keeps a 1 only where both numbers have one, so that one bit disappears and every other bit stays.
5. Count the bit that was cleared. Each round removes exactly one 1 bit, never more and never fewer. So the number of rounds is the number of 1 bits.
6. Return the count. The value is 0, so every 1 bit of n has been cleared, and each one added 1 to the count on its way out.

The same numbered steps are the comments in each solution.

function solve(n) {
  // 1. Start the count of 1 bits at 0
  let count = 0;
  // 2. Copy n into a working value of 32 bits
  // >>> 0 reads the low 32 bits as a number that is never negative.
  let bits = n >>> 0;
  // 3. Repeat while the working value still has a 1 bit
  while (bits !== 0) {
    // 4. Clear the lowest 1 bit: AND the value with itself minus 1
    // & can give a negative number here; >>> 0 makes it never negative again.
    bits = (bits & (bits - 1)) >>> 0;
    // 5. Count the bit that was cleared
    count++;
  }
  // 6. Return the count
  return count;
}

function solve(n: number): number {
  // 1. Start the count of 1 bits at 0
  let count = 0;
  // 2. Copy n into a working value of 32 bits
  // >>> 0 reads the low 32 bits as a number that is never negative.
  let bits = n >>> 0;
  // 3. Repeat while the working value still has a 1 bit
  while (bits !== 0) {
    // 4. Clear the lowest 1 bit: AND the value with itself minus 1
    // & can give a negative number here; >>> 0 makes it never negative again.
    bits = (bits & (bits - 1)) >>> 0;
    // 5. Count the bit that was cleared
    count++;
  }
  // 6. Return the count
  return count;
}

def solve(n):
    # 1. Start the count of 1 bits at 0
    count = 0
    # 2. Copy n into a working value of 32 bits
    # Python integers have no fixed width. 0xFFFFFFFF is 32 one bits,
    # so & keeps the low 32 bits of n.
    bits = n & 0xFFFFFFFF
    # 3. Repeat while the working value still has a 1 bit
    while bits != 0:
        # 4. Clear the lowest 1 bit: AND the value with itself minus 1
        bits &= bits - 1
        # 5. Count the bit that was cleared
        count += 1
    # 6. Return the count
    return count

Example 1, traced

Input
n = 11

Output
3

Why it works

Clearing the lowest 1 bit removes one 1 bit and touches nothing else, so every round takes the working value exactly one 1 bit closer to 0. The count goes up by 1 in the same round. The value starts with the 1 bits of n and ends with none, so the count ends at the number of 1 bits in n.

Time and space

Time O(number of set bits), at most 32, extra space O(1). The loop runs once for each set bit, meaning each 1 bit, not once for each place: 128 takes 1 round. A 32-bit number has at most 32 of them. Two numbers are kept, the working value and the count, so the extra space is O(1).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• In JavaScript, the slow way above must shift with >>>, which fills the leftmost place with 0. The other right shift, >>, refills it with 1 when it was 1, so 4294967295 never reaches 0 and the loop never ends.
• JavaScript's & gives a negative result when the leftmost of the 32 bits stays on: 4294967295 & 4294967294 is -2. A loop that tests for greater than 0 stops there and returns 1, not 32. Test for not 0 instead.
• Test for 0 before the first round, in either language. A loop that clears a bit first and only then tests counts 1 for an n of 0, which has no 1 bit at all.

Pattern

Bit manipulation. Builds on Single Number.

Keep going