你如何在 Java 中计算整数的对数基数 2？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3305059/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How do you calculate log base 2 in Java for integers?
提问by Nulldevice
I use the following function to calculate log base 2 for integers:
我使用以下函数来计算整数的对数基数 2：
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?
有人知道为此目的准备好 J2SE API 函数吗？
UPD1Surprisingly for me, float point arithmetics appears to be faster than integer arithmetics.
UPD1 令我惊讶的是，浮点运算似乎比整数运算更快。
UPD2Due to comments I will conduct more detailed investigation.
UPD2由于评论，我将进行更详细的调查。
UPD3My integer arithmetic function is 10 times faster than Math.log(n)/Math.log(2).
UPD3我的整数算术函数比 Math.log(n)/Math.log(2) 快 10 倍。
采纳答案by Rotsor
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.
我通常尽量避免 FP 计算。
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.
浮点运算并不精确。您永远无法确定将(int)(Math.log(65536)/Math.log(2))评估什么。例如，Math.ceil(Math.log(1<<29) / Math.log(2))在我的 PC 上是 30，在数学上它应该正好是 29。我没有找到(int)(Math.log(x)/Math.log(2))失败的x 值（只是因为只有 32 个“危险”值），但这并不意味着它会起作用在任何 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.
通常的技巧是在舍入时使用“epsilon”。喜欢(int)(Math.log(x)/Math.log(2)+1e-10)永远不会失败。选择这个“epsilon”并非易事。
More demonstration, using a more general task - trying to implement int log(int x, int base):
更多演示，使用更一般的任务 - 尝试实现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.
为了完全消除错误，我不得不添加介于 1e-11 和 1e-14 之间的 epsilon。你能在测试前告诉这个吗？我绝对不能。
回答by TofuBeer
Why not:
为什么不：
public static double log2(int n)
{
return (Math.log(n) / Math.log(2));
}
回答by Chris B.
Try Math.log(x) / Math.log(2)
尝试 Math.log(x) / Math.log(2)
回答by hvgotcodes
you can use the identity
你可以使用身份
log[a]x
log[b]x = ---------
log[a]b
so this would be applicable for log2.
所以这将适用于 log2。
log[10]x
log[2]x = ----------
log[10]2
just plug this into the java Math log10 method....
只需将其插入 java Math log10 方法中....
回答by x4u
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:
它比 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 );
}
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 binlogabove. Unfortunatly the client JIT doesn't seem to have this optimization.
更新：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 );
}
This implementation also returns the same results for all 2^32 possible input values as the the other two implementations I posted above.
此实现还为所有 2^32 个可能的输入值返回与我上面发布的其他两个实现相同的结果。
Here are the actual runtimes on my PC (Sandy Bridge i7):
以下是我的 PC (Sandy Bridge i7) 上的实际运行时间：
JDK 1.7 32 Bits client VM:
JDK 1.7 32 位客户端虚拟机：
binlog: 11.5s
log2nlz: 16.5s
log2fp: 118.1s
log(x)/log(2): 165.0s
JDK 1.7 x64 server VM:
JDK 1.7 x64 服务器虚拟机：
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 );
回答by Guido Celada
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
来源：https: //github.com/pochuan/cs166/blob/master/ps1/rmq/SparseTableRMQ.java
回答by Demetr
There is the function in guava libraries:
番石榴库中有函数：
LongMath.log2()
So I suggest to use it.
所以我建议使用它。
回答by Ofek Ron
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 :
要添加到 x4u 答案中，它为您提供了一个数字的二进制日志的下限，此函数返回一个数字的二进制日志的 ceil ：
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);
}
回答by Akanksha
To calculate log base 2 of n, following expression can be used:
要计算 n 的对数基数 2，可以使用以下表达式：
double res = log10(n)/log10(2);
回答by Marina
Some cases just worked when I used Math.log10:
当我使用 Math.log10 时，某些情况才有效：
public static double log2(int n)
{
return (Math.log10(n) / Math.log10(2));
}
