如何在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,但我很确定这是不正确的.另外,如何添加或减去值？我理解&和| 类型逻辑工作,但我对如何在代码中执行这些类型的操作感到困惑.

有人会发一些非常简单的例子吗？

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 );

[编辑]如果我想要更快的代码,我可以预先生成(或硬编码)具有8位序列的查找表,用于0-255的所有数字.

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

无论如何,只是指出你可以写它但是适合你的目的.如果你需要优化,事情会变得有趣,但对于大多数实际应用来说,这种优化可以忽略不计或毫无意义.