Fast bit map search

PowerPCで long中の ON or OFF bitを高速に探す方法

　領域管理に bit map arrayを使っていたりすると long中で上位 bitから探して最初に ON or OFFなっている bitを求めたいことがよくあります。
　もろに性能にひびく部分ですから高速であることが要求されます。 Cで書くとこんな感じでしょうか。

    unsigned long   word;
    long            bitnum;
 
    for ( bitnum = 0; bitnum < 32; bitnum++ ) {
        if (word & (0x80000000UL >> bitnum))  break;
    }
    if (bitnum < 32) {
        // on bitあった
    }else{
        // on bitない
    }

　Cではこれ以上速い Codeは書けませんが PowerPCには便利な命令があります。 Metrowerks C++では C/C++中に混在はできませんが Assemblerで関数を書けますので１命令だけの関数を作ってしまいましょう。

    //      wordの先頭から続いている 0の bit数を返す。
    asm long   AsmCountLeadingZeroBits(register unsigned long word)
    {
        cntlzw    r3,word   // 1 Clock
        blr
    }

　これを使うと

    unsigned long   word;
    long            bitnum;
 
    bitnum = AsmCountLeadingZeroBits(word);
    if (bitnum < 32) {
        // on bitあった
    }else{
        // on bitない
    }

　でおしまいです。Cでは数十 Clockかかりますが Assemblerでは Branch Foldされることを考慮すればほとんど 1 Clockです。onじゃなく offの bitを探したい場合は notを取って AsmCountLeadingZeroBits()に与えてください。
　PowerPC＋最適化 Compilerの組み合わせでも Assemblerは知っていた方が良いようですね。

　と言っている内に CodeWarrior 11で __cntlzw()という Intrinsic functionが追加されて単に

    bitnum = __cntlzw(word);

と書ける様になりました。あら簡単。

この Pageは MacOS X + Radio UserLand で作っています。