Take the 2-minute tour ×

Ok , I just worked out that every natural number can be expressed as sum of powers of 2, eg: (9 = 2^3 + 2 ^0). I am looking for an algorithm which does the splitting of natural number into powers of 2 efficiently.

share|improve this question

closed as unclear what you're asking by Kuba, Yves Klett, Mr.Wizard Feb 3 at 12:34


Is this related to Mathematica? If so you may be interested in IntegerDigits[9, 2] –  Kuba Feb 3 at 9:38

1 Answer 1

As mentioned in the comment above, IntegerDigits[] does the trick in Mathematica. If you are more interested in an algorithm, you can use the bit-wise AND function to look for the powers of two that make up your number:

BitAnd[ 9, 2^#] & /@ Range[8, 0, -1]

and then put a '1' wherever that list doesn't have a '0':

% /. n_ /; n != 0 -> 1

You can improve the speed a bit by not calculating the powers of 2, but by shifting the bit in the test pattern to the right position:

BitAnd[ 9, BitShiftLeft[1, #]] & /@ Range[ 8, 0, -1]

Or you can bitshift the number-under-test to the right and compare with '1' and reverse the result:

BitAnd[ BitShiftRight[9, #], 1] & /@ Range[0, 8]

As usual, there is more than just one way to skin this particular cat...

share|improve this answer
