Вычисление floor(log_2(x)) можно выполнить, подсчитав количество нулей, для которых существует the-highest-set-bit-msb-in-i">множество быстрых алгоритмов.
Существуют ли какие-либо аналогичные приемы для вычисления floor(log_{2^(1/4)}(x)), когда x является 64-битным целым числом без знака, охватывающим все возможные значения?
Поскольку log_{2^(1/4)}(x)=4*log_2(x)=log_2(x^4), это было бы эквивалентно поиску эффективного алгоритма для floor(4*log_2(x)) или floor(log(x^4)).
После того, как мы вычислим floor(log_2(x)), мы можем разделить z = x / 2^floor(log_2(x)) и рассмотреть задачу вычисления floor(log_{2^(1/4)}(z)), где z принадлежит диапазону [1, 2), так как floor(log_{2^(1/4)}(x)) = 4 floor(log_2(x)) + floor(log_{2^(1/4)}(z)). Есть только четыре возможности для floor(log_{2^(1/4)}(z)), поэтому два сравнения (три для безответвления) z с константами
(2^(1/4))^1, (2^(1/4))^2, (2^(1/4))^3
будет достаточно. Чтобы полностью избежать арифметики с плавающей запятой, «деление» может быть реализовано как сдвиг влево, который оставляет (2^63) z для сравнения с аналогично представленными константами.
Теперь с кодом C:
#include <assert.h>
#include <stdio.h>
static int mylog(unsigned long long x) {
assert(x > 0ULL);
/* compute n = floor(log2(x)) */
unsigned long long y = x | (x >> 1);
y |= y >> 2;
y |= y >> 4;
y |= y >> 8;
y |= y >> 16;
y |= y >> 32;
y -= (y >> 1) & 0x5555555555555555ULL;
y = (y & 0x3333333333333333ULL) + ((y >> 2) & 0x3333333333333333ULL);
y = (y + (y >> 4)) & 0x0f0f0f0f0f0f0f0fULL;
y = (y + (y >> 8)) & 0x00ff00ff00ff00ffULL;
y = (y + (y >> 16)) & 0x0000ffff0000ffffULL;
y = (y + (y >> 32)) & 0x00000000ffffffffULL;
int n = (int)y - 1;
/* normalize x and use binary search to find the last two bits of the log */
x <<= 63 - n;
n <<= 2;
if (x < 0xb504f333f9de6485ULL) {
return x < 0x9837f0518db8a970ULL ? n : n + 1;
} else {
return x < 0xd744fccad69d6af5ULL ? n + 2 : n + 3;
}
}
int main(void) {
unsigned long long x;
while (scanf("%llu", &x) == 1) {
printf("%d\n", mylog(x));
}
}
Запрос Mathematica/Wolfram Alpha для вычисления констант:
BaseForm[Table[Ceiling[2^(63+i/4)],{i,1,3}],16] .
floor(4*log_2(x))из-за ошибок округления для большихx. С точки зрения производительности, прямой перевод на Go не дает такой большой разницы в производительности, как я ожидал. Для случайных, равномерно распределенных значений uint64 я сравниваю54.7ns/opдля наивного подхода и19.8ns/opдля описанного выше. Одна только расчетная частьlog_2соответствует7.9ns/op. 29.08.2014