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.
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With