Java - Big O of bitCount()?

Question

What is the Big O of bit count? I'm not sure how the method works, but I would assume it is done in O(logn).

Specifically with this code (where x = 4, y = 1):

return Integer.bitCount(x^y);

Answer 1

Given its implementation, the method consists of six O(1) statements performed in sequence, so it's 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

It is O(1), here is its implementation for 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

Any algorithm that work on input of limited size have complexity of O(1).

bitCount works with input of limited size.

Therefore bitCount have complexity of O(1).