Java - Большой О BitCount()?

Question

Что такое Big O количества бит? Я не уверен, как метод работает, но я бы предположил, что это сделано в O(logn).

В частности, с этим кодом (где х = 4, у = 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;
}

Answer 3

Любой алгоритм, работающий с вводом ограниченного размера, имеет сложность.

работает с вводом ограниченного размера.

Следовательно bitCount иметь сложность O(1).