首页 > 代码库 > leetcode pow(x,n)实现

leetcode pow(x,n)实现

题目描述:

     自己实现pow(double x, int n)方法

 

实现思路:

    考虑位运算。考虑n的二进制表示形式,以n=51(110011)为例,x^51 = x^1*x^2*x^16*x^32,因此每次将n无符号右移一位,并将x取当前值的平方,如果n右移后末位

为1,则将res*x。考虑特殊情况,当n为Integer.MIN_VALUE时,此时-n=Integer.MAX_VALUE+1,我第一次就是没有考虑到这个边界情况出错的。。。

    该方法通过扫描n的二进制表示形式里不同位置上的1,来计算x的幂次

   

LeetCode的AC代码(Java版)如下:

       

public class Solution {
    public double myPow(double x, int n) {
       if(n < 0){
           if(n == Integer.MIN_VALUE){  //考虑边界值
               return 1/(myPow(x,Integer.MAX_VALUE)*x);  
           }else{
               return 1/myPow(x,-n);
           }
       }
       
       if(n == 0){
           return 1.0;
       }
       
       double res = 1.0;
       for(; n>0; x = x*x, n = n>>>1){  //无符号右移的同时,x取自身的平方
           
           if( (n & 1) > 0){
               res *= x;
           }
       }
       
       return res;
    }
}

 

leetcode pow(x,n)实现