0xaa和0x55在做什么？

Question

我尝试了谷歌搜索，但找不到任何可理解的@。@...。有人可以用外行的术语解释一下此代码中发生了什么吗？

这是“破解编码面试”一书中的一个问题。

“编写程序以用尽可能少的指令交换整数中的奇数和偶数位（例如，交换位0和位1，交换位2和3，依此类推）”。

我这样做的方式不涉及位操作，因为我无法弄清楚％\ ...

def swap(n):

    b = bin(n)[2:]
    print(b)
    if len(b)%2 != 0:
        c = True
        b = b[0] + b

    pairs = wrap(b, 2)
    pairs = [i[::-1] for i in pairs]
    ans = ''.join(pairs)

    if c: ans = ans[1:]
    print(ans)

但是现在我正在看他们的答案，但我并没有真正理解它（（不是因为它不在Python中）：

int swapOddEvenBits(int x) {
  return ( ((x & 0xaaaaaaaa) >>> 1) | ((x & 0x55555555) << 1) );

Answer 1

让我们分解一下。

return ( ((x & 0xaaaaaaaa) >>> 1) | ((x & 0x55555555) << 1) );

首先，我们来看一下(x & 0xaaaaaaaa)。如果分解0xaaaaaaaa为位级别，则结果为1010 1010 1010 1010 1010 1010 1010 1010（如a，在二进制中为1010）。所以(x & 0xaaaaaaaa)是说，只返回每个偶数放置1在x。这称为位屏蔽。然后，将其右移一个位-这就是使偶数切换位置的方式（因此，现在第二位占据第一位的位置，第四位占据第三位的位置，依此类推）。

您使用(x & 0x55555555)- 做相同的事情-如果将其分解为位级别，则会得到0101 0101 0101 0101 0101 0101 0101 0101（as 5，in binary，is 0101）。这将屏蔽中的所有偶数位x，并为您提供所有奇数位。然后，将所有位左移1。最后，使用or（|）运算符组合两个位序列，这就是您的答案。

示例：让我们以2456086205为例。将其转换为二进制并得到1001 0010 0110 0100 1110 0110 1011 1101。现在，我们做的(x & 0xaaaaaaaa)，并得到

1001 0010 0110 0100 1110 0110 1011 1101 & 1010 1010 1010 1010 1010 1010 1010 1010，

等于1000 0010 0010 0000 1010 0010 1010 1000。将其右移，您会得到0100 0001 0001 0000 0101 0001 0101 0100。

现在，做(x & 0x55555555)，并得到

1001 0010 0110 0100 1110 0110 1011 1101 & 0101 0101 0101 0101 0101 0101 0101 0101，

等于0001 0000 0100 0100 0100 0100 0001 0101。将其向左移动即可0010 0000 1000 1000 1000 1000 0010 1010。

最后，我们做0100 0001 0001 0000 0101 0001 0101 0100 | 0010 0000 1000 1000 1000 1000 0010 1010。然后我们得到0110 0001 1001 1000 1101 1001 0111 1110，如您所见，这就是解决方案！

Answer 2

转换为二进制

0xaaaaaaaa == 0b10101010101010101010101010101010
0x55555555 == 0b01010101010101010101010101010101

这些数字在交替的位置设置为0和1，因此当您&使用其中之一进行编号时，它会每秒提取一次。

如果您使用整数执行swapOddEvenBits过程，假设0b01111100111101001111110000110010，我们得到

0xaaaaaaaa & 0b01111100111101001111110000110010 selects the following bits:
               0 1 1 0 1 1 0 0 1 1 1 0 0 1 0 1     # unselected bits are 0

0x55555555 & 0b01111100111101001111110000110010 selects the following bits:
                1 1 1 0 1 1 1 0 1 1 1 0 0 1 0 0

0 1 1 0 1 1 0 0 1 1 1 0 0 1 0 1 gets shifted right:
 0 1 1 0 1 1 0 0 1 1 1 0 0 1 0 1

and
 1 1 1 0 1 1 1 0 1 1 1 0 0 1 0 0 gets shifted left:
1 1 1 0 1 1 1 0 1 1 1 0 0 1 0 0

and we | the results back together:
 0 1 1 0 1 1 0 0 1 1 1 0 0 1 0 1
1 1 1 0 1 1 1 0 1 1 1 0 0 1 0 0
-------------------------------
10111100111110001111110000110001