高速な log2 #2
ということで、インラインアセンブリをフル活用するバージョン。移植性ってなんですか?
Visual Studio 2005, gcc 3.4.4 on cygwin, gcc 4.1 on Linux(x86), gcc 3.4.6 on Linux(amd64) で動作確認済み。Borland C++ Compiler 5.5 にも対応しようと思ったけど、無償でダウンロードできるやつだけではインラインアセンブリを使えないらしいのでやめた。対応してない場合はちょっと遅いけど、C++ で実装したものになる。
しかし、こういうのも規格に入れておいてくれるといいのになぁ。
#if (defined(__i386__) || defined(__x86_64__)) && defined(__GNUC__) template<typename INT> inline INT intlog2(INT i) { INT r; asm("bsr %1, %0;" :"=r"(r) :"r"(i)); return r; } #elif defined(_MSC_VER) && defined(_M_IX86) template<typename INT> inline INT intlog2(register INT i) { register INT r; __asm { bsr eax, i; mov r, eax } return r; } #else template<typename INT> inline INT intlog2(INT i) { 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; } #endif