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）

回答

相關問題