Calculate numbers used from a sequence

Question

I got the following sequence of numbers 1,2,4,8,16,32,64....8192 - where each of the numbers represent something, like 1 could represent "Milk", and 2 could represent "Egg".

I got a cupcake with the value of 3. Since 1 + 2 = 3, I know that my cupcake contains both milk(1) and eggs(2).

However - I'm looking for an algorithm to help me achieve this. If the sum is 1536 I would like the algorithm to find 1024 and 512 - or, if the sum is 7 - numbers used would be: 1,2,4.

Is there a way to do this?

Answer 1

Let's see if I understood, you have a sequence that is basically "binary" (power of 2) values, ex:

32---16---8----4----2-----1

0----0----0----1----1-----0 is 6

So you can go ahead and convert your input number (which is an int) to binary and then go bit by bit checking if they are turned on.

So lets say you have the number 35, to binary:

32---16---8----4----2-----1

1----0----0----0----1-----1

I will go bit by bit now

• Bit index 1 is turned on, so I have 1!
• Bit index 2 is turned on, so I have 2!
• Bit index 3 is turned off, skip!
• Bit index 4 is turned off, skip!
• Bit index 5 is turned off, skip!
• Bit index 6 is turned on, I have 32!

Result: 1 + 2 + 32 = 35

Hope this helps! :)

Answer 2

In a modern computer, integers are already represented in binary. You can take advantage of that by using bitwise operations (pseudocode):

for p := 30 downto 0:
    if (x and (1 shl p)) > 0:
        output (1 shl p)

For example, given x = 100₁₀ = 1100100₂, the program will output 64, 32 and 4.

Here, shl is a shift operation and and is bitwise AND.