bitCount()的大O？

Question

什么是位计数的大O？我不知道这个方法是如何工作的，但我假设它是在O(logn)中完成的。

特别针对此代码(其中x= 4，y= 1)：

return Integer.bitCount(x^y);

Answer 1

给定它的实现，该方法由6个按顺序执行的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;
}

Answer 3

任何在有限大小输入上工作的算法都具有O(1)的复杂性。

bitCount用于有限大小的输入。

因此，bitCount具有O(1)的复杂性。