1. Обзор
В этой статье мы увидим, как найти наибольшую степень числа 2, которая меньше заданного числа.
Для наших примеров мы возьмем выборку ввода 9. 2 ^0 равно 1, наименьший допустимый ввод, для которого мы можем найти степень 2, меньшую, чем данный ввод, равен 2. Следовательно, мы будем рассматривать только входы больше 1 как действительный.
2. Наивный подход
Давайте начнем с 2 ^0 , что равно 1, и мы будем продолжать умножать число на 2, пока не найдем число, которое меньше входного значения :
public long findLargestPowerOf2LessThanTheGivenNumber(long input) {
Assert.isTrue(input > 1, "Invalid input");
long firstPowerOf2 = 1;
long nextPowerOf2 = 2;
while (nextPowerOf2 < input) {
firstPowerOf2 = nextPowerOf2;
nextPowerOf2 = nextPowerOf2 * 2;
}
return firstPowerOf2;
}
Давайте разберемся с кодом для примера ввода = 9.
Начальное значение для firstPowerOf2 равно 1, а nextPowerOf2 равно 2. Как мы видим, 2 < 9 верно, и мы попадаем внутрь цикла while.
Для первой итерации firstPowerOf2 равно 2, а nextPowerOf2 равно 2 * 2 = 4. Опять 4 < 9, поэтому давайте продолжим цикл while.
Для второй итерации firstPowerOf2 равно 4, а nextPowerOf2 равно 4 * 2 = 8. Теперь 8 < 9, давайте продолжим.
Для третьей итерации firstPowerOf2 равно 8, а nextPowerOf2 равно 8 * 2 = 16. Условие while 16 < 9 ложно, поэтому цикл while прерывается. 8 - это наибольшая степень числа 2, которое меньше 9.
Давайте запустим несколько тестов для проверки нашего кода:
assertEquals(8, findPowerOf2LessThanTheGivenNumber(9));
assertEquals(16, findPowerOf2LessThanTheGivenNumber(32));
Временная сложность нашего решения O(log 2 (N)) . В нашем случае мы повторили log 2 (9) = 3 раза.
3. Использование Math.log
Логарифмическая база 2 даст, сколько раз мы можем рекурсивно разделить число на 2, другими словами, логарифм 2 числа дает мощность 2 . Давайте посмотрим на несколько примеров, чтобы понять это.
log 2 (8) = 3 и log 2 (16) = 4. В общем, мы можем видеть, что y = log 2 x, где x = 2 ^y .
Следовательно, если мы находим число, которое делится на 2, мы вычитаем из него 1, чтобы избежать сценария, в котором число является совершенной степенью 2.
Math.log — это log 10 . Чтобы вычислить log 2 (x), мы можем использовать формулу log 2 (x) = log 10 (x)/log 10 (2)
Давайте поместим это в код:
public long findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(long input) {
Assert.isTrue(input > 1, "Invalid input");
long temp = input;
if (input % 2 == 0) {
temp = input - 1;
}
long power = (long) (Math.log(temp) / Math.log(2));
long result = (long) Math.pow(2, power);
return result;
}
Предполагая, что наш пример ввода равен 9, начальное значение temp равно 9.
9 % 2 равно 1, поэтому наша временная переменная равна 9. ** ** Здесь мы используем деление по модулю, что даст остаток 9/2.
Чтобы найти log 2 (9), мы делаем log 10 (9) / log 10 (2) = 0,95424 / 0,30103 ~= 3.
Теперь результат 2 ^3 , что равно 8.
Давайте проверим наш код:
assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(9));
assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(32));
На самом деле Math.pow будет выполнять ту же итерацию, что и в подходе 1. Следовательно, мы можем сказать, что и для этого решения временная сложность составляет O(Log 2 (N)) .
4. Побитовая техника
Для этого подхода мы будем использовать технику побитового сдвига. Во-первых, давайте посмотрим на двоичные представления степени 2, учитывая, что у нас есть 4 бита для представления числа.
| 2 ^0 | 1 | `0001` |
| 2 ^1 | 2 | `0010` |
| 2 ^2 | 4 | `0100` |
| 2 ^3 | 8 | `1000` |
Присмотревшись, мы можем заметить, что мы можем вычислить степень числа 2, сдвигая влево байты для 1 . т.е. 2 ^2 — сдвиг байтов влево на 1 на 2 места и т.д.
Давайте напишем код, используя технику битового сдвига:
public long findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(long input) {
Assert.isTrue(input > 1, "Invalid input");
long result = 1;
long powerOf2;
for (long i = 0; i < Long.BYTES * 8; i++) {
powerOf2 = 1 << i;
if (powerOf2 >= input) {
break;
}
result = powerOf2;
}
return result;
}
В приведенном выше коде мы используем тип данных long , который использует 8 байтов или 64 бита. Итак, мы будем вычислять мощность от 2 до 2 ^64 . Мы используем оператор битового сдвига << , чтобы найти степень числа 2. Для нашего примера ввода 9 после 4 ^-й итерации значение powerOf2 = 16 и результат = 8, где мы выходим из цикла, поскольку 16 > 9 ввод .
Давайте проверим, работает ли наш код должным образом:
assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(9));
assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(32));
Временная сложность в наихудшем случае для этого подхода снова равна O(log 2 (N)) , аналогично тому, что мы видели для первого подхода. Однако этот подход лучше, так как операция битового сдвига более эффективна по сравнению с умножением .
5. Побитовое И
Для нашего следующего подхода мы будем использовать эту формулу 2 ^n AND 2 ^n -1 = 0 .
Давайте рассмотрим несколько примеров, чтобы понять, как это работает.
Двоичное представление 4 — 0100, а 3 — 0011 .
Давайте сделаем побитовую операцию И над этими двумя числами. 0100 И 0011 это 0000 . То же самое можно сказать для любой степени двойки и числа, меньшего ее. Возьмем 16 (2 ^4 ) и 15, которые представлены как 1000 , 0111 соответственно. Опять же, мы видим, что побитовое И для этих двух результатов дает 0. Мы также можем сказать, что операция И для любого другого числа, кроме этих 2, не даст 0.
Давайте посмотрим код решения этой задачи с помощью побитового И:
public long findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(long input) {
Assert.isTrue(input > 1, "Invalid input");
long result = 1;
for (long i = input - 1; i > 1; i--) {
if ((i & (i - 1)) == 0) {
result = i;
break;
}
}
return result;
}
В приведенном выше коде мы перебираем числа, меньшие нашего ввода. Всякий раз, когда мы находим побитовое И числа, а число-1 равно нулю, мы выходим из цикла, поскольку мы знаем, что это число будет степенью 2. В этом случае для нашего примера ввода 9 мы выходим из цикла когда я = 8 и я - 1 = 7.
Теперь давайте проверим пару сценариев:
assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(9));
assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(32));
Временная сложность в наихудшем случае для этого подхода составляет O(N/2) , когда вход представляет собой точную степень 2. Как мы видим, это не самое эффективное решение, но хорошо знать этот метод, поскольку он может прийти удобно при решении подобных задач.
6. Заключение
Мы видели разные подходы к нахождению наибольшей степени двойки, которая меньше заданного числа. Мы также заметили, как побитовые операции в некоторых случаях могут упростить вычисления.
Полный исходный код с модульными тестами для этой статьи можно найти на GitHub .