如何有效地計算樓層日誌庫2 ^（1/4）

Question

計算floor(log_2(x))可以通過計算快速算法的零的數量來完成。

是否有任何類似的計算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))的高效算法。

Answer 1

我們計算floor(log_2(x))後，我們可以把z = x/2^floor(log_2(x))並在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))的問題。只有四種可能性floor(log_{2^(1/4)}(z))，所以兩個比較（三爲網點）的z與常量

(2^(1/4))^1, (2^(1/4))^2, (2^(1/4))^3 

就足夠了。爲了完全避免浮點運算，可以將「除法」實現爲左移，將(2^63) z與類似代表的常量進行比較。

#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)); 
    } 
} 

的數學/ Wolfram Alpha的查詢來計算常數是

BaseForm[Table[Ceiling[2^(63+i/4)],{i,1,3}],16] .