정수에서 Java의 로그베이스 2를 어떻게 계산합니까?

정수에서 Java의 로그베이스 2를 어떻게 계산합니까?

---

다음 함수를 사용하여 정수에 대한 로그베이스 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 배 빠릅니다.

---

정수 산술을 돕기 위해 부동 소수점을 사용하려는 경우주의해야합니다.

나는 보통 가능할 때마다 FP 계산을 피하려고 노력합니다.

부동 소수점 연산이 정확하지 않습니다. 당신은 무엇을 (int)(Math.log(65536)/Math.log(2))평가 할지 확실히 알 수 없습니다 . 예를 들어, Math.ceil(Math.log(1<<29) / Math.log(2))수학적으로 정확히 29이어야하는 내 PC의 30입니다. (int)(Math.log(x)/Math.log(2))32 개의 "위험한"값만 있기 때문에 실패한 x에 대한 값을 찾지 못했지만 제대로 작동하지는 않습니다. 모든 PC에서 동일한 방식으로.

여기에서 일반적인 트릭은 반올림 할 때 "엡실론"을 사용하는 것입니다. 등이 (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
...

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.

---

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

---

Try Math.log(x) / Math.log(2)

---

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....

http://mathforum.org/library/drmath/view/55565.html

---

Why not:

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

---

There is the function in guava libraries:

LongMath.log2()

So I suggest to use it.

---

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

---

Some cases just worked when I used Math.log10:

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

---

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

---

To calculate log base 2 of n, following expression can be used:

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

참고URL : https://stackoverflow.com/questions/3305059/how-do-you-calculate-log-base-2-in-java-for-integers