如何計算整數的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快10倍（2）。

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)應該永遠不會失敗。這個「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。 您可以在測試之前告訴這個嗎？ 我絕對不能。

Answer 2

爲什麼不：

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

Answer 3

嘗試Math.log(x)/Math.log(2)

Answer 4

您可以使用身份

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

所以這將是適用於的log 2。

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

只需將其插入到這個java的數學方法LOG10 ....

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

Answer 5

這是我使用該計算的功能：

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％）稍快幾乎10倍（JDK 1.6 x64）的比Math.log（）的實現這樣一個：

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或更新的服務器虛擬機，類似於問題中的實現的實現實際上比上述binlog稍快。不幸的是客戶JIT似乎沒有這種優化。

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

此實現還返回與上述其他兩個實現相同的結果，即所有2^32個可能的輸入值。

這裏是我的電腦上的實際運行時間（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服務器虛擬機：

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

Answer 6

讓我們添加：

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

Answer 7

有番石榴庫中的函數：

LongMath.log2() 

所以我建議使用它。

Answer 8

爲了增加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); 
}