无符号整数的反向位

问题描述：

下面两个代码是该方法可以反转无符号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; 
}

感谢您的帮助。

答

第一个代码是错误的，因为它提取给定位并将其放在结果数字的相同位置。假设您正在迭代i = 5。然后n & (1 << 5) = n & 32这是0或0b100000。意图是将1位置于最低位置，但在执行|时它实际上将它放到了＃5的相同位置。在随后的迭代中，您将该位移动得更高，因此实际上将所有位或位置设置为最高位。

请注意，有扭转像一个在标准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; 
}

答

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

答

假设n是4（例如）。然后，当i是2时，表达(n & (1 << i)) 变得(4 & (1 << 2))，这应该等于4 & 4，所以它的计算结果为4. 但表达((n >> i) & 1) 变得((4 >> 2) & 1)，其应该等于1 & 1，所以它的计算结果为1

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

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

无符号整数的反向位

相关推荐