«1. Обзор

В этой статье мы увидим, как найти наибольшую степень числа 2, которая меньше заданного числа.

Для наших примеров мы возьмем пример ввода 9. 20 равно 1, наименьший допустимый ввод, для которого мы можем найти степень 2, меньшую, чем заданный ввод, равен 2. Следовательно, мы будем рассматривать только вводы больше, чем 1 как действительный.

2. Наивный подход

Давайте начнем с 20, что равно 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;
}

Давайте разберемся с code for sample input = 9.

Начальное значение для firstPowerOf2 равно 1, а nextPowerOf2 равно 2. Как мы видим, 2 \u003c 9 верно, и мы попадаем внутрь цикла while.

Для первой итерации firstPowerOf2 равно 2, а nextPowerOf2 равно 2 * 2 = 4. Опять 4 \u003c 9, поэтому давайте продолжим цикл while.

Для второй итерации firstPowerOf2 равно 4, а nextPowerOf2 равно 4 * 2 = 8. Теперь 8 \u003c 9, продолжим.

Для третьей итерации firstPowerOf2 равно 8, а nextPowerOf2 равно 8 * 2 = 16. Условие while 16 \u003c 9 ложно, поэтому цикл while прерывается. 8 — это наибольшая степень двойки, которая меньше 9.

Давайте запустим несколько тестов для проверки нашего кода: 

assertEquals(8, findPowerOf2LessThanTheGivenNumber(9));
assertEquals(16, findPowerOf2LessThanTheGivenNumber(32));

Временная сложность нашего решения равна O(log2(N)). В нашем случае мы повторили log2(9) = 3 раза.

3. Использование Math.log

Логарифмическая база 2 даст, сколько раз мы можем рекурсивно разделить число на 2, другими словами, log2 числа дает степень 2. Давайте рассмотрим несколько примеров, чтобы понять это. .

log2(8) = 3 и log2(16) = 4. В общем случае мы видим, что y = log2x, где x = 2y.

Следовательно, если мы находим число, которое делится на 2, мы вычитаем из него 1, чтобы избежать сценария, в котором число является полной степенью числа 2.

Math.log равно log10. Чтобы вычислить log2(x), мы можем использовать формулу log2(x)=log10(x)/log10(2)

Давайте запишем это в код: значение temp равно 9. 

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 % 2 равно 1, поэтому наша переменная temp равна 9. Здесь мы используем деление по модулю, что даст остаток 9/2.

Чтобы найти log2(9), мы делаем log10(9) / log10(2) = 0,95424 / 0,30103 ~= 3.

Теперь результат равен 23, что равно 8.

Давайте проверим наш код :

На самом деле Math.pow будет выполнять ту же итерацию, что и в подходе 1. Следовательно, мы можем сказать, что и для этого решения временная сложность равна O(Log2(N)). 

assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(9));
assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(32));

4. Метод побитового сдвига

Для этого подхода мы будем использовать метод побитового сдвига. Во-первых, давайте посмотрим на двоичное представление степени 2, учитывая, что у нас есть 4 бита для представления числа

Присмотревшись внимательно, мы можем заметить, что мы можем вычислить степень 2, сдвигая байты влево для 1. т.е. 22 — это байты сдвига влево для 1 на 2 места и так далее.

20 1 0001
21 2 0010
22 4 0100
23 8 1000

Давайте напишем код, используя технику битового сдвига:

В приведенном выше коде мы используем тип данных long, который использует 8 байтов или 64 бита. Таким образом, мы будем вычислять степень числа 2 до 264. Мы используем оператор сдвига бит \u003c\u003c, чтобы найти степень числа 2. Для нашего примера ввода 9 после 4-й итерации значение powerOf2 = 16, а результат = 8, где мы выходим из цикла, так как 16 \u003e 9 вход. 

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

Давайте проверим, работает ли наш код так, как ожидалось:

Временная сложность в наихудшем случае для этого подхода снова равна O(log2(N)), аналогично тому, что мы видели для первого подхода. Однако этот подход лучше, так как операция битового сдвига более эффективна по сравнению с умножением. 

assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(9));
assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(32));

5. Побитовое И

Для нашего следующего подхода мы будем использовать эту формулу 2n И 2n -1 = 0.

Давайте рассмотрим несколько примеров, чтобы понять, как это работает.

Двоичное представление 4 — 0100, а 3 — 0011.

Давайте выполним побитовую операцию И над этими двумя числами. 0100 И 0011 равно 0000. То же самое можно сказать для любой степени двойки и числа, меньшего ее. Возьмем 16 (24) и 15, которые представлены как 1000, 0111 соответственно. Опять же, мы видим, что побитовое И для этих двух результатов дает 0. Мы также можем сказать, что операция И для любого другого числа, кроме этих 2, не даст 0.

«Давайте посмотрим на код решения этой проблемы с помощью побитового И:

В приведенном выше коде мы перебираем числа, меньшие нашего ввода. Всякий раз, когда мы находим побитовое И числа, а число-1 равно нулю, мы выходим из цикла, поскольку мы знаем, что это число будет степенью 2. В этом случае для нашего примера ввода 9 мы выходим из цикла когда i = 8 и i – 1 = 7. 

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

Теперь давайте проверим пару сценариев:

Временная сложность в наихудшем случае для этого подхода составляет O(N/2), когда вход является точной степенью 2. Как мы видим, это не самое эффективное решение, но хорошо знать эту технику, поскольку она может пригодиться при решении подобных задач. 

assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(9));
assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(32));

6. Заключение

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

Полный исходный код с модульными тестами для этой статьи можно найти на GitHub.

«