高速な 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倍速い、くらいが順当なところみたいだ。