158

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

3
  • 1
    How did you test the performance of this? On my System (Core i7, jdk 1.6 x64) the integer version is almost 10 times faster than the floating point version. Be sure to actually do something with the result of the function so that the JIT can't remove the calculation entirely!
    – x4u
    Jul 22, 2010 at 3:57
  • You are correct. I did not use results of calculation and compiler have optimized something. Now I have the same result as you - integer function is 10 times faster (Core 2 Duo, jdk 1.6 c64)
    – Nulldevice
    Jul 22, 2010 at 5:03
  • 10
    This effectively gives you Math.floor(Math.log(n)/Math.log(2)), so its not really calculating log base 2!
    – Dori
    Apr 20, 2016 at 16:48

10 Answers 10

101

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 );
2
  • 9
    x86's BSR instruction does 32 - numberOfLeadingZeros, but undefined for 0, so a (JIT) compiler has to check for non-zero if it can't prove it doesn't have to. The BMI instruction set extensions (Haswell and newer) introduced LZCNT, which fully implements numberOfLeadingZeros exactly, in a single instruction. They're both 3 cycle latency, 1 per cycle throughput. So I'd absolutely recommend using numberOfLeadingZeros, because that makes it easy for a good JVM. (The one weird thing about lzcnt is that it has a false dependency on the old value of the register it overwrites.) Sep 15, 2015 at 16:14
  • I am most interested in your comment about Java 1.7 server JIT CPU intrinsics replacements. Do you have a reference URL? (JIT Source code link is OK also.)
    – kevinarpe
    Mar 7, 2016 at 11:57
86

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.

6
  • 4
    "it does not mean that it will work the same way on any PC" -- It would if you used strictfp, no?
    – Ken
    Jul 22, 2010 at 5:14
  • @Ken: Maybe... But you can only be sure after exhaustively enumerating all the possible input values. (we are lucky there are so few of them here)
    – Rotsor
    Jul 22, 2010 at 11:01
  • 2
    Technically, yes, but that's true of any function. At some point you have to trust that if you use the available documentation, and test some well-chosen but vanishingly small fraction of "all possible input values", that your program will work well enough. strictfp seems to have actually gotten a lot of crap for being, in fact, strict. :-)
    – Ken
    Jul 25, 2010 at 18:31
  • how about return ((long)Math.log(x) / (long)Math.log(base)); to solve all the errors?
    – Not a bug
    Jun 10, 2017 at 18:43
  • @Notabug not sure about that but one of the side effects will be that your code will work incorrectly for any values which does not fit in a long, this might not be useful if your values range exceeds long range ( float has much higher range than long in java)
    – Naruto26
    Aug 19, 2020 at 4:31
49

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

1
  • 14
    While mathematically this is correct, please be aware that there is a risk of mis-calculation due to imprecise floating-point arithmetic, as explained in Rotsor's answer.
    – leeyuiwah
    Oct 22, 2017 at 21:51
36

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

1
  • 5
    While mathematically this is correct, please be aware that there is a risk of mis-calculation due to imprecise floating-point arithmetic, as explained in Rotsor's answer.
    – leeyuiwah
    Oct 22, 2017 at 21:51
23

Why not:

public static double log2(int n)
{
    return (Math.log(n) / Math.log(2));
}
1
  • 9
    While mathematically this is correct, please be aware that there is a risk of mis-calculation due to imprecise floating-point arithmetic, as explained in Rotsor's answer.
    – leeyuiwah
    Oct 22, 2017 at 21:52
10

Some cases just worked when I used Math.log10:

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

There is the function in guava libraries:

LongMath.log2()

So I suggest to use it.

4
  • How can I add this package to my application? Oct 14, 2015 at 5:52
  • Download the jar from here and add it to your project's build path. Feb 18, 2016 at 6:03
  • 4
    Should I add a library into my application just to use one function? Oct 4, 2016 at 13:27
  • 11
    Why exactly would you suggest using it? A quick read of the Guava source shows that it does the same thing as the OP's method (a few very clearly understood lines of code), at the cost of adding an otherwise useless dependency. Just because Google provides something doesn't make it any better than understanding the problem and solution yourself.
    – Dave
    Jan 1, 2017 at 4:18
3

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);
}
1
  • Where is the "number" variable?
    – barteks2x
    Sep 3, 2016 at 16:10
0

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

1
  • That would be creating a lookup table. The OP asked for a faster way to "calculate" a logarithm.
    – Dave
    Jan 1, 2017 at 4:52
-4

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

double res = log10(n)/log10(2);
1
  • 2
    This answer has already been posted several times, and has already been noticed to be potentially inaccurate due to round-off error. Note the OP asked for the integral value; it's not at all clear what rounding precision needs to be used to get from here to an integer. Jul 26, 2018 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.