高速な log2

高速に floor(log2(n)) を計算するコード。無駄に template です。大量の計算のお供に。

#include <boost/concept_check.hpp>

/**
 * returns floor of log i
 */
template<typename INT>
inline int intlog2(INT i)
{
    boost::function_requires< boost::UnsignedIntegerConcept<INT> >();
    int n = 1;
    int d = std::numeric_limits<INT>::digits / 2;
    int s = 0;

    while (d > 1) {
        s += d;
        if ((i >> s) == 0) {
            n += d;
            i <<= d;
        }
        d /= 2;
    }
    n -= i >> (std::numeric_limits<INT>::digits - 1);
    return std::numeric_limits<INT>::digits - 1 - n;
}

素直な実装だとこうだろうか。

template<typename INT>
inline int intlog2(INT i)
{
    boost::function_requires< boost::UnsignedIntegerConcept<INT> >();
    int r = 0;
    while (i > 1) {
        r++;
        i >>= 1;
    }
    return r;
}

gcc -O3 でコンパイルすると速度は数十倍程度の差になるようだ。インライン展開されないとそこまでの差は付かないけど。
objdump してみてみたら、最適化でコード丸ごと実行されなくなってるだけだった。5倍速い、くらいが順当なところみたいだ。