code4offer-7 数值的整数次方

数值的整数次方

问题描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和exponent不同时为0

分析

计算$base^{exponent}$，正好最近在学密码学，想到了快速幂算法，可以减少乘法次数

$base^{1}$、
$base^{2}$、
$base^{4}$、
$base^{8}$……
一直逼近到$base^{exponent}$，剩下的部分直接乘上去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
double Power(double base, int exponent) {
    if (exponent == 0) return 1;
    if (base == 0) return 0;

    int curE = 1;
    double result = base;
    int tmpE = abs(exponent);

    while (2 * curE < tmpE) {
        result *= result;
        curE *= 2;
    }

    while (tmpE - curE >0) {
        result *= base;
        --tmpE;
    }

    return exponent < 0 ? 1/result : result;
}

牛客上大佬更简洁的代码，也是快速幂，这代码太🐂了

1
2
3
4
5
6
7
8
9
10
11
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;
}