今天遇到问题需要计算以2为底的对数值（需要整数），找了半天API中log函数有自然对数，以10为底的对数，没有以2为底的，~~o(>_<)o ~~，API中提供的方法返回的都是double类型的，可能你会觉得，不就这么简单嘛，其实这里面学问也挺大的呢，且听我慢慢叙来~~
- 方法一：
我们都知道
log[a]x
log[b]x = ---------
log[a]b
因此呢，我们可以用一下的方法计算 log2（或者用自然对数）
log[10]x
log[2]x = ----------
log[10]2
即：
(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);
- }
- }
- }
结果是：
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
...也就是说，当底为第一个数，指数为第二个数时，用(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，如需转载请自行联系原作者
