Free Math and bits lessonsMath and bits · Stage 2 · Bits · Step 1

Read the last bit, shift it away

Count the 1s in a number's binary form with & 1 and >> 1. About 8 minutes.

Numbers are stored in binary

Computers store 13 as 1101, which means 8 + 4 + 1: a row of on/off switches called bits. You peeled decimal digits by dividing by 10. Bits peel off the same way using 2.

There are faster operators for it: AND with 1 reads the last bit, and a right shift by 1 drops it.

AND with 1: reads the last bit (1 when the number is odd).

Right shift by 1: drops the last bit.

In code

13 & 1    # 1, the last bit of 1101
13 >> 1   # 6, which is 110

n = 13, stored as 1101 (8 + 4 + 1)

n & 1

n: 13
count: 1

The lowest bit is 1. count = 1. Then shift right: n >> 1.

Move 1 of 5

Count as you peel

Keep a counter. Look at the last bit and add it to the counter: it adds 1 for an "on" switch and 0 for an "off" one. Then shift and repeat.

When the number reaches 0, every bit has been seen. A 32-bit number takes at most 32 rounds, however large its value.

Loop while positive: this version is for non-negative numbers.

In code

count = 0
while n > 0:
    count += n & 1
    n >>= 1
return count

Quick check

How many 1 bits does 13 have?

Show the answer

3. 13 = 1101 in binary: 8 + 4 + 1.

Your problem

Count the 1 bits

Return how many 1s appear in the binary form of n.

Example

n = 13 → 3

0 ≤ n ≤ 2,147,483,647

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.