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.

Answer 3

You could continue taking the log base 2 of the number until you reach a number evenly divisible by 2^(log base 2 of that number)

Example:

• 1536
• log_2(1536) = 10 (so, add 2¹⁰ = 1024 to your list)
• remainder = 1536 - 1024 = 512
• log_2(512) = 9 (so, add 2⁹ = 512 to your list)
• remainder = 512 - 512 = 0
• so your list contains 1024 and 512

Working Python:

import math
goal = int(raw_input("Enter a goal"))
solution = []
while(goal > 0):
    nextExponent = int(math.log(goal)/math.log(2))
    goal -= 2**nextExponent
    solution.append(2**nextExponent)
print solution

If your set of powers of 2 is limited, you will have to cap nextExponent at the maximum.

Sample input:

Enter a goal 58094

Output:

[32768, 16384, 8192, 512, 128, 64, 32, 8, 4, 2]