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

If you have few bytes of memory to spare, I would start with a lookup 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.

(Plus my ifelse naive idea.)

[Feel free to add yourself and edit my answer].

Please do correct me if you believe the benchmark is incorrect, I am not an expert in reading assembly. So hopefully volatile x prevented caching the result between loops.

I'll ignore the top bits for a second - there's a trick using multiplication. Multiplication is really a convolution operation, and you can use that to shuffle bits.

In particular, assume the two lower bits are AB. Multiply that by 0b0101, and you get ABAB. You'll see that the swapped bits BA are the middle bits.

Hence, x = (x & ~3U) | ((((x&3)*5)>>1)&3)

[edit] The &3 is needed to strip the top A bit, but with std::uint_32_t you can use overflow to lose that bit for free - multiplication then gets you the result BAB0'0000'0000'0000'0000'0000'0000'0000'0000' :

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

I would use

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

Inspired by the table idea, but with the table as a simple constant instead of an array. We just need 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;  
}

This also uses the xor-trick from dyungwang to avoid isolating the top bits.

Another idea, to avoid stripping the top bits. Assume x has the bits XXXXAB, then we want to x-or it with 0000(A^B)(A^B). Thus

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. 

Just looking from a mathematical point of view, I would start with a rotate_left() function, which rotates a list of bits one place to the left (011 becomes 110, then 101, and then back 011), and use this as follows:

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

Using this on the author's example 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;

There is also a shift() function, which can be used (twice!) for replacing the integer division.