如何用Java计算整数中的log base 2？ [英] How do you calculate log base 2 in Java for integers?

问题描述

我使用以下函数计算整数的log base 2：

I use the following function to calculate log base 2 for integers:

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

它是否具有最佳性能？

有人知道为此目的准备好J2SE API函数吗？

Does someone know ready J2SE API function for that purpose?

UPD1 令我惊讶的是，出现浮点算术比整数算术更快。

UPD2 由于评论，我会进行更详细的调查。

UPD3 我的整数运算函数比Math.log（n）/Math.log（2）快10倍。

推荐答案

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

If you are thinking about using floating-point to help with integer arithmetics, you have to be careful.

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

I usually try to avoid FP calculations whenever possible.

浮点运算并不准确。你永远不可能知道（int）（Math.log（65536）/Math.log（2））评估为什么。例如， Math.ceil（Math.log（1<<<< 29）/ Math.log（2））在我的电脑上是30，在数学上它应该是29我没有找到x的值，其中（int）（Math.log（x）/Math.log（2））失败（仅因为只有32 危险值），但这并不意味着它在任何PC上的工作方式都相同。

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.

这里通常的技巧是在舍入时使用epsilon。像（int）（Math.log（x）/Math.log（2）+ 1e-10）应该永远不会失败。选择这个epsilon并不是一项微不足道的任务。

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.

使用更一般的任务进行更多演示 - 尝试实现 int log（int x，int base）：

More demonstration, using a more general task - trying to implement 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);
        }
    }
}

如果我们使用最直接 - 向前执行对数，

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

打印：

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。
你能在测试之前告诉过这个吗？
我绝对不能。

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.

这篇关于如何用Java计算整数中的log base 2？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！