ビットスワップの方法


固定ビット長さ（例16bit）のビットの順序をビット単位で反転（スワップ）する方法を教えてください。  
例：0001 1010 1100 1000 を 0001 0011 0101 1000

C言語の標準ライブラリに含まれる関数だけを使用するものとしますが、ワークエリアについては特に制限をもうけません。




ビット長が2のべき乗と仮定できる場合ならこういう手も。  
下のコードでは最大32ビットまで対応。

[code]

    /* ビット長が bits の整数 x のビットを逆転する */
    unsigned reversebits(unsigned x, int bits)
    {
        /*
         * unsigned が32ビット以上であることを仮定している。
         * 16ビットなら case 32: とその直下の行を消した上で、
         * 各マスクの長さを半分にすれば対応可能。
         */
        assert(sizeof(x) * CHAR_BIT >= 32);
    
        /* bits は32以下の2のべき乗でなければならない */
        assert(bits <= 32);
        assert((bits & (bits - 1)) == 0);
    
        switch(bits)
        {
        case 32:
            x = ((x & 0x0000ffff) << 16) | ((x >> 16) & 0x0000ffff);
        case 16:
            x = ((x & 0x00ff00ff) <<  8) | ((x >>  8) & 0x00ff00ff);
        case 8:
            x = ((x & 0x0f0f0f0f) <<  4) | ((x >>  4) & 0x0f0f0f0f);
        case 4:
            x = ((x & 0x33333333) <<  2) | ((x >>  2) & 0x33333333);
        case 2:
            x = ((x & 0x55555555) <<  1) | ((x >>  1) & 0x55555555);
        default:
            break;
        }
        return x;
    }
    
[/code]

### やっていること

まず、整数の上位半分と下位半分をごっそり入れ替える。  
次に、その半分についてさらにその半分を入れ替える。  
以下同様に、半分にできなくなるまで入れ替えを繰り返していくと、最終的に全体が反転する。

### 例

8ビット数 `abcdefgh` (`a` 〜 `h` はそれぞれ0または1) をこの方法で反転させます。

元の数: `abcdefgh`  
全体の半分を入れ替え: `abcd efgh` → `efgh abcd` (上コード `case 8:` 直下に対応)  
さらに半分を入れ替え: `ef gh ab cd` → `gh ef cd ab` (上コード `case 4:` 直下に対応)  
さらに半分を入れ替え: `g h e f c d a b` → `h g f e d c b a` (上コード `case 2:` 直下に対応)

これで、最終的に `hgfedcba` が得られ、反転できていることが分かります。

