java - 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

该代码是

1. 破坏了一半可能的位模式(所有负数)，并且
2. O(n)，而不是 O(log n)，其中 n 是 a 中的位数
3. 效率非常低
4. 写得困惑

该算法仅适用于正数，并且:

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 ;