固定ビット長さ(例16bit)のビットの順序をビット単位で反転(スワップ)する方法を教えてください。
例:0001 1010 1100 1000 を 0001 0011 0101 1000
C言語の標準ライブラリに含まれる関数だけを使用するものとしますが、ワークエリアについては特に制限をもうけません。
スタック・オーバーフローはプログラマーとプログラミングに熱心な人のためのQ&Aサイトです。すぐ登録できます。
登録してこのコミュニティに参加するビット長が2のべき乗と仮定できる場合ならこういう手も。
下のコードでは最大32ビットまで対応。
/* ビット長が 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;
}
まず、整数の上位半分と下位半分をごっそり入れ替える。
次に、その半分についてさらにその半分を入れ替える。
以下同様に、半分にできなくなるまで入れ替えを繰り返していくと、最終的に全体が反転する。
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
が得られ、反転できていることが分かります。
ビット反転処理をストレートに実装したコードです。x
が入力値、b
がビット長。
unsigned swapbit(unsigned x, int b) {
unsigned r = 0;
while (b--) {
r <<= 1;
r |= (x & 1);
x >>= 1;
}
return r;
}
LiveDemo: http://melpon.org/wandbox/permlink/XVsAjckDHC9g0W06
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;
}
BitReverseTable256 の作り方はここ。
例:16ビットinteger
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
0001 1010 1100 1000 ---> 0001 0011 0101 1000