ビット列の逆順アルゴリズム

最初からjava言語のような超高級言語の便利ライブラリにどっぷり浸かっているダメプログラマは、最適なアルゴリズムを考えるのが苦手だ。最近は実行効率よりもコードの読みやすさを求められる場合が多いので、ますますそんな傾向は強くなりそう。

そんなわけで頭の体操の代わりにビット列の逆順を作る 10001101→10110001 のように左右を入れ替えるアルゴリズムを考えてみるがよかろう、と指令を受けて考えているのだがムズカシイ。

すぐに思いつくのはこんなの。上位４ビットと下位４ビットを入れ替え、次に、２ビットずつに分けて隣同士入れ替え、最後に全てのビットを隣同士入れ替える。考え方はマージソートと同じか。

void printBit(unsigned char c){
    int i;
    for (i = 7; i >= 0; i--) {
        printf("%d", (c >> i) & 1);
    }
    printf("\\n");
}
int main(int argc, char* argv[]){
    unsigned char c = atoi(argv[1]);
    printBit(c);
    c = (c >> 4) | (c << 4);
    c = ((c & 0xCC ) >> 2) | ((c & 0x33 ) << 2);
    c = ((c & 0xAA ) >> 1) | ((c & 0x55 ) << 1);
    printBit(c);
}

1ビット目が立っていたら128を加え、2ビット目が立っていたら64を加え・・、以下8ビット目まで繰り返してみる力押し。そのままプログラムしても面白くないので一ひねり。

int main(int argc, char* argv[]){
    unsigned char c = atoi(argv[1]);
    printBit(c);
    unsigned char r = 0;
    unsigned char h = 128;
    int i;
    for (i = 8; i > 0; i--) {
        r = r | ((c & 1) * h );
        c = c >> 1;
        h = h >> 1;
    }
    printBit(r);
    return 1;
}

こんな方法しか思いつかない。上のコードはunsigned charのビット列を前提にしているが、ビットが増えてもまったく同じ計算回数で入れ替えられるアルゴリズムがあるらしい。

んで、正解は「変換テーブルを使え」だそうです。CPUによっては逆順に読み出せる命令があるらしいです。