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

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'

• Do you know what the binary representation of a number is? – blst Nov 30 '15 at 22:37
• If the number is $n$, start with an empty list $L$, compute $n \mod 2$, prepend that to the list, compute $n \leftarrow \lfloor n / 2 \rfloor$, and repeat until $n$ is 0. Then $L$ has the binary representation of $n$. – Reinstate Monica Nov 30 '15 at 22:38
• If you're considering a positive integer as a "number", then you're simply looking for the base-2 (binary) representation of it. In general, you can "split" a number into powers of $b$ where $b$ is some positive integer $\gt 1$ by writing the base-$b$ representation of the number. – learner Nov 30 '15 at 22:39

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*}

$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

• Could you explain the method for the first step, please? – Rob Arthan Nov 30 '15 at 22:47
• Basically, if the log base 2 of a number is between the integers "x" and "x+1", then the original number was between $2^x$ and $2^{x+1},$ and thus the largest power of 2 that you want to look at will be $2^x.$ The fact that the log base 2 of 76, for example, is between 6 and 7 means that 76 is between $2^6$ and $2^7$, and thus the largest power you are looking at in the first step is $2^6$ – Simpson17866 Nov 30 '15 at 22:51
• A simpler way to do it : $$\begin{array}{c|c|c}2&76&0\\ \hline 2&38&0\\ \hline 2&19&1\\ \hline 2&9&1\\ \hline 2&4&0\\ \hline 2&2&0\\ \hline &1\end{array}$$ The leftest column represents the divisor, the middle the dividend and the rightest column represents remainder after division. The binary representation would be the remainders piled up from bottom to top. – learner Nov 30 '15 at 22:51
• Well then. I can't believe I've never seen that one before, but I like it :) – Simpson17866 Nov 30 '15 at 22:56
• @Simpson17866: I apologise. I am old and English and was being a little ironic (as old English people sometimes are). I think you did your first step with a calculator. That doesn't really give an algorithm to solve the problem unless we find out the algorithm your calculator uses to calculate logs. I am glad you appreciated learner's comment that shows how you could do it without a calculator. – Rob Arthan Nov 30 '15 at 23:02

The algorithm is as follows in python - you just iterate through the remainder - works for any base (radix) not just 2 :

def deconstruct(aNum, aBase):
primeComps = []  #initialise array to hold the indexes
num = aNum
while num >= 1:
index = int(math.floor(math.log(num,aBase)))
#index = ilog(num,aBase)
num = num - (aBase ** index)
primeComps.append(int(index)) # append each index into the array
return primeComps


note instead of using the floor of the log to some radix

you can calculate the ilog, which is still based on the old idea of divide by 2 or divide by some radix - the ilog or index returned is the count of the quotients

def ilog(aNum, aBase):
count = 0
temp = aNum
while temp >= (aBase):
count = count + 1
temp = temp/aBase
return count


A very useful algorithm for information security - if anyone wants to know why I can explain

## C# function for split the given number into sum of power of 2

 public static List<long> GetSumOfPowerOfTwo(long n)
{

var reminders = new List<int>();
var powerOfTwo = new List<long>();
while (n > 0)
{