Продолжение степени двойки
Недавно я писал про алгоритм определения является ли число степенью двойки. Nitro на пару с Sam предложили функцию, которая работала медленнее, чем мой алгоритм, но в достоинства этого решения вписали возможность определения в какую степень нужно возвести двойку, чтобы получить заданное число. Я хотел бы немного порассуждать как можно определить какой степенью двойки является число.
Задача: Дано число. Известно, что это число равно 2 в степени N. Найти это N, если оно в пределах от 1 до 30.
На самом деле, я нашел четыре метода. Но два из них - клоны, поэтому будем считать, что их три. Алгоритмы, приведенные здесь, возможно, не новы. Но интересно было попробовать их реализовать. Придумывалось это все с помощью Сергея Лунгу — моего знакомого хорошего программиста.
Ну, сейчас самое время начать уже писать что-то по делу.
Исходные данные
$grade = 29;
$var = 2**$grade;
$g = 30;
$try = 1 << $g;
Здесь $grade - искомая величина, то есть - степень двойки. $var - это число, которое дается по условию. $g - степень числа, которое мы будем сравнивать с $var. А $try - само это число.
Определение степени двойки методом прямого перебора
Самый простой метод заключается в том, чтобы тупо прогнать все степени от нуля до максимума, каждый раз возводя 2 в эту степень и проверяя, не равен ли результат данному числу. Это можно сделать, используя операции возведения в степень, но мы не ищем легких путей, поэтому будем оперировать операциями +, - и сдвиг вправо, свдиг влево.
for ($try=$var, $g=0; $try>1; $try=$try>>1)
{$g++}
Для тех, кто не понял, объясню: операция "сдвиг вправо"(>>) делит число на два без остатка. А операция "сдвиг влево"(<<) - умножает число на два.
Здесь мы просто берем число и делим его на два до тех пор, пока не получится 1. Каждый раз прибавляем степень. Как только единица - сразу прекращаем выполнение цикла. Все, искомая степень у нас есть.
Можно идти и с начала к концу, каждый раз умножая число на два.
for($try=1, $g=0; $try!=$var; $try=$try << 1)
{$g++;}
Результат такой же. Какое преимущество этого метода? Простота. Какой недостаток? Для того, чтобы определить результат, нужно сделать количество итераций, равное искомой степени, что не айс.
Определение степени двойки методом половинного деления
Если вы когда-нибудь искали в отсортированном массиве значение, то знаете (надеюсь) про метод половинного деления. Его суть сводится к тому, что мы каждый раз делим отрезок пополам и сравниваем значение в полученной точке с искомым. Если оно меньше, то снова делим пополам и уменьшаем на это значение. Если больше, то делим и увеличиваем. Именно по такому принципу можно искать и решение этой задачи.
$s = $g >> 1; #Вводим переменную длины шага, которая равна тестируемая степень/2
while($try != $var)
{
print "g=$g, try=$try, s=$s|";
if($try > $var)
{$g = $g - $s;}
elsif($try < $var)
{$g = $g + $s;}
$try = 1 << $g; #Задаем $try новое значение
$s = $s >> 1 if ($s!=1);
print "g=$g, try=$try, s=$s<br/>";
$iter++; #накапливаем количество итераций, которое потребовалось для решения задачи
}
print "<h1>$g(Iterations: $iter)</h1>";
Если запустить этот алгоритм, можно четко видеть как трансформируются переменные в нем и сколько итераций потребовалось для его выполнения. Скажем, если мы искали число 27 в предыдущем алгоритме за 27 итераций, то в этом мы найдем его за 5! Это, на мой взгляд, большой прорыв.
Какие достоинства у этого метода? Он быстр. Недостатки? Степень двойки ограничивается промежутком от 1 до 31. Благо, 2^0 - единица, так что это не проблема, однако, проблемой могут стать большие числа. Хотя, сталкиваться с такими в подобных задачах приходится не часто, все равно обидно.
Определение степени двойки разумным методом
А теперь, господа (и дамы?), приготовьтесь. Мы тут, конечно, поумничали, поприменяли битовые операции и написали нечитаемые алгоритмы для решения задачи, которая звучит так:
"В какую степень нужно возвести двойку, чтобы она стала равна вот этому числу?"
Знаете, какая математическая функция выполняет эту задачу? Логарифм по основанию два! В результате несложных математических преобразований, мы получаем самое простое, эффективное и элегантное решение:
print "log2($var) = <b>", log($var)/log(2), "</b>";
Вот так вот. И здесь нет никаких ограничений ни на диапазон допустимых значений, ни на знак степени. Просто и гениально.
Но зато как было интересно писать алгоритм для метода половинного деления... Всем рекомендую поизобретать велосипед на досуге.
![[Valid RSS]](/img/valid-rss-rogers.png)
by SHAman