Математическая задача: петля или рекурсив

Question

Я пытаюсь разбить число на массив чисел (в php), например, так:

• 25 становится (16, 8, 1)
• 8 становится (8)
• 11 становится (8, 2, 1)

Я не знаю, каков правильный термин, но я думаю, что идея ясна.

Мое решение с циклом довольно простое:

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

У меня также есть рекурсивное решение, но я не могу заставить это работать без использования глобальной переменной (не хочу этого), следующее близко, но приводит к массивам в массивах:

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

Тем не менее, использование что-то вроде pow (floor (log ())) * кажется слишком большим для такой простой проблемы, как эта.

Мне кажется, что проблема требует рекурсивного решения с некоторыми очень простыми математическими вычислениями, но я просто не вижу этого.

Любая помощь будет оценена.

Редактировать: Бинарный ключ, большое спасибо всем!

Answer 1

Вы можете просто получить двоичное представление числа - 1 означает, что включает степень 2, ноль означает, что

т.е.

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

Это проверено и работает нормально, но, возможно, есть и лучшие способы синтаксического использования в PHP.

Answer 2

Вы можете проверить каждый бит входного номера с помощью следующей (непроверенной) функции.

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

Он проверяет бит в позиции $ pos в переменной $ var с помощью побитовой функции AND. Для краткости я покажу вам 4-битные числа.

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

Если я хочу проверить позицию 0 (самый правый бит) числа 3, я бы вызвал функцию следующим образом:

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

Внутри, checkBit будет сдвигать константу 1 влево 0 раз, потому что я передал 0. Затем он будет поразрядно И (&) результат с числом, которое я передал, 3. Поскольку 3 = 0011 1 = 0001 результат равен true, поскольку 0-й бит установлен в обоих аргументах для побитового оператора AND.

Answer 3

По моему опыту рекурсия имеет больше накладных расходов, чем зацикливание, поэтому я бы посоветовал придерживаться вашего зацикливания

Answer 4

Еще один способ разбить целое число на степени 2 - продолжить деление на 2 и найти остаток.

Например: 25/2 = 12 R 1, мощность = 2 ^ 0 = 1

12/2 = 6 R 0, мощность = 2 ^ 1 = 2

6/2 = 3 R 0, мощность = 2 ^ 2 = 4

3/2 = 1 R 1, мощность = 2 ^ 3 = 8

1/2 = 0 R 1, мощность = 2 ^ 4 = 16

Итак, здесь 25 = 1 + 8 + 16, потому что это единственные места, где остаток был 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;
}

Answer 5

Если вы просто выполняете битовую обработку и (например, "num & 0x0001") и проверяете значение этой операции на нулевое значение, это должно быть тривиально, чтобы отключить через биты, например (Я знаю, что это в Java, но я не знаю php, и это не совсем проблема php в любом случае)

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

Нечто подобное должно быть тривиально на любом языке.

Answer 6

Если ваши числа не очень редки (то есть число_карта будет маленьким), возможно, быстрее будет работать через все силы Пребывание с базой 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;
}