4

このような：

input:  10010011
(10->01->00->11)

output: 11000110
(11->00->01->10)


input:  11010001
(11->01->00->01)

output: 01000111
(01->00->01->11)

誰かそれについて何か考えがありますか？

4

7 に答える 7

7

lserniのアルゴリズムよりも少ない操作：

uint32_t reverseByTwo(uint32_t value) {
    value = ((value & 0x03030303) << 2) | ((value >> 2) & 0x03030303); // swap adjacent pairs
    value = ((value & 0x0F0F0F0F) << 4) | ((value >> 4) & 0x0F0F0F0F); // swap nibbles
    value = ((value & 0x00FF00FF) << 8) | ((value >> 8) & 0x00FF00FF); // swap bytes
    value = ((value & 0x0000FFFF) << 16) | ((value >> 16) & 0x0000FFFF);
    return value;
}

64ビット値の場合は、32ビットの半分に別のスワップを追加するだけです。小さいタイプの場合は、最後のいくつかのスワップを省略します。

于 2012-08-30T20:56:29.020 に答える
3

奇妙なリクエスト。私はこのようにします：

uint32_t reverseByTwo(uint32_t value)
{
    int i;
    uint32_t new_value = 0;
    for (i = 0; i < 16; i++)
    {
        new_value <<= 2;            
        new_value |= (value & 0x3);
        value >>= 2;
    }
    return new_value;
}

各反復で、値の2つのLSBがnew_valueの2つのLSBに配置され、左にシフトされます。

8ビット値の場合、

uint8_t reverseByTwo(uint8_t value)
{
    int i;
    uint32_t new_value = 0;
    for (i = 0; i < 4; i++)
    {
        new_value <<= 2;            
        new_value |= (value & 0x3);
        value >>= 2;
    }
    return new_value;
}

パフォーマンスが貴重な場合は、手動でループを展開し（GCCはこれを単独で実行する必要がありますが、気にしない場合もあります）、関数をとして宣言できますinline。

    new_value = 0;
    // new_value <<= 2; // First time not necessary
    new_value |= (value & 0x3);
    value >>= 2;
    new_value <<= 2;            
    new_value |= (value & 0x3);
    value >>= 2;
    new_value <<= 2;            
    new_value |= (value & 0x3);
    value >>= 2;
    new_value <<= 2;            
    new_value |= (value & 0x3);
    // value >>= 2; 
    return new_value;
于 2012-08-30T20:45:03.257 に答える
2

1バイト（char）のビットを別の1バイトに変換する最も速い方法は、自分で配列を作成することです。

unsigned char rev[256];
rev[0]   = 0;     /* 00000000 -> 00000000 */
...
rev[147] = 198;   /* 10010011 -> 11000110 */
...
rev[198] = 147;   /* 11000110 -> 10010011 */
...
rev[255] = 255;   /* 11111111 -> 11111111 */

数値xをビット反転形式に変換するには、と書くだけrev[x]です。4バイトのように、変換するバイトが複数ある場合は、テーブルintで4バイトを検索するだけです。rev

このコードを書くときは、バイナリを別のベース（ここでは10進数を使用）に変換する必要があります。これは、Cにバイナリ定数（8進数の定数よりも10倍便利）がないためです。

値を初期化子に入れることもできますが、すべてが正しい場所にあることを確認するために位置をカウントする必要があります。（たぶんそれをするための小さなプログラムを書いてください！）

unsigned char rev[256] = {0, ..., 198, ..., 147, ..., 255};

...適切な場所に他のすべての番号を入力します。

于 2012-08-30T21:22:41.533 に答える
1 
$x = (($x & 0x33333333) << 2) | (($x & 0xCCCCCCCC) >> 2);
$x = (($x & 0x0F0F0F0F) << 4) | (($x & 0xFOFOFOFO) >> 4);
$x = (($x & 0x00FF00FF) << 8) | (($x & 0xFF00FF00) >> 8);
$x = (($x & 0x0000FFFF) << 16) | (($x & 0xFFFF0000) >> 16);

正当な理由で、このアルゴリズムはヘンリーS.ウォーレンジュニアによる「ハッカーのたのしみ」から来ました。唯一の違いは、本のアルゴリズムがペアで逆転しなかったことです。ビットを逆にしただけです。

于 2012-08-30T21:14:22.743 に答える
0 
#include <limits.h>

#define INT_BITS  (sizeof(int) * CHAR_BIT)

unsigned reverse_bits(unsigned x) {
#define PAIR(i)       ((((x) >> (i*2)) & 3) << (INT_BITS - (i+1)*2))
    unsigned result = 0;
    unsigned i;
    for(i = 0; i < INT_BITS/2; i++) {
        result |= PAIR(i);
    }
    return result;
}

これはunsignedintに対してはそれを行いますが、intandで置き換えたい場合unsignedがcharありunsigned charます。

于 2012-08-30T20:54:36.387 に答える
0

可能な限り最速にしたい場合：

output =
  ((input & 0xc0) >> 6) |
  ((input & 0x30) >> 2) |
  ((input & 0xc) << 2) |
  ((input & 0x3) << 6);
于 2012-08-30T20:56:43.420 に答える
0

あなたはビット（ab cd ef gh）を持っていて、欲しい（gh ef cd ab）
0x101を掛けて、16ビットintに格納すると、（ab cd ef gh ab cd ef gh）が得られます。
次に、4ビットの2つのグループにその数のビットパターンがあります。

  • （00 00 ef 00 ab 00 00 00）、
  • （00 00 00 gh 00 cd 00 00）

だからあなたはただ適切にシフトしてマスクする必要があります

unsigned char swap_bit_pairs(unsigned char b)
{
    unsigned int a = 0x101*b;
    return ((a >> 6) & 0x33) | ((a >> 2) & 0xCC);
}

したがって、6つの操作で可能です

編集：おっと！0xCCの代わりに0x66を書きました

于 2012-08-31T10:48:50.573 に答える