Java 中的反转位 - O(n)

Question

我试图理解这段在 O(n) 时间内反转位的代码。我了解时间复杂度，但无法理解这段代码背后的逻辑。

public static long reverse(long a) {
    long result = 0;
    int i = 31;
    while(a > 0){

        result += (a % 2) * Math.pow(2, i);
        i--;                        
        a = a/2;
    }
    return result;
}

为简单起见，例如，如果我取 12（1100）且仅取 4 位（设置 i = 3），我的输出将是 3（0011）。我明白了，我也能得出答案。

但是有人可以解释这段代码背后的逻辑吗？谢谢！

Answer 1

那个密码是

中断了一半可能的位模式（所有负数），并且
O(n)，而不是 O(log n)，其中 n 是 a
效率很低
写得乱七八糟

该算法仅适用于正数并且：

extract the rightmost bit from a
set the corresponding bit from the left end
shift a one position to the right

它重复 a > 0。如果 a 的值有一些前导零位，那么这个算法会比 O(n) 好一点。

尽管现代编译器应该能够将 a/2 转换为 a >> 1 和 a%2 到 a & 0x00000001。但是我不知道它是否会将 Math.pow(2, i) 识别为 0x00000001 << i;

Answer 2

这是解释

i = 31 //number of bits in integer

以下分为两部分

result += (a % 2) * Math.pow(2, i);

(a % 2) 计算最后一位。乘以 2 的正幂具有左移位的效果。 (Math.pow(2, i) 向左移动 i 次。

所以我们计算的是单位位置位，把它放在从单位位置开始的第i个位置，也就是从右边算起(31 - i)，这有效地把位的位置从左到右反转了。

最后

i--; //move to next bit
a = a/2; //chop the unit place bit to proceed to next.

就是这样。

Java 中的反转位 - O(n)

reverse bits in Java - O(n)

java

reverse

bits

bit-manipulation