我使用以下函数来计算整数的以2为底的对数：
public static int log2(int n){
if(n <= 0) throw new IllegalArgumentException();
return 31 - Integer.numberOfLeadingZeros(n);
}
这个代码是否具有最佳性能？
是否有人知道现成的J2SE API函数来实现这个目的？
更新1 让我惊讶的是，浮点数算术似乎比整数算术更快。
更新2 由于评论的缘故，我将进行更详细的调查。
更新3 我的整数算法函数比Math.log(n)/Math.log(2)快10倍。
这是我用于进行此计算的函数：
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 );
}
两个函数对于所有可能的输入值都返回相同的结果。
更新:
Java 1.7服务器JIT能够使用基于CPU内部函数的另一种实现替换一些静态数学函数。其中之一是Integer.numberOfLeadingZeros()。因此，对于1.7或更新版本的服务器VM，像问题中的实现实际上比上面的binlog稍微快一点。不幸的是，客户端JIT似乎没有这种优化。
public static int log2nlz( int bits )
{
if( bits == 0 )
return 0; // or throw exception
return 31 - Integer.numberOfLeadingZeros( bits );
}
这个实现方式对于所有2^32种可能的输入值也会返回与我上面发布的另外两个实现相同的结果。
以下是在我的电脑（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 server VM：
binlog: 5.8s
log2nlz: 5.1s
log2fp: 89.5s
log(x)/log(2): 108.1s
以下是测试代码:
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 );
BSR指令执行32 - numberOfLeadingZeros，但对于0未定义，因此（JIT）编译器必须检查非零值，如果无法证明它不需要。BMI指令集扩展（Haswell及更高版本）引入了LZCNT，它完全按照numberOfLeadingZeros进行实现，可以在单个指令中完成。它们都是3个周期延迟，每个周期1次吞吐量。因此，我绝对建议使用numberOfLeadingZeros，因为这使得好的JVM易于实现。（关于lzcnt的一个奇怪之处是它对要覆盖的寄存器的旧值存在伪依赖。） - Peter Cordes如果你考虑使用浮点数来辅助整数算术，你必须小心谨慎。
我通常尽可能避免使用浮点计算。
浮点运算并不是精确的。你永远无法确定 (int)(Math.log(65536)/Math.log(2)) 的值是多少。例如，在我的PC上，Math.ceil(Math.log(1<<29) / Math.log(2)) 的值是30，但根据数学计算它应该是29。我没有发现任何使得 (int)(Math.log(x)/Math.log(2)) 失败的x的值（因为只有32个“危险”值），但这并不意味着它在任何PC上都能够以同样的方式工作。
通常的技巧是在四舍五入时使用“epsilon”。例如：(int)(Math.log(x)/Math.log(2)+1e-10) 应该不会失败。选择“epsilon”的值并不是一项微不足道的任务。
更多的演示可以通过尝试实现 int log(int x, int base) 来展示：
测试代码：
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。你在测试之前能提前告诉我吗？当然不可能。
strictfp，那么它不代表它会在任何计算机上以相同的方式工作。 - Kenstrictfp似乎因为实际上是严格的而受到了很多批评。 :-) - Kenreturn ((long)Math.log(x) / (long)Math.log(base));来解决所有错误怎么样？ - Not a bug尝试使用Math.log(x) / Math.log(2)
你可以使用身份认证（identity）
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));
}
当我使用Math.log10时，有些情况是有效的：
public static double log2(int n)
{
return (Math.log10(n) / Math.log10(2));
}
guava库中有这个函数:
LongMath.log2()
所以我建议使用它。
作为对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
要计算以2为底数的n的对数，可以使用以下表达式：
double res = log10(n)/log10(2);
Math.floor(Math.log(n)/Math.log(2))，因此它并没有真正计算以2为底的对数！ - Dori