mitsunari@cybozu labs

2008/4/16にSEA & FSIJ 合同フォーラムでビット演算による最適化の妙味とJITアセンブラというタイトルで発表したときの資料を公開します(pptx, pdf)．
鋭いご質問，ご指摘をいただきありがとうございました．
またいろいろ議論できたらと思います．

よろしくお願いします．

ビットリバースのところで，『ハッカーのたのしみ』(ヘンリー・S・ウォーレン，ジュニア)に短いアルゴリズムがあったよと教えていただいたのでチェックしました(昔にちらっと見ただけなので忘れてました)．
それは

typedef unsigned int uint32;
 
#ifdef WIN32
uint32 bsr(uint32 x)
{
    __asm {
        bsr eax, x
    }
}
#else
 
#define bsr(x) __builtin_clz(x)
 
#endif
 
void put(uint32 x)
{
    for (int i = 0; i < 32; i++) {
        putchar((x & (1 << (31 - i))) ? '1' : '0');
    }
    printf("\n");
}
 
int main()
{
    uint32 x = 0;
    int len = 31;
    for (int i = 0; i < 32; i++) {
        put(x);
        uint32 s = 31 - bsr(~x);
        x = ((x << s) + (1 << len)) >> s;
    }
}

という感じのコードで，これはこれで面白いです．ただ今回のケースに限っては資料に書いた方法の方が命令数が短くて速いですね．