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

이것은이 계산에 사용하는 함수입니다.

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 비트 클라이언트 VM :

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

JDK 1.7 x64 서버 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 );

답변

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

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

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

LongMath.log2()

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