То, что является лучшим решением для получения основы 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
Чтобы это было быстрее, чем число битов, не кэшируя его должно быть быстрее, чем O(lg(k))
где k
количество битов устройства хранения данных.
Многие архитектуры имеют инструкцию "найти первой" (bsr, clz, bfffo, cntlzw и т.д.), которая будет намного быстрее, чем подходы к подсчету битов.
Если вы знаете, что число является степенью двойки, вы можете просто сдвинуть его вправо ( >>
), пока оно не станет равным 0. Сколько раз вы сдвигались вправо (минус 1) - это ваше k
.
Правка : быстрее, чем этот метод таблицы поиска (хотя вы жертвуете некоторым пространством, но не тонной). См. http://doctorinterview.com/index.html/algorithmscoding/find-the-integer-log-base-2-of-an-integer/ .
Да. Вот способ сделать это без битового счета в 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.
Если вы не против работы с плавающей точкой, вы можете использовать log(x) / log(2)
.