Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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 '14 at 12:34

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

Is this related to Mathematica? If so you may be interested in IntegerDigits[9, 2] –  Kuba Feb 3 '14 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

Not the answer you're looking for? Browse other questions tagged or ask your own question.