Is there an algorithm to split a number into the sum of powers of 2?

Question

Am I able to split, lets say 76, into the sum of powers of two, through an algorithm and without cycling through possible combinations?

For the example above, the answer would be '2^6+2^3+2^2' or just simply the exponents, so '6,3,2'

Thanks in advance.

Answer 1

Make successive divisions by $2$ and note the remainders, until the quotient is $0$: $$\begin{array}{r|cc} 76&0\\38&0\\19&1\\9&1&\uparrow\\4&0\\2&0\\1&1 \end{array}$$ The binary digits of $76$ are $\;\color{red}{1001100}_2$. In other words $$76=2^6+2^3+2^2.$$

This is because, if you write the Euclidean division equalities for each of these divisions, you have (Horner scheme) \begin{align*} 76&=2\cdot 38 =2(2\cdot 19))=2(2(2\cdot 9+1))=2(2(2(2\cdot 4+1)+1)) \\&=2(2(2(2(2\cdot 2)+1)+1))=2(2(2(2(2(2\cdot 1))+1)+1)) \end{align*}

Answer 2

Hint: if you are seriously asking whether there is an algorithm for calculating the binary representation of a number, then the answer is yes. Google for "radix conversion" to learn more.

Answer 3

$log_2 76 ≈ 6.248$

$\lfloor log_2 76 \rfloor =$ 6

$76-2^{6}=12$

$log_2 12 ≈ 3.585$

$\lfloor log_2 12 \rfloor =$ 3

$12-2^3 = 4$

$log_2 4 =$ 2