Java - bitCount（）的大O？

Question

位數大是什麼？我不知道該方法如何工作，但我會認爲它在O（logn）中完成。

具體而言，此代碼（其中x = 4，Y = 1）：

return Integer.bitCount(x^y); 

Answer 1

鑑於其實現方式中，方法包括六個O（1）在序列進行語句，所以它的O（1） 。

public static int bitCount(int i) { 
    // HD, Figure 5-2 
    i = i - ((i >>> 1) & 0x55555555); 
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); 
    i = (i + (i >>> 4)) & 0x0f0f0f0f; 
    i = i + (i >>> 8); 
    i = i + (i >>> 16); 
    return i & 0x3f; 
} 

Answer 2

這是O(1)，這裏其JDK 1.5+實現：

public static int bitCount(int i) { 
    i = i - ((i >>> 1) & 0x55555555); 
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); 
    i = (i + (i >>> 4)) & 0x0f0f0f0f; 
    i = i + (i >>> 8); 
    i = i + (i >>> 16); 
    return i & 0x3f; 
}