你如何计算整数在Java中的日志基数2？
我使用下面的函数来计算整数的log base 2：
public static int log2(int n){ if(n <= 0) throw new IllegalArgumentException(); return 31 - Integer.numberOfLeadingZeros(n); } 它有最佳的性能吗？
有人知道为此准备好J2SE API函数吗？
UPD1 令人惊讶的是，浮点运算似乎比整数运算更快。
UPD2 由于意见，我会进行更详细的调查。
UPD3 我的整数算术函数比Math.log（n）/Math.log（2）快10倍。
如果你正在考虑使用浮点数来帮助整数运算，你必须小心。
我通常尽可能地避免FP计算。
浮点操作并不准确。 你永远无法知道什么将(int)(Math.log(65536)/Math.log(2))评估。 例如， Math.ceil(Math.log(1<<29) / Math.log(2))在我的电脑上是30，在math上它应该是29.我没有find一个值，其中(int)(Math.log(x)/Math.log(2))失败（仅仅因为只有32个“危险的”值），但这并不意味着它将在任何PC上以相同的方式工作。
这里常用的技巧是在四舍五入时使用“epsilon”。 像(int)(Math.log(x)/Math.log(2)+1e-10)应该永远不会失败。 这个“epsilon”的select不是一件小事。
更多的演示，使用更一般的任务 – 试图实现int log(int x, int base) ：
testing代码：
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); } } }
如果我们使用最直接的对数实现，
static int log(int x, int base) { return (int) (Math.log(x) / Math.log(base)); }
这打印：
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 ...
要完全摆脱错误，我不得不添加1e-11和1e-14之间的epsilon。 你可以在testing之前告诉这个吗？ 我绝对不能。
这是我用于这个计算的function：
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 ); }
它比Integer.numberOfLeadingZeros（）（20-30％）快一点，比Math.log（）这样的实现要快10倍（jdk 1.6 x64）：
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 ); }
这两个函数都会为所有可能的input值返回相同的结果。
更新： Java 1.7服务器JIT能够用基于CPU内部函数的替代实现replace一些静态math函数。 其中一个函数是Integer.numberOfLeadingZeros（）。 所以对于一个1.7或更新的服务器虚拟机，类似问题中的实现实际上比上面的binlog稍快。 不幸的是客户JIT似乎没有这个优化。
public static int log2nlz( int bits ) { if( bits == 0 ) return 0; // or throw exception return 31 - Integer.numberOfLeadingZeros( bits ); }
对于所有2 ^ 32个可能的input值，这个实现也会返回与上面发布的其他两个实现相同的结果。
以下是我的电脑上的实际运行时间（Sandy Bridge i7）：
JDK 1.7 32位客户端VM：
binlog: 11.5s log2nlz: 16.5s log2fp: 118.1s log(x)/log(2): 165.0s
JDK 1.7 x64服务器VM：
binlog: 5.8s log2nlz: 5.1s log2fp: 89.5s log(x)/log(2): 108.1s
这是testing代码：
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 );
尝试Math.log(x) / Math.log(2)
你可以使用这个身份
log[a]x log[b]x = --------- log[a]b
所以这将适用于log2。
log[10]x log[2]x = ---------- log[10]2
只需将其插入到Java Math log10方法中。
为什么不：
public static double log2(int n) { return (Math.log(n) / Math.log(2)); }
有番石榴图书馆的function：
LongMath.log2()
所以我build议使用它。
要添加到x4u答案，这给你一个数字的二进制日志的底线，这个函数返回一个数字的二进制日志的细胞：
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); }
让我们添加：
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; } } }
来源： https ： //github.com/pochuan/cs166/blob/master/ps1/rmq/SparseTableRMQ.java
