Should I use loop or recursive function?

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.

Brendan · Accepted Answer · 2009-02-17 18:10:47Z

7

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.

edited Feb 17, 2009 at 18:10

answered Feb 17, 2009 at 17:41

Brendan

19.6k19 gold badges90 silver badges118 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Bill the Lizard · Accepted Answer · 2009-02-17 19:02:34Z

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.

edited Feb 17, 2009 at 19:02

answered Feb 17, 2009 at 17:52

Bill the Lizard

407k213 gold badges579 silver badges892 bronze badges

Comments

Scott Vander Molen · Accepted Answer · 2009-02-17 17:43:16Z

3

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

answered Feb 17, 2009 at 17:43

Scott Vander Molen

6,4296 gold badges44 silver badges43 bronze badges

Comments

Venkat D. · Accepted Answer · 2009-02-18 06:22:47Z

1

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;
}

answered Feb 18, 2009 at 6:22

Venkat D.

3,03938 silver badges43 bronze badges

Comments

Mark · Accepted Answer · 2009-02-17 18:11:46Z

0

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;
}

answered Feb 17, 2009 at 18:11

Mark

6,3212 gold badges38 silver badges35 bronze badges

Collectives™ on Stack Overflow

Should I use loop or recursive function?

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related