How do you calculate log base 2 in Java for integers?

今天遇到問題需要計算以2為底的對數值（需要整數），找了半天API中log函數有自然對數，以10為底的對數，沒有以2為底的，~~o(>_<)o ~~，API中提供的方法傳回的都是double類型的，可能你會覺得，不就這麼簡單嘛，其實這裡面學問也挺大的呢，且聽我慢慢叙來~~

方法一：

我們都知道

是以呢，我們可以用一下的方法計算 log2（或者用自然對數）

即：(int) (Math.log(x) / Math.log(base));

如果隻是計算以2為底的對數，上面的方法沒有什麼問題，如果以3或者其他數為底的時候，上面的方法就暗藏玄機了，強制裝換成Int類型不一定可靠，以前寫程式遇到過強制轉後精度丢失的問題，結果查了半天才把這個bug找出來。上面的計算方法其實也是有問題的，無論什麼時候，用浮點數運算去代替整數計算時都要小心。浮點數的運算是不确切的，你也不能很确切的知道(int)(Math.log(65536)/Math.log(2))的值是多少，例如：Math.ceil(Math.log(1<<29) / Math.log(2))計算的結果是30，而它的正确值應該是29，我不能很找到哪些值用(int)(Math.log(x)/Math.log(2))的時候會不正确， (just because there are only 32 "dangerous" values)，

注：下面的與本主題無關，隻是就這個問題說開去，證明一個問題，當底數不是2時，用上述方法是有問題的~~

下面就用周遊的方法把這些值列印出來：

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

static int log(int x,int base) 

 { 

     return(int)(Math.log(x)/Math.log(base)); 

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

         } 

     } 

結果是：

 也就是說，當底為第一個數，指數為第二個數時，用(int)(Math.log(x)/Math.log(base))是有問題的，又有人提出用近似值（"epsilon"）來減小誤差：(int)(Math.log(x)/Math.log(2)+1e-10)，這種方法也是可以的；

方法二：

public static int log2(int n){ 

    if(n <=0)throw new IllegalArgumentException(); 

    return31-Integer.numberOfLeadingZeros(n); 

} 

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

上面的方法會不會有性能問題呢，可能你會不以為然，有人給出了更簡便的方法，我們知道移位操作比周遊和運算要快得多；

方法三：

public static int log2X(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 倍：

private static final double log2div =Math.log(2); 

 public static int log2fp(int bits ) 

     if( bits ==0) 

         return0;// or throw exception 

     return(int)(Math.log( bits &0xffffffffL)/ log2div ); 

我說的沒錯吧，可能你覺得太鑽牛角尖了，也是，不過别人能用更優雅，效率更高的方法實作相 同的功能，也

值得借鑒一下，并且以後在用浮點數代替整數計算時也要曉得，會不會有“陷阱”~~

本文轉自 breezy_yuan 51CTO部落格，原文連結：http://blog.51cto.com/lbrant/469310，如需轉載請自行聯系原作者