如何在 Java 中计算整数的日志基数为2？

我使用以下函数计算整数的日志基数2:

public static int log2(int n){
if(n <= 0) throw new IllegalArgumentException();
return 31 - Integer.numberOfLeadingZeros(n);
}

它有最佳的性能吗？

是否有人知道为此目的准备好 J2SEAPI 函数？

UPD1 < em > 令我惊讶的是，浮点运算似乎比整数运算更快。

UPD2 < em > 根据评论，我将进行更详细的调查。

我的整数算术函数比 Math.log (n)/Math.log (2)快10倍。

256395 次浏览
小开

为什么不:

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

试试 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方法... ..。

林克

小开
最佳答案

如果您正在考虑使用浮点数来帮助整数算术，那么您必须小心。

我通常尽可能避免 FP 计算。

浮点运算并不精确。你永远不能确定 (int)(Math.log(65536)/Math.log(2))的评估结果。例如，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)永远不会失败。选择这个“ Esilon”并不是一件微不足道的事情。

更多演示，使用更一般的任务——试图实现 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之间。 你能在测试前告诉我吗？ 我绝对不能。

小开

这是我用来计算的函数:

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.732位客户端 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

这是测试代码:

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 );
小开

再加上:

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

小开

番石榴图书馆有这样的功能:

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);
}
小开

要计算 n 的对数基2，可以使用以下表达式:

double res = log10(n)/log10(2);
小开

当我使用 Math.log10的时候，有些情况是可行的:

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

提交答案