Sometimes it can be useful to think about numbers as an array of bits. This question asks us to consider a number in that way, and then count the number of elements in that array that are “1”. The link.

The first key realization is really considering how a number is an array-of-bits. That has a lot of follow-on implications. In particular, it suggests that maybe we can write code like the following:

def count_bits(n):
    counter = 0
    for bit in n:
        if bit == 1:
            counter += 1
    return counter

This code is a solution! We would count all the bits that are 1. The issue is that key line, “for bit in n“, doesn’t really exist. How might we address this? Fortunately, I’ve seen this problem many times, or similar-enough ones, and I’ll present a solution and discuss it.

def count_bits(n):
    counter = 0
    while n > 1:
        if n % 2 == 1:
            counter += 1
        n = int(n/2)
    return counter

That was quick!

Approach

1. The if on line 4 of our solution is essentially testing the least-significant bit in n. So in that way we can look at a single bit in n, and emulate the condition in our “ideal” loop.
2. The n = int(n/2) on line 6 essentially chops off the last binary digit of n. Just as dividing a normal number by 10 (and rounding down) has the effect of trimming off the last decimal digit of a number, so too does dividing by 2 and rounding down trim off the last binary digit (i.e., the last bit) of the number.
3. That “trimming” gives us the effect of iterating through every bit of n, accessing that bit with the modulo (%) operator. In this way we can see if the rightmost bit is 1 or 0 (again, using the if statement mentioned in point 1.)

Bit-related questions don’t come up too often, but the “trick” we have here to iterate through a number as a sequence of bits is a useful staple in these bitwise questions. All bit manipulation questions so far on the sight should be collected here.