# 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

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
• @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