Home › Counting and number theory

Count the ones in a binary sum of powers of two

Each distinct power of two marks one bit

The binary form of $2^{n}$ is a one followed by $n$ zeros. A sum of different powers of two has a one at each listed exponent. Repeated exponents require carrying before you count bits.

Problem

How many ones appear in the binary representation of $4^{200} + 2^{300} + 1$ ? Also check the smaller example $2^{7} + 4$ .

Answer

The large expression has

3

ones;

2^{7} + 4

has

2

ones.

Both counts follow from distinct exponent positions, without expanding the integers.

Step-by-step solution

1. Rewrite everything as powers of two

4^{200} = (2^{2})^{200} = 2^{400}, 1 = 2^{0} .

The full expression is $2^{400} + 2^{300} + 2^{0}$ .

2. Read the bit positions

The three exponents $400$ , $300$ and $0$ are distinct, so there is a one in each of those binary positions and zero elsewhere. No carrying is needed. Thus the count is $3$ .

3. Check a smaller example

$2^{7} + 4 = 2^{7} + 2^{2}$ has a one in positions $7$ and $2$ , giving $2$ ones.

Add to Chrome - solve your own

Screenshot any problem on your screen and get the steps. Chrome on a computer; free.