

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

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


CC BY-SA 3.0
2015-03-05T12:44:40.957
7494
2015-04-16T18:58:55.377
8707
question
c アルゴリズム
ビットスワップの方法


ビット反転処理をストレートに実装したコードです。`x`が入力値、`b`がビット長。

[code]

    unsigned swapbit(unsigned x, int b) {
      unsigned r = 0;
      while (b--) {
        r <<= 1;
        r |= (x & 1);
        x >>= 1;
      }
      return r;
    }
    
[/code]

LiveDemo: <http://melpon.org/wandbox/permlink/XVsAjckDHC9g0W06>


CC BY-SA 3.0
2015-03-05T14:13:31.730
7500
2015-03-05T14:13:31.730
49
7494
answer

[code]

    static const unsigned char BitReverseTable256[256] = 
    {
     #   define R2(n)     n,     n + 2*64,     n + 1*64,     n + 3*64
     #   define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
     #   define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )
         R6(0), R6(2), R6(1), R6(3)
    };
    
    unsigned int reversebits(unsigned int x)
    {
      const size_t sz = sizeof x * CHAR_BITS;
      const unsigned int MASK = (1U << CHAR_BITS) - 1U;
      unsigned int ret = 0U;
      assert(CHAR_BITS == 8);  /* Table size is 256 */
      while(sz--) {
        ret = (ret << CHAR_BIT) | (unsigned int)BitReverseTable256[x & MASK];
        x >>= CHAR_BIT;
      }
      return ret;
    }
    
[/code]

BitReverseTable256
の作り方は[ここ](https://stackoverflow.com/questions/15107398/algorithm-behind-the-
generation-of-the-reverse-bits-lookup-table8-bit)。

例：16ビットinteger

[code]

          x              |  sz   |     ret
    ---------------------+-------+---------------------
    0001 1010 1100 1000  |  2    | 0000 0000 0000 0000
    0000 0000 0001 1010  |  1    | 0000 0000 0001 0011
    0000 0000 0000 0000  |  0    | 0001 0011 0101 1000
    
[/code]

0001 1010 1100 1000 ---> 0001 0011 0101 1000


CC BY-SA 3.0
2015-04-16T12:01:43.410
9233
2015-04-16T12:01:43.410
2017-05-23T12:38:56.083
-1
9348
7494
answer


ビット長が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` が得られ、反転できていることが分かります。


CC BY-SA 3.0
2015-04-16T18:48:22.603
9239
2015-04-16T18:58:55.377
2015-04-16T18:58:55.377
7831
7831
7494
answer