decompose a number (less than 255) in a sum of powers of 2

Question

Is there a built in function that would take a number and decompose it into a sum of powers of 2? The numbers will be non negative less than 256.

For what it's worth I'm trying to understand a paper on RAID 6, which uses some Galois field in calculating the second parity (in this case) byte. There's a rule for mulitplying by 2, which is unusual in iteself, at least to me. It seems that in order to generalize mulitplication to any two bytes I would have decompose those bytes into powers of 2 and mulitply them like polynomials. Then in this case, mod them by 255.

I can write a function to do the necessary decomposition, but I thought that there might be a built in function.

Answer 1

IntegerDigits works

Try

powers = IntegerDigits[204, 2]

{1, 1, 0, 0, 1, 1, 0, 0}

Now, if you want that formatted as a sum of powers of two, you have to hold it. For example

Total@MapIndexed[#1 Defer[2]^(First@#2 - 1) &, Reverse@powers]

2^2 + 2^3 + 2^6 + 2^7

EDIT

Nicer code, given that your numbers go up to 255

pow2[num_]:=Inner[#1 2^Defer[#2] &, IntegerDigits[num, 2, 8], Range[7, 0, -1], Plus]

Answer 2

This isn't directly an answer, and I'll delete it if it is off target. But you might want to use some non-System` context functionality for taking polynomial-mod-2 products. Specifically this works with integer lists of coefficients. I'll show an example below.

In[1110]:= SeedRandom[1111];
vals = RandomInteger[2^8 - 1, 2]
intlists = Map[Reverse[IntegerDigits[#, 2]] &, vals]

Out[1111]= {19, 234}

Out[1112]= {{1, 1, 0, 0, 1}, {0, 1, 0, 1, 0, 1, 1, 1}}

Now we'll take the polynomial product and see what we recover when we convert the corresponding list to an integer, working in base 2.

In[1134]:= intproduct = Times @@ vals
polyprod = Algebra`PolynomialTimesModList[Sequence @@ intlists, 2]
FromDigits[Reverse[polyprod], 2]

Out[1134]= 4446

Out[1135]= {0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1}

Out[1136]= 3998

3998 != 4446 so we do not get the product of the original inputs. No surprise, really, because the polynomial multiplication does not allow for carries. To show that it is (plausibly) doing the correct thing, we can use a much bigger modulus, large enough to avoid overflows in this example (that is, nothing will get clipped from the modulus). When we conver that result back to an integer, we do recover the product of the original pair.

In[1137]:= polyprodbiggermod = 
 Algebra`PolynomialTimesModList[Sequence @@ intlists, 10]
FromDigits[Reverse[polyprodbiggermod], 2]

Out[1137]= {0, 1, 1, 1, 1, 2, 2, 3, 1, 1, 1, 1}

Out[1138]= 4446

Whether this Algebra` context "list polynomial" manipulation functionality is useful will depend on your actual needs. I wrote this because I'm guessing it is, but that is just a guess.