How to decompose a number in powers of 2

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

An example:

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

Then, going from right to left, 44 in binary and 101100. So, to know what the decomposition of any number in powers of 2 we need to see what are the bits connected in their representation in base 2. p>

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.

Soon, something like this:

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

The Lucas Virgili's answer explains well the rationale behind the question (which certainly is even about binary representation ), but I would like to give you a slightly more general answer:

When you get any number in the abstract and represent that number in a base , you are just breaking it down 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 not:

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

In the case of numbers in decimal, for example, each component can 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. In order to "assemble" the number 44 , we take 4 units (i.e. from the 9% available% coefficients we get 4) and 4 tens (from the 9% available coefficients we get 4). No hundred, thousand, etc.

This reasoning is true even for "crazy" bases, such as "represent an amount in Reais using as few notes 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

The most efficient way to solve this problem (to represent a given number of components) is to start with the "largest of them" (or, if the sequence is infinite, the largest of them is less than or equal to the number ) and scroll 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 bit testing is simpler and more efficient - since the computer "helps" the task with binary operators for it), this would be the best way to do an arbitrary input [ ordered in ascending order, of course].

Direct method

Remember the primary when you learned how to make sums using QVL ? The same principle can be used, but using an arbitrary base 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 - decrementing the input
  • If the lowest value in the list is not available (ie all units have been used), remove N values from the output and change them to a larger value (ten) - so that N units + 1 unit is equal to ten.
  • Repeat recursively for larger quantities (tens / hundreds, hundreds / thousands, etc.).

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

  

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

By 'so it goes', I am assuming that its sequence represents powers of 2:

2 0 = 1
2 1 = 2
2 2 = 4
2 3 = 8
2 4 = 16
2 5 = 32

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

2 6 = 64
2 7 = 128
2 8 = 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 numeric value if interpreted as a presence or not of a value in its power sequence of 2: / p>

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

Any number in decimal base can be interpreted in this way. Thus, to find out which bitmap composes a given decimal number, you can use the following JavaScript function:

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

If you use 44 in the position of the parameter number, your return will be as follows:

101100

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