反转无符号整数的位

Question

下面两段代码是将一个无符号的32位整数的位取反的方法。但是下面的两个代码有什么区别？为什么第一个代码是错误的，而第二个代码是正确的。我看不出这两者的区别。

public int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        result = result << 1 | (n & (1 << i));
    }
    return result;
}
public int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        result = result << 1 | ((n >> i) & 1);
    }
    return result;
}

感谢任何帮助。

Answer 1

这与从n中抓取的位是存储在结果的最右位还是存储回相同位置有关。

Answer 2

假设n为4（举例）。那么当i为2时，表达式(n & (1 << i)) 变为 (4 & (1 << 2))，它应该等于 4 & 4，因此它的计算结果为 4。但是表达式 ((n >> i) & 1) 变为 ((4 >> 2) & 1)，它应该等于 1 & 1，因此它的计算结果为 1。

两个表达式没有相同的结果。

但是函数的两个版本都尝试以完全相同的方式使用这些结果，因此函数的两个版本没有相同的结果。

Answer 3

第一个代码是错误的，因为它提取给定的位并将其放在与结果数相同的位置。假设您正在进行迭代 i = 5。然后 n & (1 << 5) = n & 32 即 0 或 0b100000。本意是将一位放到最低位置，但是在执行|的时候操作它实际上把它放在相同的位置#5。在随后的迭代中，您将此位移得更高，因此实际上所有位都在最高位位置 or'ed。

请注意，有更有效的算法来反转位，例如在标准 JDK Integer.reverse 方法中实现的算法：

public static int reverse(int i) {
    // HD, Figure 7-1
    i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
    i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
    i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
    i = (i << 24) | ((i & 0xff00) << 8) |
        ((i >>> 8) & 0xff00) | (i >>> 24);
    return i;
}

反转无符号整数的位

Reverse bits of a unsigned integer

java

integer

bit-manipulation