前言

本文的常数测试均在 Luogu IDE 中测试，测试 C++ 版本为 C++14(GCC 9)+O2，随机数生成种子为 114514，值域取 $[0,10^8)$ 的整数，以运行 1e7 次对数运算为准.

效率测试

当值域降到 $[0,10^6)$ 的整数时

降低值域的同时，将查询次数增加到 2e8 次.

总结

综上所述，递推法在各类环境中很难起到作用，甚至会增加时空复杂度，而自带的库函数表现优秀，std::__lg() 在一定程度上优于 std::log2().

附录

测试代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn1=1e6;
const int maxn2=2e8;
int main(){
    srand(114514);
    for(int i=1;i<=maxn2;i++){
        int k=log2(rand()%maxn1);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn1=1e6;
const int maxn2=2e8;
int main(){
    srand(114514);
    for(int i=1;i<=maxn2;i++){
        int k=__lg(rand()%maxn1);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn1=1e6;
const int maxn2=2e8;
short lg[maxn1+10];
int main(){
    srand(114514);
    lg[2]=1;
    for(int i=1;i<=maxn1;i++){
        lg[i]=lg[i>>1]+1;
    }
    for(int i=1;i<=maxn2;i++){
        int k=lg[rand()%maxn1];
    }
    return 0;
}