How to decompose a number into powers of 2

Question

I’m using javascript for my logic:

I have a sequence of numbers: 1, 2, 4, 8, 16, 32 and so on. Given a number, which needs to be the sum of numbers in the sequence, for example: 44 (of which the value is the sum of 4+8+32). How do I know the number 44 is the sum of 4, 8 and 32?

I’ve been doing some research, and I thought I’d use radiciation. Does anyone have any suggestions on how to find the number?

Answer 1

Remember that a number on the PC is represented in binary, that is, base 2. What this means is that the number is already a sum of powers of 2 when it is on the computer.

An example:

44 = 1 x 2^5 + 1 x 2^3 + 1 x 2^2
   = 32 + 8 + 4

Soon, going from right to left, 44 in binary and 101100. Thus, to know what is the decomposition of any number in potentials of 2 we need to see which are the connected bits in their representation on basis 2.

In javascript we can do this using the following algorithm:

Passo 1) Vemos se o bit mais a direita do numero e um 1
Passo 1.1) Se for, marcamos a potencia correta de 2 como presente
Passo 2) Nos dividimos o numero por 2, o que vai fazer com que o bit mais a
         direita do numero seja descartado.
Passo 3) Se o numero for 0, pare.

So something like this:

n = 44;
power = 0;
var fatores = []
while (n != 0) {
    if ((n & 1) != 0) { 
        fatores[fatores.length] = (1 << power);
    }
    ++power;
    n >>>= 1;
}

Answer 2

To response from Lucas Virgili explains well the reasoning behind the question (which is certainly even about binary representation), but I would like to give a somewhat more general answer:

When you take any number, in the abstract, and you represent that number in a groundwork, if you are just decomposing it into a series of smaller numbers. For example:

44 = 10*4 + 1*4                            (base 10: 44)
   = 16*2 + 1*12                           (base 16: 2C)
   = 32*1 + 16*0 + 8*1 + 4*1 + 2*0 + 1*0   (base 2: 101100)

And so on. In the case of binary numbers, there are only two possibilities: either the component is present or it is not:

1, 2, 4, 8, 16, 32,...

In the case of decimal numbers, for example, each component may occur from 0 to 9 times:

1,1,1,1,1,1,1,1,1, 10,10,10,10,10,10,10,10,10, 100,100,100,100,100,100,100,100,100, 1000...

And so on. To "mount" the number 44, take 4 units (i.e. from 9 values 1 available take 4) and 4 tens (among the 9 values 10available take up 4). No hundred, thousand, etc.

This reasoning is even true for "crazy" bases, such as: "represent an amount in Reais using as few notes/coins as possible":

1c,1c,1c,1c, 5c, 10c,10c, 25c, 50c, R$1, R$2,R$2, R$5, R$10,R$10, R$20, R$50, R$100...

R$44 = R$20 + R$10 + R$10 + R$2 + R$2

Reverse method

The most efficient way to solve this problem (representing a given number of components) is to start with the "largest of them" (or, if the sequence is infinite, the largest of them that is less than or equal to the number) and go through the list to the beginning - subtracting the values found until the number reaches zero:

entrada = 44
lista = [1,2,4,8,16,32,64,128]
maior = x in lista if x <= entrada
for y from maior to 0:
    if y <= entrada:
        incluir y na saída
        entrada -= y

Except for the binary case (where the bit test is simpler and more efficient - since the computer "helps" you with the task with binary operators for this), this would be the best way to do, for an arbitrary input [ordered in ascending order, of course].

Direct method

Remember elementary school, when you learned to make sums using the QVL? The same principle can be used, but using an arbitrary basis instead of 10:

• As long as the value to be reached is greater than zero:
  • Take the lowest value from the list (unit), and add it to the output - decreasing the input
  • If the lowest value in the list is not available (i.e. all units were used), remove N values from the output and exchange them for a higher value (dec) - so that N units + 1 unit equals 1 dec.
  • Repeat recursively for larger quantities (ten/hundred, hundred/thousand, etc).

I quoted this method out of curiosity only, because needless to say it is too inefficient (you would be "counting" from 1 to 44 - complexity O(n)), I leave the implementation in code as exercise for the reader... : P

Answer 3

I have a sequence of numbers: 1, 2, 4, 8, 16, 32 and so on

So 'so go', I’m assuming that your sequence represents powers of 2:

2⁰ = 1
2¹ = 2
2² = 4
2³ = 8
2⁴ = 16
2⁵ = 32

I can infer, then, that the next numbers are:

2⁶ = 64
2⁷ = 128
2⁸ = 256
[...]

Digital devices make use of a structure called Bit to store data. A bit alone can only express a binary state (0/1, true/false, yes/no), but a group of them can express a numerical value if interpreted as the presence or not of a value in its sequence of powers of 2:

Posição            87654321
Mapa de bits       01011011
Valores decimais   |||||||\_ 1
                   ||||||\__ 2
                   |||||\___ (desligado)
                   ||||\____ 8
                   |||\_____ 16
                   ||\______ (desligado)
                   |\_______ 64
                   \________ (desligado)
                ----------------
Total                        91

Any number on a decimal basis can be interpreted that way. So, to find out which bit map composes a certain decimal number, you can use the following Javascript function:

parseInt(numero, 10).toString(2);

If you use 44 at the position of the number parameter, your return will be the following:

101100

Which indicates exactly the bits relative to the values 32, 8 and 4.