CODEWITHSUNDEEP
c++bit-manipulation
kaspersky
kaspersky

Reputation: 4117

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.

Upvotes: 8

Views: 386

Answers (2)

Rémi
Rémi

Reputation: 3744

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.

Upvotes: 4

alain
alain

Reputation: 12057

This is the same idea without using an if.

unsigned long long special_swap(unsigned long long number)
{
    unsigned long long t = ((number & 1) << 1) - 1;
    return (number + t) ^ ((number ^ (number + t)) >> 2);
}

The variable t is either 1 or -1, depending on the lsb of the number.

Test it live

Upvotes: 3

Related Questions