Как получить lg2 из числа 2 ^ k

Question

Какое наилучшее решение для получения логарифма числа 2 для оснований, которое, как мне известно, является степенью двойки (2^k). (Конечно, я знаю только значение 2^k, а не k).

Один из способов, которым я думал об этом, - вычитать 1 и затем делать битовый подсчет:

lg2(n) = bitcount( n - 1 ) = k, iff k is an integer
0b10000 - 1 = 0b01111, bitcount(0b01111) = 4

Но есть ли более быстрый способ сделать это (без кэширования)? Также было бы неплохо узнать что-то, что не связано с быстрым подсчетом битов?

Одно из приложений это:

suppose you have bitmask
0b0110111000

and value
0b0101010101

and you are interested of
(value & bitmask) >> number of zeros in front of bitmask
(0b0101010101 & 0b0110111000) >> 3 = 0b100010

this can be done with

using bitcount
value & bitmask >> bitcount((bitmask - 1) xor bitmask) - 1

or using lg2
value & bitmask >> lg2(((bitmask - 1) xor bitmask) + 1 ) - 2

Чтобы он был быстрее, чем bitcount без кэширования, он должен быть быстрее, чем O(lg(k)), где k - это количество битов хранения.

Answer 1

Да. Вот способ сделать это без учета битов в lg(n), если вы знаете, что целое число является степенью 2.

unsigned int x = ...;
static const unsigned int arr[] = {
  // Each element in this array alternates a number of 1s equal to
  // consecutive powers of two with an equal number of 0s.
  0xAAAAAAAA, // 0b10101010..         // one 1, then one 0, ...
  0xCCCCCCCC, // 0b11001100..         // two 1s, then two 0s, ...
  0xF0F0F0F0, // 0b11110000..         // four 1s, then four 0s, ...
  0xFF00FF00, // 0b1111111100000000.. // [The sequence continues.]
  0xFFFF0000
}

register unsigned int reg = (x & arr[0]) != 0;
reg |= ((x & arr[4]) != 0) << 4;
reg |= ((x & arr[3]) != 0) << 3;
reg |= ((x & arr[2]) != 0) << 2;
reg |= ((x & arr[1]) != 0) << 1;

// reg now has the value of lg(x).

На каждом из шагов reg |= мы последовательно тестируем, чтобы увидеть, используются ли какие-либо биты x для чередующихся битовых масок в arr. Если это так, это означает, что lg(x) имеет биты, которые находятся в этой битовой маске, и мы фактически добавляем 2^k к reg, где k - это лог длины чередующейся битовой маски. Например, 0xFF00FF00 - это чередующаяся последовательность из 8 единиц и нулей, поэтому k равно 3 (или lg(8)) для этой битовой маски.

По сути, каждый шаг reg |= ((x & arr[k]) ... (и начальное назначение) проверяет, установлен ли lg(x) бит k. Если это так, мы добавляем его к reg; сумма всех этих битов будет lg(x).

Это похоже на много волшебства, поэтому давайте попробуем пример. Предположим, мы хотим знать, что такое степень 2, значение 2,048:

// x = 2048
//   = 1000 0000 0000

register unsigned int reg = (x & arr[0]) != 0;
// reg =       1000 0000 0000
         & ... 1010 1010 1010
       =       1000 0000 0000 != 0
// reg = 0x1 (1)        // <-- Matched! Add 2^0 to reg.

reg |= ((x & arr[4]) != 0) << 4;
// reg =     0x .. 0800
           & 0x .. 0000
       =              0 != 0
// reg = reg | (0 << 4) // <--- No match.
// reg = 0x1 | 0
// reg remains 0x1.

reg |= ((x & arr[3]) != 0) << 3;
// reg =     0x .. 0800
           & 0x .. FF00
       =            800 != 0
// reg = reg | (1 << 3) // <--- Matched! Add 2^3 to reg.
// reg = 0x1 | 0x8
// reg is now 0x9.         

reg |= ((x & arr[2]) != 0) << 2;
// reg =     0x .. 0800
           & 0x .. F0F0
       =              0 != 0
// reg = reg | (0 << 2) // <--- No match.
// reg = 0x9 | 0
// reg remains 0x9.        

reg |= ((x & arr[1]) != 0) << 1;
// reg =     0x .. 0800
           & 0x .. CCCC
       =            800 != 0
// reg = reg | (1 << 1) // <--- Matched! Add 2^1 to reg.
// reg = 0x9 | 0x2
// reg is now 0xb (11).

Мы видим, что окончательное значение reg равно 2 ^ 0 + 2 ^ 1 + 2 ^ 3, что в действительности равно 11.

Answer 2

Если вы знаете, что число является степенью 2, вы можете просто сдвинуть его вправо (>>) до тех пор, пока оно не станет равным 0. Количество раз, когда вы сдвинули вправо (минус 1), будет вашим k.

Редактировать : быстрее, чем этот метод таблицы поиска (хотя вы жертвуете некоторое пространство, но не тонну). Смотри http://doctorinterview.com/index.html/algorithmscoding/find-the-integer-log-base-2-of-an-integer/.

Answer 3

Во многих архитектурах есть инструкция "найти первым" (bsr, clz, bfffo, cntlzw и т. Д.), Которая будет намного быстрее, чем подходы с счетом битов.

Answer 4

Если вы не против иметь дело с поплавками, вы можете использовать log(x) / log(2).