如何在C++中操作和表示二进制数

Question

我目前正在尝试使用一种相当简单的先序遍历算法来构建哈夫曼树的查找表，但是我在执行非常基本的比特运算时卡住了。以下是伪代码：

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）行定义的操作感到非常困惑。

在表示和打印二进制数时，应该使用哪种数据类型？在上面的例子中，我将数字表示为int，但我相当确信那是不正确的。另外，你如何添加或减去值？我明白&和|类型逻辑如何工作，但我对如何在代码中执行这些操作感到困惑。

可以有人发布一些非常简单的示例吗？

- Wakka Wakka Wakka

Answer 1

这里是一些基本的二进制操作示例。我主要使用了就地操作。

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

如果你想要打印一个二进制数，则需要自己创建方法......以下是一种不太高效但易于阅读的方法:

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而不是字符串。

无论如何，只要指出您可以根据您的目的编写它。如果您需要进行优化，那么事情会变得有趣，但对于大多数实际应用程序来说，这些优化是微不足道或毫无意义的。

- paddy

---

哇，真不错，我一直在尝试做一些很酷的事情。非常感谢！ - Wakka Wakka Wakka

快速问题..我最终回到了这个问题，为什么不直接打印出二进制数，如下所示： for (int i = length; i> 0; i--) { cout << bit%2 << " "; bit /= 2; } - Wakka Wakka Wakka

我真是该死，无法在评论中发布代码...但是快速查看一下那个for循环。像那样打印二进制数不是更容易吗？或者这种方法有什么劣势吗？ - Wakka Wakka Wakka

当然……你觉得怎么方便就怎么做。我只是暗示我的方法是众多方法之一。我会根据当时的心情写代码。我更喜欢避免多次调用流输出函数，所以我将其生成为一个字符串以供更通用的使用。如果你想要快速操作，你可能会生成一个字符串，但不会像我上面那样冗长。你也应该避免模数和除法运算符，除非你对编译器的优化有很大的信心。 - paddy

如果您尝试编写快速的代码，我添加了一些替代方案，这可能会对您感兴趣。 - paddy

Answer 2

除非您的二进制序列长度超过int位数，否则您可以直接使用int。

要在a的当前表示末尾添加0，可以使用 a << 1

要用1替换a当前表示末尾的0，可以使用 a ^= 1

请注意，要以这种方式使用int，您还需要跟踪您的位在int中从哪里开始，这样如果您有例如值0x0，您就可以知道其中的0、00、000等是哪一个。

- David

Answer 3

您的代码中的操作：

(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。

- Pavel Radzivilovsky