Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to swap first 2 consecutive different bits

What would be a fast and elegant way to swap the first (least significant) 2 different consecutive bits in an unsigned integer?

E.g.

100100 -> 100010
110011 -> 110101

So far I came up with this:

unsigned long long special_swap(unsigned long long number)
{
    if (number & 1)
        return (number + 1) ^ ((number ^ (number + 1)) >> 2);
    number = ~number;
    return ~((number + 1) ^ ((number ^ (number + 1)) >> 2));
}

My biggest discontent with the above solution is that it uses the if instruction.

like image 695
kaspersky Avatar asked Nov 04 '15 21:11

kaspersky


People also ask

How do you swap two bits in a number?

Method 1: The idea is to first find the bits, then use XOR based swapping concept, i..e., to swap two numbers 'x' and 'y', we do x = x ^ y, y = y ^ x, and x = x ^ y.


1 Answers

This is how I would do it:

unsigned long long my_swap(unsigned long long number)
{
 unsigned long long x = number ^ (number >> 1);
 return number ^ ((x & -x) * 3);
}

My solution returns 0 when number == 0, whereas the function of the original question returns 1100000000000000000000000000000000000000000000000000000000000000.

Some explanations: the bits of x contain 0 if the bit at this position is equal to the next bit, and 1 if it is different. (x & -x) is the least significant bit of x, that is to say the first bit difference.

like image 115
Rémi Avatar answered Oct 09 '22 16:10

Rémi