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 ;