c++ - 完美实现按位非(~)运算符(翻转位)

Question

最近在做位操作相关的事情。到目前为止，我已经尝试了很多位操作操作。但是我卡在了一个操作上。

假设我有 int n = 5;二进制 (101)，现在我想对这个 int 执行按位 NOT，我认为结果是 (010)，但结果是 -6。

但是当我尝试 n = ~(-n) 时，它给了我结果 4(尽管仍然没有得到正确的输出)。请告诉我为什么它显示出这种类型的行为是因为我的 int 不是无符号的。也请告诉我实现该操作的完美方式，以便我可以获得正确的输出。我的主要动机是正确翻转位。

谢谢

Answer 1

int 有多个树位，因此您必须像这样屏蔽按位求反的结果:

int flip(int n) {
    // bitwise AND with 0b111 = 7, this will clear all but the last 3 bits
    return ~n & 0b111;
}

你得到 -6 的原因是因为 int 通常用二进制补码表示，其中 -6 都是 1 位但结束使用 010。您必须删除这些前导 1 位才能获得正确的结果。

通常，我建议不要对有符号数使用按位运算，而是执行以下操作:

unsigned flip(unsigned n) {
    return ~n & 0b111;
}

// this version works with any number of bits, not just 3
unsigned flip(unsigned n, unsigned bits) {
    unsigned mask = (1 << bits) - 1;
    return ~n & mask;
}

如果您不知道您的数字有多少位，则必须先找到最高有效位。以最天真的方式，它可以像这样完成:

unsigned log2(unsigned val)
{
    unsigned result = 0;
    while (val >>= 1) {
        ++result;
    }
    return result;
}

unsigned variable_flip(unsigned n) {
    return flip(n, log2(n));
}

您可以找到更高效的解决方案here .

例如:

unsigned log2_debruijn(uint32_t val) {
    static const unsigned MultiplyDeBruijnBitPosition[32] = {0, 9,  1,  10, 13, 21, 2,  29, 11, 14, 16, 18, 22, 25, 3, 30,
                                                          8, 12, 20, 28, 15, 17, 24, 7,  19, 27, 23, 6,  26, 5,  4, 31};

    // first round down to one less than a power of 2
    // this step is not necessary if val is a power of 2
    val |= val >> 1;
    val |= val >> 2;
    val |= val >> 4;
    val |= val >> 8;
    val |= val >> 16;

    return MultiplyDeBruijnBitPosition[(val * uint32_t{0x07C4ACDD}) >> 27];
}