8

私は現在、非常に単純なプレオーダートラバーサルアルゴリズムを使用してハフマンツリーのルックアップテーブルを構築しようとしていますが、非常に基本的なビット単位の操作を実行するのに行き詰まっています。疑似コードは次のとおりです。

void preOrder(huffNode *node, int bit) //not sure how to represent bit
{
  if (node == NULL)
    return;

  (1) bit = bit + 0; //I basically want to add a 0 onto this number (01 would go to 010)
  preOrder(node->getLeft(), bit);
  (2) bit = bit - 0 + 1; //This should subtract the last 0 and add a 1 (010 would go to 011)
  preOrder(node->getRight());


}

行（1）と（2）で定義された操作を実行する方法についてかなり混乱しています。

2進数を表現および出力するためにどのデータ型タイプを使用しますか？上記の例では、整数として表された数値がありますが、それは間違いであると確信しています。また、どのように値を加算または減算しますか？私はどのように＆と|を理解しています タイプロジックは機能しますが、コードでこれらの種類の操作を実行する方法について混乱しています。

誰かがいくつかの非常に簡単な例を投稿できますか？

4

3 に答える 3

8

二項演算の基本的な例を次に示します。ここでは主にインプレース操作を使用しました。

int bit = 0x02;   //               0010
bit |= 1;         // OR  0001 ->   0011
bit ^= 1;         // XOR 0001 ->   0010
bit ^= 7;         // XOR 0111 ->   0101
bit &= 14;        // AND 1110 ->   0100
bit <<= 1;        // LSHIFT 1 ->   1000
bit >>= 2;        // RSHIFT 2 ->   0010
bit = ~bit;       // COMPLEMENT -> 1101

2 進数を出力したい場合は、自分で行う必要があります...少し非効率的ですが、適度に読みやすい方法を次に示します。

char bitstr[33] = {0};
for( int b = 0; b < 32; b++ ) {
    if( bit & (1 << (31-b)) )
        bitstr[b] = '1';
    else
        bitstr[b] = '0';
}
printf( "%s\n", bitstr );

[編集]より高速なコードが必要な場合は、0 ～ 255 のすべての数値の 8 ビット シーケンスを含むルックアップ テーブルを事前に生成 (またはハードコード) することがあります。

// This turns a 32-bit integer into a binary string.
char lookup[256][9] = {
    "00000000",
    "00000001",
    "00000010",
    "00000011",
    // ... etc (you don't want to do this by hand)
    "11111111"
};

char * lolo = lookup[val & 0xff];
char * lohi = lookup[(val>>8) & 0xff];
char * hilo = lookup[(val>>16) & 0xff];
char * hihi = lookup[(val>>24) & 0xff];

// This part is maybe a bit lazy =)
char bitstr[33];
sprintf( "%s%s%s%s", hihi, hilo, lohi, lolo );

代わりに、これを行うことができます：

char *bits = bitstr;
while( *hihi ) *bits++ = *hihi++;
while( *hilo ) *bits++ = *hilo++;
while( *lohi ) *bits++ = *lohi++;
while( *lolo ) *bits++ = *lolo++;
*bits = 0;

または、全体を展開するだけです。;-)

char bitstr[33] = {
    hihi[0], hihi[1], hihi[2], hihi[3], hihi[4], hihi[5], hihi[6], hihi[7],
    hilo[0], hilo[1], hilo[2], hilo[3], hilo[4], hilo[5], hilo[6], hilo[7],
    lohi[0], lohi[1], lohi[2], lohi[3], lohi[4], lohi[5], lohi[6], lohi[7],
    lolo[0], lolo[1], lolo[2], lolo[3], lolo[4], lolo[5], lolo[6], lolo[7],
    0 };

もちろん、ルックアップの 8 バイトは 64 ビット整数と同じ長さです... では、これはどうでしょうか。文字配列を無意味に蛇行するよりもはるかに高速です。

char bitstr[33];
__int64 * intbits = (__int64*)bitstr;
intbits[0] = *(__int64*)lookup[(val >> 24) & 0xff];
intbits[1] = *(__int64*)lookup[(val >> 16) & 0xff];
intbits[2] = *(__int64*)lookup[(val >> 8) & 0xff];
intbits[3] = *(__int64*)lookup[val & 0xff];
bitstr[32] = 0;

当然、上記のコードでは、ルックアップ値を文字列ではなく int64 として表します。

とにかく、あなたがそれを書くことができることを指摘するだけで、あなたの目的には適しています. 最適化が必要な場合、物事は楽しくなりますが、ほとんどの実用的なアプリケーションでは、そのような最適化は無視できるか、無意味です。

于 2012-07-30T00:40:36.897 に答える
4

バイナリ シーケンスが int のビット数よりも長くならない限り、int をそのまま使用できます。

a の現在の表現の末尾に 0 を追加するには、<< 1 を使用できます。

a の現在の表現の末尾にある 0 を 1 に置き換えるには、a ^= 1 を使用できます。

このように int を使用するには、int のどこでビットが開始するかを追跡する必要があることに注意してください。たとえば、値が 0x0 の場合、0、00、000、..です。

于 2012-07-30T00:32:46.937 に答える
2

コード内の操作:

(1) bit = bit << 1;
(2) bit = bit|1;

ただし、シーケンスの長さも維持する必要があります。

int の長さで十分な場合は、使用しない理由はありません。ただし、ハフマンアルゴリズムでは、実際にはデータに依存します。C++ プログラマーは、任意の長さのビット シーケンスに boost::dynamic_bitset を使用する必要があります。また、上記のビット操作もサポートしています。http://www.boost.org/doc/libs/1_42_0/libs/dynamic_bitset/dynamic_bitset.html

于 2012-07-30T00:47:53.243 に答える