c++ - 如何交换前 2 个连续的不同位

Question

交换无符号整数中前 2 个不同连续位的快速而优雅的方法是什么？

例如

100100 -> 100010
110011 -> 110101

到目前为止，我想到了这个:

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

我对上述解决方案最大的不满是它使用了if指令。

Answer 1

我会这样做:

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

当数字 == 0 时，我的解决方案返回 0，而原始问题的函数返回 11000000000000000000000000000000000000000000000000000000000000000。

一些解释:x 的位如果这个位置的位与下一位相等则包含 0，如果不同则包含 1。 (x & -x)是x的最低位，也就是第一个位差。