如何计算Java中以整数为底的对数2？

Question

我使用以下函数为整数计算对数基数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倍。

Answer 1

如果您正在考虑使用浮点数来帮助进行整数运算，则必须小心。

我通常会尽量避免FP计算。

浮点运算不精确。您永远无法确定会(int)(Math.log(65536)/Math.log(2))得出什么结果。例如，Math.ceil(Math.log(1<<29) / Math.log(2))在我的PC上为30，数学上应该恰好为29。我没有找到x
(int)(Math.log(x)/Math.log(2))失败的值（只是因为只有32个“危险”值），但这并不意味着它将起作用在任何PC上都是相同的方式。

此处的常用技巧是在四舍五入时使用“
epsilon”。喜欢(int)(Math.log(x)/Math.log(2)+1e-10)永远都不会失败。选择这种“ε”不是一件容易的事。

使用更一般的任务进行更多的演示-尝试实现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。在测试之前，您能告诉这个吗？我绝对不能。