Противоположность 2 ^ n

Question

Функция a = 2 ^ b может быть быстро вычислена для любого b, выполнив a = 1 << b.А как же наоборот, получить значение b для любого данного a?Это должно быть относительно быстро, поэтому журналы исключены .Все, что не O (1), также плохо.

Я был бы доволен , но не может быть , даже если его просто невозможно обойтись без журналов или типа поиска.

Answer 1

Постройте справочную таблицу. Для 32-разрядных целых чисел есть только 32 записи, поэтому это O (1).

В большинстве архитектур также есть инструкция для поиска позиции старшего значащего бита числа a , которое является значением b . (gcc предоставляет для этого __builtin_clz функцию .)

Для BigInt его можно вычислить в O (log a) путем многократного деления на 2.

int b = -1;
while (a != 0) {
  a >>= 1;
  ++ b;
}

Answer 2

Для такого рода вещей я обычно обращаюсь к этой странице с битовыми хаки:

• Битовые трюки

Например:

Найти логическую базу 2 целого числа с таблицей поиска :

static const char LogTable256[256] = 
{
#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
    -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
    LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
    LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
};

unsigned int v; // 32-bit word to find the log of
unsigned r;     // r will be lg(v)
register unsigned int t, tt; // temporaries

if (tt = v >> 16)
{
  r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
}
else 
{
  r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}

На этой странице также приведено несколько алгоритмов O (log (n)).

Answer 3

Или вы можете написать:

while ((a >>= 1) > 0) b++;

Это O (1). Можно представить, что это будет расширено до:

b = (((a >> 1) > 0) ? 1 : 0) + (((a >> 2) > 0) ? 1 : 0) + ... + (((a >> 31) > 0) ? 1 : 0);

При оптимизации компилятора, когда (a >> x) > 0) возвращает false, остаток не будет рассчитываться. Также сравнение с 0 быстрее, чем любое другое сравнение. Также: , где k не более 32, а g равно 1.

Ссылка: Большая буква O

Но если вы используете BigInteger, мой пример кода будет выглядеть так:

    int b = 0;
    String numberS = "306180206916083902309240650087602475282639486413"
            + "866622577088471913520022894784390350900738050555138105"
            + "234536857820245071373614031482942161565170086143298589"
            + "738273508330367307539078392896587187265470464";
    BigInteger a = new BigInteger(numberS);

    while ((a = a.shiftRight(1)).compareTo(BigInteger.ZERO) > 0) b++;

    System.out.println("b is: " + b);

Answer 4

В некоторых архитектурах есть инструкция «считать ведущие нули». Например, на ARM:

MOV R0,#0x80      @ load R0 with (binary) 10000000
CLZ R1,R0         @ R1 = number of leading zeros in R0, i.e. 7

Это O (1).

Answer 5

В Java вы можете использовать Integer.numberOfLeadingZeros для вычисления двоичного логарифма.Возвращает число ведущих нулей в двоичном представлении, поэтому

• floor (log2 (x)) = 31 - numberOfLeadingZeros (x)
• ceil (log2 (x)) =32 - numberOfLeadingZeros (x - 1)

Answer 6

Если a является двойным, а не int, то оно будет представлено как мантисса и показатель степени.Экспонента - это та часть, которую вы ищете, поскольку это логарифм числа.

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

Для интегрального значения, если какой-либо метод получения наиболее значимой позиции бита недоступен, вы можете выполнить двоичный поиск битов для верхнего-мост 1, который, следовательно, O (log numbits).Выполнение этого может на самом деле работать быстрее, чем сначала преобразование в двойное число.

Answer 7

Это невозможно сделать без тестирования старшего бита, но большинство современных FPU поддерживают log2, поэтому не все потеряно.