How do you calculate log base 2 in Java for integers

Question

I use the following function to calculate log base 2 for integers   public static int log2 int n       if n  lt   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

User · Answer

Try Math log x    Math log 2

User · Answer

Some cases just worked when I used Math log10   public static double log2 int n        return  Math log10 n    Math log10 2

User · Answer

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 lt  lt 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  lt  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  amp  amp   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  lt  500  base              int maxPow    int   Math log Integer MAX VALUE    Math log base            for  int pow   0  pow  lt   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

User · Answer

Why not   public static double log2 int n        return  Math log n    Math log 2

User · Answer

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  amp  0xffff0000      0     bits  gt  gt  gt   16  log   16        if  bits  gt   256     bits  gt  gt  gt   8  log    8        if  bits  gt   16      bits  gt  gt  gt   4  log    4        if  bits  gt   4       bits  gt  gt  gt   2  log    2        return log     bits  gt  gt  gt  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  amp  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 - gt      sum

User · Answer

There is the function in guava libraries   LongMath log2     So I suggest to use it

User · Answer

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

User · Answer

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  amp  0xffff0000     0            bits  gt  gt  gt   16          log   16            if  bits  gt   256            bits  gt  gt  gt   8          log    8            if  bits  gt   16            bits  gt  gt  gt   4          log    4            if  bits  gt   4            bits  gt  gt  gt   2          log    2            if  1  lt  lt  log  lt  number          log        return log    bits  gt  gt  gt  1

User · Answer

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

User · Answer

To calculate log base 2 of n  following expression can be used   double res   log10 n  log10 2

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

Examples related to java

Examples related to performance

Examples related to discrete-mathematics

Examples related to logarithm