How do you calculate log base 2 in Java for integers?

Question

I use following function to calculate log base 2 for integers:

public static int log2(int n){
    if(n <= 0) throw new IllegalArgumentException();
    return 31 - Integer.numberOfLeadingZeros(n);
}

Does it has optimal performance?

Does someone know ready J2SE API function for that purpose?

UPD1 Surprisingly for me, float point arithmetics appears to be faster than integer arithmetics

UPD2 Due to comments i will conduct more detailed investigation

UPD3 My integer arithmetic function is 10 times faster than Math.log(n)/Math.log(2).

Answer 1

Math.log(x)/Math.log(2)

That's the usual accepted way. There isn't a built in function for log2, but making one is trivial and will give your code better cohesion.

(if you remember from math class, log10 x = ln x / ln 10) :D

Answer 2

Why not:

public static double log2(int n)
{
    return (Math.log(n) / Math.log(2));
}

Answer 3

Try Math.log(x) / Math.log(2)

Answer 4

you can use the identity

            log[a]x
 log[b]x = ---------
            log[a]b

so this would be applicable for log2.

            log[10]x
 log[2]x = ----------
            log[10]2

just plug this into the java Math log10 method....

http://mathforum.org/library/drmath/view/55565.html

Answer 5

If you are thinking about using floating-point to help with integer arithmetics, you have to be careful.

I usually try to avoid FP calculations whenever possible.

Floating-point operations are not exact. You can never know for sure what will (int)(Math.log(65536)/Math.log(2)) evaluate to. For example, Math.ceil(Math.log(1<<29) / Math.log(2)) is 30 on my PC where mathematically it should be exactly 29. I didn't find a value for x where (int)(Math.log(x)/Math.log(2)) fails (just because there are only 32 "dangerous" values), but it does not mean that it will work the same way on any PC.

The usual trick here is using "epsilon" when rounding. Like (int)(Math.log(x)/Math.log(2)+1e-10) should never fail. The choice of this "epsilon" is not a trivial task.

More demonstration, using a more general task - trying to implement int log(int x, int base):

The testing code:

static int pow(int base, int power) {
    int result = 1;
    for (int i = 0; i < power; i++)
        result *= base;
    return result;
}

private static void test(int base, int pow) {
    int x = pow(base, pow);
    if (pow != log(x, base))
        System.out.println(String.format("error at %d^%d", base, pow));
    if(pow!=0 && (pow-1) != log(x-1, base))
        System.out.println(String.format("error at %d^%d-1", base, pow));
}

public static void main(String[] args) {
    for (int base = 2; base < 500; base++) {
        int maxPow = (int) (Math.log(Integer.MAX_VALUE) / Math.log(base));
        for (int pow = 0; pow <= maxPow; pow++) {
            test(base, pow);
        }
    }
}

If we use the most straight-forward implementation of logarithm,

static int log(int x, int base)
{
    return (int) (Math.log(x) / Math.log(base));
}

this prints:

error at 3^5
error at 3^10
error at 3^13
error at 3^15
error at 3^17
error at 9^5
error at 10^3
error at 10^6
error at 10^9
error at 11^7
error at 12^7
...

To completely get rid of errors I had to add epsilon which is between 1e-11 and 1e-14. Could you have told this before testing? I definitely could not.

Answer 6

This is the function that I use for this calculation:

public static int binlog( int bits ) // returns 0 for bits=0
{
    int log = 0;
    if( ( bits & 0xffff0000 ) != 0 ) { bits >>>= 16; log = 16; }
    if( bits >= 256 ) { bits >>>= 8; log += 8; }
    if( bits >= 16  ) { bits >>>= 4; log += 4; }
    if( bits >= 4   ) { bits >>>= 2; log += 2; }
    return log + ( bits >>> 1 );
}

It is slightly faster than Integer.numberOfLeadingZeros() (20-30%) and almost 10 times faster (jdk 1.6 x64) than a Math.log() based implementation like this one:

private static final double log2div = Math.log( 2 );
public static int log2fp( int bits )
{
    if( bits == 0 )
        return 0; // or throw exception
    return (int) ( Math.log( bits & 0xffffffffL ) / log2div );
}

Both functions return the same results for all possible input values.