Prompt, pzhl, algorithm. The input can be the sum of any degrees 2, the maximum 2 ^ 9 = 512, for example:

1) 2 + 512 = 514

2) 1 + 16 + 32 = 49

3) 64 + 128 = 192

    3 answers 3

    In fact, the powers of two, of which the number is added, are reflected by the positions of the units in its binary representation. For example, the number 123 in binary numbering system looks like this: 1111011. Units in positions 0, 1, 3, 4, 5 (numbering went from right to left, starts from 0). So 123 = 2 ^ 0 + 2 ^ 1 + 2 ^ 3 + 2 ^ 4 + 2 ^ 5 + 2 ^ 6 = 1 + 2 + 8 + 16 + 32 + 64. Much has been written about the conversion of numbers to binary CC, I I will not dwell on this.

    If bitwise arithmetic looks too complicated for you, then you can use the "greedy" algorithm. The bottom line is this: at each iteration, we select the maximum power of two that is less than or equal to the current number. We memorize it as one of the components and wean it from the number. Repeat until the number becomes 0.

    Example: decompose the number 123.

    1. The maximum power of two is less than or equal to 123 - 64. We memorize 64, subtract it from 123, we get 59.
    2. The maximum power of two is less than or equal to 59 - 32. We memorize 32, subtract it from 59, we get 27.
    3. The maximum power of two is less than or equal to 27 - 16. We memorize 16, subtract it from 27, we get 11.
    4. The maximum power of two is less than or equal to 11 - 8. We memorize 8, subtract it from 11, we get 3.
    5. The maximum power of two is less than or equal to 3 - 2. We memorize 2, subtract it from 11, we get 1.
    6. The maximum power of two is less than or equal to 1 - 1. We memorize 1, subtract it from 1, we get 0.

    The algorithm finished, resulting in 123 = 64 + 32 + 16 + 8 + 2 + 1.

      To solve the problem, it suffices to test each of the 10 bits of the number. The simplest is logical AND with a shifted unit:

      function bit_analysis($n){ $bin_powers = array(); for($bit = 0; $bit<10; $bit++){ $bin_power = 1 << $bit; if($bin_power & $n) $bin_powers[$bit] = $bin_power; } return $bin_powers; } $n = 514; print("n=$n"); var_dump(bit_analysis($n)); $n = 49; print("n=$n"); var_dump(bit_analysis($n)); $n = 192; print("n=$n"); var_dump(bit_analysis($n));

      Results:

       n = 514
 array (size = 2)
   1 => int 2
   9 => int 512
 n = 49
 array (size = 3)
   0 => int 1
   4 => int 16
   5 => int 32
 n = 192
 array (size = 2)
   6 => int 64
   7 => int 128

      The keys are equal to the number of the corresponding bit (or the power of two, which is the same).

        I'll start:

        1) check the number "a" for parity

        1a) if even a = b, go to the second paragraph

        1b) if odd, then the series starts with one, we get b = (a-1) and move on with the current number b

        2) divide the number b by 2 until we get an odd number, memorize the number of divisions i, raise 2 to the power of i, write this number z in the series we need,

        3) bz = c and go to step 2

        4) we build the resulting series in ascending order.

        It seems so, I can be mistaken.

        • I misunderstand a little. Sketched on a piece of paper, it turned out like this: 1) a = 1023 2) b = 1023 - 1 = 1022 3) 1022/2 = 511 And then I don’t know how - zooZooz