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배 빠르다.

이 계산에 사용하는 함수는 다음과 같습니다.

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 x 64) 빠릅니다.

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.number Of Leading Zeros()입니다.따라서 1.7 이상의 서버 VM을 사용하는 경우 문제의 구현과 같은 구현이 실제로는 서버 VM보다 약간 더 빠릅니다.binlog위입니다. 불행히도 클라이언트 JIT는 이러한 최적화를 가지고 있지 않은 것 같습니다.

public static int log2nlz( int bits )
{
    if( bits == 0 )
        return 0; // or throw exception
    return 31 - Integer.numberOfLeadingZeros( bits );
}

이 실장에서는, 상기의 2개의 실장과 같은 결과가 2^32 의 모든 입력치에 대해서 반환됩니다.

PC의 실제 실행 시간은 다음과 같습니다(Sandy Bridge i7).

JDK 1.7 32비트 클라이언트 VM:

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

JDK 1.7 x 64 서버 VM:

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

정수 산술에 도움이 되는 부동 소수점 사용을 고려하고 있는 경우 주의해야 합니다.

저는 가능한 한 FP 계산을 피하려고 합니다.

부동 소수점 연산은 정확하지 않습니다.무슨 일이 일어날지 아무도 모른다.(int)(Math.log(65536)/Math.log(2))평가하다예를들면,Math.ceil(Math.log(1<<29) / Math.log(2))계산상으로는 정확히 29가 되어야 하는 PC에서는 30이 됩니다.x 값을 찾을 수 없습니다.(int)(Math.log(x)/Math.log(2))('위험한' 값이 32개밖에 없다는 이유만으로) 장애가 발생하지만 어떤 PC에서도 동일하게 동작하는 것은 아닙니다.

여기서 일반적인 방법은 반올림할 때 "엡실론"을 사용하는 것입니다.맘에 들다(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 사이의 엡실론을 추가해야 했습니다.테스트 전에 이 사실을 알려주실 수 있습니까?난 절대 그럴 수 없어.

★★를 해 보세요.Math.log(x) / Math.log(2)

아이덴티티를 사용할 수 있습니다.

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

따라서 이는 log2에 적용됩니다.

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

이것을 java Math log10 메서드에 꽂기만 하면 됩니다.

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

안 되는 이유:

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

guava 라이브러리에는 다음과 같은 기능이 있습니다.

LongMath.log2()

그래서 나는 그것을 사용할 것을 권한다.

Math.log10:

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

숫자의 바이너리 로그 바닥을 제공하는 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);
}

추가:

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

로그 베이스 2(n)를 계산하려면 다음 식을 사용할 수 있습니다.

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

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