How do you calculate log base 2 in Java for integers?_问答_开发者

I use the 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 have optimal perfor开发者_C百科mance?

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).

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 = 1.000000000001 / Math.log( 2 );
public static int log2fp0( 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.

Update: The Java 1.7 server JIT is able to replace a few static math functions with alternative implementations based on CPU intrinsics. One of those functions is Integer.numberOfLeadingZeros(). So with a 1.7 or newer server VM, a implementation like the one in the question is actually slightly faster than the binlog above. Unfortunatly the client JIT doesn't seem to have this optimization.

public static int log2nlz( int bits )
{
    if( bits == 0 )
        return 0; // or throw exception
    return 31 - Integer.numberOfLeadingZeros( bits );
}

This implementation also returns the same results for all 2^32 possible input values as the the other two implementations I posted above.

Here are the actual runtimes on my PC (Sandy Bridge i7):

JDK 1.7 32 Bits client VM:

binlog:         11.5s
log2nlz:        16.5s
log2fp:        118.1s
log(x)/log(2): 165.0s

JDK 1.7 x64 server VM:

binlog:          5.8s
log2nlz:         5.1s
log2fp:         89.5s
log(x)/log(2): 108.1s

This is the test code:

int sum = 0, x = 0;
long time = System.nanoTime();
do sum += log2nlz( x ); while( ++x != 0 );
time = System.nanoTime() - time;
System.out.println( "time=" + time / 1000000L / 1000.0 + "s -> " + sum );

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.

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

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....

Link

Why not:

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

There is the function in guava libraries:

LongMath.log2()

So I suggest to use it.

Some cases just worked when I used Math.log10:

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

To add to x4u answer, which gives you the floor of the binary log of a number, this function return the ceil of the binary log of a number :

public static int ceilbinlog(int number) // returns 0 for bits=0
{
    int log = 0;
    int bits = number;
    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;
    }
    if (1 << log < number)
        log++;
    return log + (bits >>> 1);
}

let's add:

int[] fastLogs;

private void populateFastLogs(int length) {
    fastLogs = new int[length + 1];
    int counter = 0;
    int log = 0;
    int num = 1;
    fastLogs[0] = 0;
    for (int i = 1; i < fastLogs.length; i++) {
        counter++;
        fastLogs[i] = log;
        if (counter == num) {
            log++;
            num *= 2;
            counter = 0;
        }
    }
}

Source: https://github.com/pochuan/cs166/blob/master/ps1/rmq/SparseTableRMQ.java

To calculate log base 2 of n, following expression can be used: