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

Question

假设我有：

unsigned int x = 883621;

二进制是：

00000000000011010111101110100101

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

00000000000011010111101110100110

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

Answer 1

我会用

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

Answer 2

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

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

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

Quickbench -O3 of all the answers so far.

Quickbench -Ofast of all the answers so far.

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

[随时添加您自己并编辑我的答案]。

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

Answer 3

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

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

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

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

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

Answer 4

另一个想法，避免剥离最高位。假设 x 的位为 XXXXAB，那么我们想用 0000(A^B)(A^B) 对它进行 x 或运算。于是

auto t = x^(x>>1); // Last bit is now A^B
t &=1; // take just that bit
t *= 3; // Put in the last two positions
x ^= t; // Change A to B and B to A.

Answer 5

受到 table 想法的启发，但将 table 作为一个简单的常量而不是数组。我们只需要 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 的异或技巧来避免隔离最高位。

Answer 6

从数学的角度来看，我将从 rotate_left() 函数开始，它将位列表向左旋转一位（011 变为 110，然后 101，然后返回 011)，并按如下方式使用：

int func(int input){
  return rotate_left(rotate_left((input / 4))) + rotate_left(input % 4);
}

在作者的例子中使用这个11010111101110100101:

input = 11010111101110100101;
input / 4 = 110101111011101001;
rotate_left(input / 4) = 1101011110111010010;
rotate_left(rotate_left(input / 4) = 11010111101110100100;

input % 4 = 01;
rotate_left(input % 4) = 10;

return 11010111101110100110;

还有一个shift()函数，可以用来（两次！）代替整数除法。

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

The fastest way to swap the two lowest bits in an unsigned int in C++

c++

binary

bitwise-operators