Java中的反向位 - O（n）

我想了解这个代码，它反转O（n）时间的位。我了解时间复杂性，但我无法理解此代码背后的逻辑。Java中的反向位 - 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）。我明白了，我也能够得出答案。

但有人能解释这个代码背后的逻辑吗？谢谢！

来源

2016-07-30 Ravi Krishna

奇怪调用这个O（log n）的，因为我宁愿称之为位的数量，我，问题大小，然后它是O（我）。 – Harald

@Harald我认为他指的是运行时复杂性。 – 11thdimension

@Harald你是对的，位数是输入大小，这使得它'O（n）' – 11thdimension

这里的解释

i = 31 //number of bits in integer

下面有两个部分

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

(a % 2)计算最后一位。用2的正数乘以任何值会产生左移位的效果。（Math.pow(2, i)移位到左i倍。

所以我们计算单元地点位并将其放置在从单元地点，这是从右侧，这将有效地撤消由左到右位的位置(31 - i)第i个位置。

最后

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

就是这样。

来源

2016-07-30 05:59:27 11thdimension

更新它谢谢你的解释！ –

该代码是

打破了一半的可能位模式（所有的负数），和
为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;

来源

2016-07-30 05:58:08

Java中的反向位 - O（n）

回答

相关问题