Skip to content

Latest commit

 

History

History
155 lines (120 loc) · 4.11 KB

12.数值的整数次方.md

File metadata and controls

155 lines (120 loc) · 4.11 KB
Raw

12.数值的整数次方

题目描述

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

解题思路

方法一，笨办法，累乘
  • 第一种思路是常规思路，也是笨办法，就是累乘，最容易想到（方法一），但是这种方法很慢
方法二，快速幂算法：

  • 参考博客

  • 假如我们要求的是$3^{999}$，那么累乘的话效率也太低了，于是我们可以借助乘方的运算性质：

$$ \begin{align} a^{m+n} &= a^{m}*a^{n} \\ \\ 3^{999} &= 3^{(512+256+128+64+32+4+2+1)} \\ &= 3^{(2^{9}+2^{8}+2^{7}+2^{6}+2^{5}+2^{2}+2^{1}+2^{0})} \\ &= 3^{(2^{9})} * 3^{(2^{8})} * 3^{(2^{7})} * 3^{(2^{6})} * 3^{(2^{5})} * 3^{(2^{2})} * 3^{(2^{1})} * 3^{(2^{0})} \end{align} $$

  • 按上面的方法，我们只需要用某种快速方法把一系列$3^{(2^{k})}$算出来（一个整数的2次方相当于左移1位），就只需要算7次乘法。将幂也就是$999$转换成二进制（111 110 0111）以后，所有为1的位置对应的二进制权值就是所有我们需要计算的$3$的次方，而这些次方都只用一次，因此可以从低次往高次算，不保留中间结果。

  • 因此，算法流程如下：

    1. 将result初始化为1，底数为base，幂为e，如果幂是负数的话将其取反，最后结果取倒数；
    2. 如果e & 1 == 1的话，说明幂的末位为1，需要计算这个次方，就让result *= base；
    3. 每次循环都让base *= base，即平方，也就是$base^{(2^{k})}$里面的$k$不断增加，如果base确定为整数的话也可以用左移；
    4. e >>= 1，即幂右移1位，也可以用除以2实现，下一次循环就判断下一个$base^{(2^{k})}$需不需要乘到结果里面（步骤2）。
    5. e为0的时候循环结束

  • 伪代码如下（C++代码更好理解）：

    POWER_INTEGER(x, n)    # x^n
    pow ← 1
    while (n > 0)
        do if (n mod 2 = 1)   # mod表示取模，即取余数
            then pow ← pow * x
        x ← x * x
        n ← n / 2
    return pow

  • C++代码如下：

    NumberType optimized_pow_n(NumberType x, unsigned int n)
{
    NumberType pw = 1;

    while (n > 0) {
        if (n & 1)        // n & 1 等价于 (n % 2) == 1
            pw *= x;
        x *= x;
        n >>= 1;        // n >>= 1 等价于 n /= 2
    }

    return pw;
}

代码

  • 方法一，笨办法，累乘
class Solution {
public:
    double Power(double base, int exponent) {
        if(exponent == 0){
            return 1.;
        }
        if(base == 0){
            return 0.;
        }
        double result = base;
        bool flip_flag = false;
        if(exponent < 0) {
            flip_flag = true;
            exponent = -exponent;
        }
        
        while(--exponent) result *= base;
        if(flip_flag) result = 1/result;
        
        return result;
    }
};
  • 方法二，快速幂算法
class Solution {
public:
    double Power(double base, int exponent) {
        if(exponent == 0){
            return 1.;
        }
        if(base == 0){
            return 0.;
        }
        
        bool flip_flag = false;
        if(exponent < 0) {
            flip_flag = true;
            exponent = -exponent;
        }
        
        double result = 1;
        while(exponent){
            if(exponent&1){
                result *= base;
            }
            base *= base;
            exponent >>= 1;
        }
        return flip_flag ? 1/result : result;
    }
};

网上其他人写的简单版代码

class Solution {
public:
    double Power(double base, int exponent) {
        long long p = abs( (long long) exponent);
        double r = 1.0;
        while (p) {
            if (p & 1)
                r *= base;
            base *= base;
            p >>= 1;
        }
        return ( exponent > 0 ) ? r : 1/r;
    }
};