最初に1になっているビットを探す

program


「下位ビットから最初に1になっているビットを探していくプログラムを書くだけの簡単なお仕事です」っていうアルバイトをする初夢を見た。


「うわーん、それ全然簡単じゃないよー！！」って下のプログラム書きながら叫んだところで目が覚めた。まさに悪夢であった。




#ifndef BITOP_H

#define BITOP_H
#include <cassert>
#ifdef _MSC_VER

#include <intrin.h>

#endif
namespace misc

{
// BSF(BitScanForward)

//  1になっているbitを下位からscanして何bit目で見つかったかを返す。

//  引数に0を渡してはいけない。

int bsf(unsigned int mask)

{

    assert(mask);

#ifdef _MSC_VER

    // VC++の場合

    unsigned long ret;

    _BitScanForward(&u, mask);

    // これ引数が0だとサーチ失敗を意味するのだが…。

    // まあ、そういう使い方はしてはならないということで…。

    return (int)ret;

#elif defined (__x86_64 || i386)

    int ret;

    __asm__("bsfl %1,%0" : "=r"(ret) : "r"(mask));

    return ret;

#else

    // gccの場合

    return __builtin_ctzl(mask);

#endif

}
}

#endif