Find the number of 1's in the binary representation of a number

Examples

$$5_{10} \to 101_2 = 2$$ $$120_{10} \to 1111000_2 = 4$$ In order to solve this problem, the first thing we must do is establish what the input type will be. Let's say it's an integer (meaning base 32). We can iterate through the number, and add up the ones. For example, let's look at 120 (or 1111000) in more detail. $$\text{Number: }1111000\text{, is the last digit 1? } \text{No.}$$ $$\text{Number: }111100\text{, is the last digit 1? } \text{No.}$$ $$\text{Number: }11110\text{, is the last digit 1? } \text{No.}$$ $$\text{Number: }1111\text{, is the last digit 1? } \boxed{\text{Yes!}}$$ $$\text{Number: }111\text{, is the last digit 1? } \boxed{\text{Yes!}}$$ $$\text{Number: }11\text{, is the last digit 1? } \boxed{\text{Yes!}}$$ $$\text{Number: }1\text{, is the last digit 1? } \boxed{\text{Yes!}}$$ At this point the number is 0, so we're finished. There are 3 zeroes.

Code

We just follow the same logic we described before.

def ones(integer):
    count = 0
    while integer > 0:
        count += integer & 1
        integer >>= 1
    return count

Variation on the Problem

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example

Input: 5
Output: [0,1,1,2,1,2]

Logic

Let’s establish this fact: worst case scenario, we can calculate the value of ones at each point. However, we’re wasting information!

For example, $$\text{Ones}(11100_2) = \text{Ones}(1110_2) = \text{Ones}(111_2) = 3$$ $$\begin{align}\text{Ones}(111_2) \begin{aligned}= 1 + \text{Ones}(110_2) \end{aligned}\\ \begin{aligned} = 1 + \text{Ones}(11_2) \end{aligned}\\= \begin{aligned}2 + \text{Ones}(10_2) \end{aligned}\\= 2 + \text{Ones}(1_2) \\= 3 + \text{Ones}(0)\\ = 3\end{align}$$ We don't actually have to go back down to 0 each time. If we're calculating $\text{One}(111)$, we already have the value of $\text{One}(110)$.

Step 1: Decent Solution

def countBits(self, n):
        j = [0]
        for i in range(1,n+1):
            if i%2 == 1: #If odd, subtract 1
                j.append(j[-1] + 1)
            else: #If even, divide by 2
                j.append(j[i>>1])
        return j

This is pretty good, but it turns out you don’t even need cases.

n & n-1

Let's look at this operation $n \& (n-1)$. $$\begin{align} & 1010000 \\ \& & 1001111 \\ \hline & 1000000 \end{align}$$ I'm going to do a few more examples, and maybe you can find a pattern. $$\begin{align} & 1010100 \\ \& & 1010011 \\ \hline & 1010000 \end{align}$$ $$\begin{align} & 1010101 \\ \& & 1010100 \\ \hline & 1010100 \end{align}$$ Maybe you noticed this, but the operation cleared the last 1. Therefore, the result of $n\&(n-1)$ has one fewer 1 than $n$.

Better Solution

def countBits(self, n):
        j = [0]
        for i in range(1,n+1):
            j.append(j[i&(i-1)] + 1)
        return j