如何交换前 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

这与不使用 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);
}

变量 t 为 1 或 -1，具体取决于数字的 lsb。

Test it live

Answer 2

我会这样做：

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

我的解法returns 0 when number == 0，而原题的函数returns 11000000000000000000000000000000000000000000000000000000000000000.

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

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

How to swap first 2 consecutive different bits

c++

bit-manipulation