# Examples

# 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!

## 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

## Better Solution

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