# Finding which of six numbers was used to make its sum

I have $6$ numbers: $C_1 = 1$, $C_2 = 2$, $C_3 = 4$, $C_4 = 8$, $C_5 = 16$, $C_6 = 32$ They could also be seen as $2^i$. If I am given a sum that is made up of some or all or none of these $6$ numbers (Not repeating) and I would like to find out which of the six numbers were used to make the sum. Example:

C1          C2          C3          C4          C5          C6          SUM

0           0           0           0           16          32          48

1           0           0           0           16          32          49

0           2           0           0           16          32          50

• Please see this tutorial for information about how to format mathematics on this site. Note that $C_k = 2^{k - 1}$ for $1 \leq k \leq 6$. – N. F. Taussig Apr 4 '15 at 9:28

## 2 Answers

You can use division with remainder to determine how to express the number as a sum of powers of $2$. We begin by dividing the number by the highest power of $2$ less than the number. If there is a non-zero remainder, we divide the remainder by the highest power of $2$ less than the remainder. We continue until the remainder is $0$. The number is then the sum of the quotients. For example, \begin{align*} 48 & = 1 \cdot 32 + 16 & 53 & = 1 \cdot 32 + 21\\ 16 & = 1 \cdot 16 & 21 & = 1 \cdot 16 + 5\\ & & 5 & = 1 \cdot 4 + 1\\ & & 1 & = 1 \cdot 1 \end{align*} Hence, $48 = 32 + 16$, while $53 = 32 + 16 + 4 + 1$.

• or divide by 2 each time, until the quotient is 0, so you don't have to search for "the highest power of 2 less than the number". If the remainder of the $i$-th division is 0, then the $i$-th summand is not present, and if the remainder is 1, then it's present. – rewritten Apr 4 '15 at 10:03

Write the number in base 2 and check which digits are 1.

• Could you give an example? – joe Apr 4 '15 at 9:39
• @joe The base $2$ representation of $48$ is $110000$, while the base $2$ representation of $53$ is $110101$. Reading $110101$ from right to left tells us that the corresponding decimal is $1 \cdot 2^0 + 0 \cdot 2^1 + 1 \cdot 2^2 + 0 \cdot 2^3 + 1 \cdot 2^4 + 1 \cdot 2^5 = 1 + 4 + 16 + 32 = 53$. To obtain the binary representation, you follow the procedure I outlined above, then place a $1$ whenever the corresponding power of $2$ is a quotient and a $0$ otherwise. – N. F. Taussig Apr 4 '15 at 9:55
• Just curious, how come it is read from right to left and not the other way around? – joe Apr 4 '15 at 21:42
• Think about base 10, if you read the number 345 from right to left, you can say "5 units, 4 tens, and 3 hundreds". In base 2 is the same, but the "powers" are the units, twos, fours, eights, sixteens, ... and you can't have more than one of each (because two of them would make an overflow onto the next digit) – rewritten Apr 5 '15 at 8:37