Szybkie obliczanie log2 dla 64-bitowych liczb całkowitych
Świetny zasób programistyczny, Bit Twiddling Hacks, proponuje (tutaj) następująca metoda obliczania log2 32-bitowej liczby całkowitej:
#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
static const char LogTable256[256] =
{
-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];
}
i wspomina o tym
Metoda tabeli przeglądowej zajmuje tylko około 7 operacji, aby znaleźć dziennik o wartości 32-bitowej. Jeśli zostanie rozszerzony dla 64-bitowych wielkości, zajmie około 9 operacji.
ale, niestety, nie podaje żadnych dodatkowych informacji o tym, w którą stronę należy się udać, aby rozszerzyć algorytm na 64-bitowe liczby całkowite.
Jakieś wskazówki, jak wyglądałby ten 64-bitowy algorytm?