The fastest way to swap the two lowest bits in an unsigned int in c-CodePudding

Assume that I have:

unsigned int x = 883621;

which in binary is :

00000000000011010111101110100101

I need the fastest way to swap the two lowest bits:

00000000000011010111101110100110

Note: To clarify: If x is 7 (0b111), the output should be still 7.

CodePudding user response：

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 question].

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.

CodePudding user response：

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

CodePudding user response：

I would use

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

CodePudding user response：

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.

CodePudding user response：

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.