反向位算法

Question

这是一个非常明显和简单的问题，不幸的是我遇到了一些麻烦。反转给定整数中的位（不是 inverting/flipping 位），使 MSB 变为 LSB，MSB-1 变为 LSB+1，依此类推。在我看来，我想到的做法是将输入的最后一位存储到输出变量中，每次将该变量右移 1，然后将输入左移 1，然后重复该过程。这是我到目前为止编写的函数：

unsigned int oldRev(unsigned int input){
    unsigned int output = 0;    

    for(int i=0; i<((sizeof(int)*8)-1); i++){
        output |= input&1;
        output <<= 1;
        input >>= 1;
    }    

    return output;    

}

当我尝试执行 oldRev(2147483648) 时出现问题，其中输入中只有最高有效位为 1。输出应该只是 1，但我得到 0。为什么会这样？我一直试图用我的逻辑找出问题，但到目前为止一直没有成功。我已经在网上看到了各种这样做的方法，但仍然想知道我做错了什么。

提前致谢！

Answer 1

您需要调换两个操作的顺序：

    output <<= 1;
    output |= input&1;

要理解原因，请查看现有代码并宣称它最终会生成一个 output，其最后一位将始终为 0。因为最后一件事将对 output，不管你的int有多大，总是左移操作。这将始终将 output 的最后一位保留为 0。这显然是错误的。

此外，由于 int 中有 sizeof(int)*8 位，循环显然必须迭代 sizeof(int)*8 次，以处理该位，但是：

for(int i=0; i<((sizeof(int)*8)-1); i++){

这会迭代 sizeof(int)*8-1 次。比要求的数量少一。这应该是：

for(int i=0; i<sizeof(int)*8; i++){

反向位算法

Reverse Bits Algorithm

c++

reverse

bit-manipulation