Как получить lg2 числа, равного 2^k

Какое лучшее решение для получения логарифма по основанию 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 — количество бит памяти.


performance bit-manipulation logarithm micro-optimization bitcount
person Egon    schedule 06.02.2010    source источник

Ответы (4)


arrow_upward
3
arrow_downward

Многие архитектуры имеют инструкцию «найти первую» (bsr, clz, bfffo, cntlzw и т. д.), которая будет намного быстрее, чем методы подсчета битов.

person Community    schedule 06.02.2010
comment
наверное самый быстрый способ...) - person Egon; 06.02.2010

arrow_upward
6
arrow_downward

Да. Вот способ сделать это без счетчика битов в 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]) ... (и начальное назначение) проверяет, установлен ли бит k в lg(x). Если это так, мы добавляем его к reg; сумма всех этих битов будет lg(x).

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

// 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.

person John Feminella    schedule 06.02.2010
comment
Это лучший подход, если у вас нет доступа к инструкциям по сборке, но я бы избавился от массива и использовал константы напрямую. - person x4u; 06.02.2010
comment
@x4u: это больше для иллюстративных/образовательных целей, чем для демонстрации оптимизированного кода. Но в остальном согласен. - person John Feminella; 06.02.2010
comment
Лучший подход без сборки, хотя вы можете использовать константы на месте, а не массив arr. Это может сэкономить несколько циклов. - person Mike Dunlavey; 07.02.2010

arrow_upward
5
arrow_downward

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

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

person danben    schedule 06.02.2010
comment
Вы должны установить k = #shifted - 1; - person tur1ng; 06.02.2010
comment
Это будет медленнее, чем метод подсчета битов. Вы можете сделать подсчет битов за O (lg (k)), этот сдвиг будет в худшем случае O (k). (k — количество бит памяти) - person Egon; 06.02.2010
comment
@egon - Единственное, что я вижу, что улучшает lg k, - это метод таблицы поиска. Ответ обновлен. - person danben; 06.02.2010
comment
@danben - да, похоже ... может быть, у кого-то есть отличная идея, как это улучшить. Он чувствует, что может стать быстрее, используя тот факт, что число является степенью двойки. У него есть только k состояний, и это не так много. - person Egon; 06.02.2010
comment
На самом деле я нашел решение в статье. У метода 3 и 4 были версии, если значение было степенью двойки. У метода 3 была версия, которая быстрее, чем использование битового счетчика. - person Egon; 06.02.2010

arrow_upward
-2
arrow_downward

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

person Ignacio Vazquez-Abrams    schedule 06.02.2010
comment
Это будет сотни тактовых циклов на большинстве процессоров. Вы можете сделать это за один цикл, если у вас есть clz или аналогичная инструкция. - person Paul R; 06.02.2010