【剑指Offer】数值的整数次方

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0

解法1

最直接的思路，计算base的exponent次方，则将base连乘exponent次即可，时间复杂度为O(exponent)
但是要注意处理特殊情况：

• 如果底数base等于0则直接返回0
• 非0数的0次方等于1
• 当指数为负数时的结果，相当于用1除以指数为正数时的结果

还有一个坑需要注意，下面的代码中使用了long y = exponent;，需要将exponent转换为long类型
是因为exponent可以等于-2147483648（int类型的最小值），如果直接进行-exponent操作，由于int类型的最大值是2147483647，则会导致越界，出现错误的结果

实现代码

public double Power(double thebase, int exponent)
{
    if(thebase == 0) return 0;
    long y = exponent;  // 避免越界
    if(y < 0){
        thebase = 1 / thebase;
        y = -y;
    } 
    double ret = 1;
    for(double i = 0; i < y; i ++){
        ret *= thebase;
    }
    return ret;
}

解法2

可以根据二分的思路，利用递归每次求指数的一半的次方结果，然后再将递归的结果相乘得到完整的指数次方
由于求指数的一半，即整数除以2的结果会自动向下取整，所以需要特殊处理指数为奇数时的情况，当指数为奇数时，需要在递归结果相乘的基础上再乘以一次底数
代码中使用的位运算e >> 1相当于e / 2来计算指数的一半
代码中通过位运算(e & 1) == 1 来判断指数是奇数还是偶数（奇数的二进制表示最低位一定是1，偶数的二进制表示最低位一定是0），相当于(e % 2) == 1
使用位运算会有更快的执行效率

实现代码

public double Power2(double thebase, int exponent)
{
    if(thebase == 0) return 0;
    if(exponent == 0) return 1;
    long e = exponent;  // 避免越界
    if(exponent < 0){
        e = - e;
        thebase = 1 / thebase;
    }
    if(e == 1) return thebase;
    double ret = Power2(thebase, (int)(e >> 1));
    return (e & 1) == 1 ? thebase * ret * ret : ret * ret;
}

解法3

求解整数m的n次方，一般是mⁿ = m * m * m .....，连乘n次，算法复杂度是O(n)，这样的算法效率太低，我们可以通过减少相乘的次数来提高算法效率，即快速幂
对于n我们可以用二进制表示，以14为例，14 = 1110

 

m14=m1110=m23∗1+22∗1+21∗1+20∗1=m23∗1∗m22∗1∗m21∗1∗m20∗0$$m^{14}=m^{1110}=m^{2^3\ast 1+2^2\ast 1+2^1\ast 1+2^0\ast 1}=m^{2^3\ast 1}\ast m^{2^2\ast 1}\ast m^{2^1\ast 1}\ast m^{2^0\ast 0}$$

 

 

=m8∗m4∗m2∗m0=m8∗m4∗m2∗1$$=m^8\ast m^4\ast m^2\ast m^0=m^8\ast m^4\ast m^2\ast 1$$

 

可以发现这样的规律，指数n的二进制从低位到高位依次对应底数m的1次方，2次方，4次方，8次方...，当该二进制位是1的时候，则乘以底数对应的次方数，如果该二进制位是0，则不能乘以底数对应的次方数，即乘以1。
例如，m⁸对应的二进制位是1，所以最终结果中有m⁸
m¹对应的二进制位是0，所以最终结果中只有m⁰，即1
使用快速幂后，原本需要的14次连乘，现在只需要4次连乘。
那么怎样得到一个整数的二进制位呢，又怎样判断该二进制位是0还是1呢
可以使用与运算和右移运算，例如对于14 = 1110

• 和1按位与得到0，即第一个二进制位是0
• 1110右移一位，得到0111，和1按位与得到1，即第二个二进制位是1
• 0111右移一位，得到0011，和1按位与得到1，即第三个二进制位是1
• 0011右移一位，得到0001，和1按位与得到1，即第四个二进制位是1
• 0001右移一位，得到0000，等于0则，算法结束

实现代码

public double Power3(double thebase, int exponent)
{
    if(thebase == 0) return 0;
    long y = exponent;  // 避免越界
    if(y < 0){
        thebase = 1 / thebase;
        y = -y;
    } 
    double ret = 1;
    while(y > 0){
        if((y & 1) == 1){
            ret *= thebase;
        }
        thebase *= thebase;
        y >>= 1;
    }
    return ret;
}

更多算法题目的完整描述，AC代码，以及解题思路可以查看GitHub仓库Algorithm