在 C++ 中交换 unsigned int 中两个最低位的最快方法

Question

假设我有：

unsigned int x = 883621;

二进制形式是：

00000000000011010111101110100101

我需要最快的方法来交换两个最低位：

00000000000011010111101110100110

注意：澄清一下：如果 x 为 7 (0b111)，则输出仍应为 7。

Answer 1

如果你有几个字节的空闲内存，我会从一个查找表开始：

constexpr unsigned int table[]={0b00,0b10,0b01,0b11};

unsigned int func(unsigned int x){
    auto y = (x & (~0b11)) |( table[x&0b11]);
    return y;  
}

-O3到目前为止所有答案的Quickbench。

-Ofast到目前为止所有答案的Quickbench。

（加上我ifelse天真的想法。）

[随意添加你自己并编辑我的答案]。

如果您认为基准测试不正确，请纠正我，我不是阅读汇编的专家。因此希望volatile x能够防止在循环之间缓存结果。

Answer 2

我暂时忽略最高位——有一个使用乘法的技巧。乘法实际上是一种卷积运算，您可以使用它来打乱位。

特别地，假设两个较低位是AB。将其乘以 0b0101，即可得到 ABAB。您将看到交换的位 BA 是中间位。

因此，x =(x & ~3U) | ((((x&3)*5)>>1)&3)

[编辑] 需要 &3 来去除顶部 A 位，但是使用 std::uint_32_t 你可以使用溢出来免费丢失该位 - 乘法然后得到结果 BAB0'0000'0000'0000'0000'0000'0000 ‘0000’0000’：

x = (x & ~3U) | ((((x&3)*0xA0000000)>>30));

Answer 3

我会用

x = (x & ~0b11) | ((x & 0b10) >> 1) | ((x & 0b01) << 1);

Answer 4

受到表想法的启发，但将表作为一个简单的常量而不是数组。我们只需要 mask(00)==00、mask(01)==11、mask(10)=11、mask(11)==11。

constexpr unsigned int table = 0b00111100;

unsigned int func(unsigned int x) {
    auto xormask = (table >> ((x&3) * 2)) &3;
    x ^= xormask;
    return x;  
}

这也使用了 dyungwang 的异或技巧来避免隔离最高位。