Mathematical problem: loop or recursive

Question

I´m trying to break a number into an array of numbers (in php) in the way that for example:

• 25 becomes (16, 8, 1)
• 8 becomes (8)
• 11 becomes (8, 2, 1)

I don´t know what the correct term is, but I think the idea is clear.

My solution with a loop is pretty straightforward:

   $number = rand(0, 128);    
   $number_array_loop = array();

   $temp_number = $number;
   while ($temp_number > 0) {
       $found_number = pow(2, floor(log($temp_number, 2)));
       $temp_number -= $found_number;

       $number_array_loop[] = $found_number;
   }

I also have a recursive solution but I can´t get that to work without using a global variable (don´t want that), the following comes close but results in arrays in arrays:

   function get_numbers($rest_number) {

       $found_number = pow(2, floor(log($rest_number, 2)));

       if ($found_number > 0) {
        $temp_array[] = get_numbers($rest_number - $found_number);
        $temp_array[] = $found_number;
       }

       return $temp_array;
   }

   $number_array_recursive = array();
   $number_array_recursive = get_numbers($number);

However, using something like pow(floor(log())) seems a bit much for a simple problem like this.

It seems to me that the problem calls for a recursive solution with some very simple maths, but I just don´t see it.

Any help would be apreciated.

Edit: Binary is the key, thanks a lot all!

Answer 1

You could just get the binary representation of the number - a 1 means include that power of 2, a zero means don't

i.e.

$binary_number = decbin($test_number);
$binary_string = "${binary_number}";
for ($i = 0; $i < strlen($binary_string); $i++) {
  if ($binary_string[strlen($binary_string) - $i - 1] == "1") {
    $num_out = pow(2, $i);
    print "${num_out} ";
  }
}

This is tested and work ok but there are probably better ways of doing syntactically in PHP.

Answer 2

It's been my experience that recursion has more overhead than looping, so I would suggest to stick with your looping solution.

Answer 3

You can check each bit of the input number with the following (untested) function.

function checkBit($var, $pos)
{
    return ($var & (1 << $pos));
}

It checks the bit at position $pos in the variable $var by using a bitwise AND function. I'll show you with 4-bit numbers for brevity.

• 1 = 0001
• 2 = 0010
• 4 = 0100
• 8 = 1000

If I want to check position 0 (the rightmost bit) of the number 3, I'd call the function like this:

$number = 3;
checkBit($number, 0);

Internally, checkBit is going to shift the constant 1 to the left 0 times because I passed in a 0. It's then going to bitwise AND (&) the result with the number I passed in, 3. Since 3 = 0011 and 1 = 0001 the result is true, since the 0th bit is set in both arguments to the bitwise AND operator.

Answer 4

If you just do a bit-wise and (like "num & 0x0001" for example), and check the value of that operation for zeroness, it should be trivial to trip thru the bits, like so: (I know this is in java, but I don't know php, and it's not really a php-specific problem anyway)

    int number=25;
for (int i = 0; i < 16; i++)
{
    if ((number & 0x0001) != 0)
    {
 System.out.println("" + Math.pow(2, i));
    }
    number = number >> 1;
}

Something like this should be trivial to do in any language.

Answer 5

Unless your numbers are very sparse (i.e. number_array will be small), it's probably quicker to work through all powers. Staying with base 2:

function get_powers_of_2($n) {

  // $max_pow = 31;       // faster if you know the range of $n
  $max_pow = log($n, 2);  // safe
  $powers = array();

  for($i = 0; i <= $max_pow; $i++) {
    $pow = 1 << $i;
    if($n & $pow) $powers[] = $pow;
  }
  return $powers;
}

Answer 6

Another way to break an integer into powers of 2 would be to keep dividing by 2 and finding the remainder.

For example: 25/2 = 12 R 1, power = 2^0 = 1

12/2 = 6 R 0, power = 2^1 = 2

6/2 = 3 R 0, power = 2^2 = 4

3/2 = 1 R 1, power = 2^3 = 8

1/2 = 0 R 1, power = 2^4 = 16

So, here 25 = 1 + 8 + 16 because these are the only places where the remainder was 1.

function powers_of_2($n)
{
    $powers = array();
    $base = 1;
    while ($n > 0)
    {
     if ($n % 2 == 1)
     {
      $powers[] = $base;
     }
     $n = (int)$n/2;
     $base *= 2;
    }
    return $powers;
}