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

发布于 2024-09-10 17:26:35 字数 448 浏览 9 评论 0原文

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

原文

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

Does it have optimal performance?

Does someone know ready J2SE API function for that purpose?

UPD1 Surprisingly for me, float point arithmetics appears to be faster than integer arithmetics.

UPD2 Due to comments I will conduct more detailed investigation.

UPD3 My integer arithmetic function is 10 times faster than Math.log(n)/Math.log(2).

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

够运 2024-09-17 17:26:35

这是我用于此计算的函数：

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 可能的输入值返回与我上面发布的其他两个实现相同的结果。

以下是我的 PC (Sandy Bridge i7) 上的实际运行时间：

JDK 1.7 32 位客户端虚拟机：

binlog:         11.5s
log2nlz:        16.5s
log2fp:        118.1s
log(x)/log(2): 165.0s

JDK 1.7 x64 服务器虚拟机：

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

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:

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 binlog above. Unfortunatly the client JIT doesn't seem to have this optimization.

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.

Here are the actual runtimes on my PC (Sandy Bridge i7):

JDK 1.7 32 Bits client 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

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

回复收藏 0 原文

半步萧音过轻尘 2024-09-17 17:26:35

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

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

浮点运算并不精确。您永远无法确定 (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 上都以相同的方式工作。

这里通常的技巧是在舍入时使用“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。
你能在测试前告诉我这一点吗？
我绝对不能。

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.

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.

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.

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

回复收藏 0 原文

是伱的 2024-09-17 17:26:35

尝试 Math.log(x) / Math.log(2)

回复收藏 0 原文

堇年纸鸢 2024-09-17 17:26:35

您可以使用该身份

            log[a]x
 log[b]x = ---------
            log[a]b

，因此这适用于 log2。

            log[10]x
 log[2]x = ----------
            log[10]2

只需将其插入 java Math log10 方法...

链接

you can use the identity

            log[a]x
 log[b]x = ---------
            log[a]b

so this would be applicable for log2.

            log[10]x
 log[2]x = ----------
            log[10]2

just plug this into the java Math log10 method....

Link

回复收藏 0 原文

情愿 2024-09-17 17:26:35

为什么不：

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

Why not:

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

回复收藏 0 原文

攒一口袋星星 2024-09-17 17:26:35

当我使用 Math.log10 时，某些情况才有效：

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

Some cases just worked when I used Math.log10:

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

回复收藏 0 原文

瀞厅☆埖开 2024-09-17 17:26:35

guava库中有这个函数：

LongMath.log2()

所以我建议使用它。

There is the function in guava libraries:

LongMath.log2()

So I suggest to use it.

回复收藏 0 原文

绮烟 2024-09-17 17:26:35

要添加到 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);
}

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 :

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

回复收藏 0 原文

时光磨忆 2024-09-17 17:26:35

让我们添加：

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

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

回复收藏 0 原文