Logn Integral Part

http://wxx5433.github.io/logn-integral-part.html

Implement the integral part logn base 2 with bit manipulations

Analysis

This problem can be very easily solved using bit manipulation. However, we must ask the interviewer what the input type is. Is it integer or can be float number?

1. Negative or zero input -> invalid
2. If input is positive integer -> no tricy part
3. If input is positive float number -> we can cast to integer and only remain the integral part.

For example, 3.99f can be cast to 3, which will give the same result.

Time complexity of this method is O(n), n is the length of the binary representation of this number.

This can be acclerated on hardware level. It is easy to use binary merge to get the count of 1 bits.

public static int getIntegralPart (float n) {
    if (n <= 0) {  // invalid input
        return -1;
    }
    int result = 0;
    int num = (int)n;
    while ((num >>= 1) != 0) {
        ++result;
    }
    return result;
}