数值的整数次方

  • 题目描述:

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

  • 解题思路:

该题主要考察代码的完整性,需要结合指数表达式特征以及所给变量的正负性全面考虑。
有可能出现的情况如下:

  1. 底数base!=0,指数exponent>0 => 累乘 (这是我们最容易想到的一条)
  2. 底数base=0,指数exponent<0 ==""> 编译出错,分母不能为0
  3. 底数base!=0,指数exponent<0 ==""> 累乘结果取倒数(base^exponent = 1/base^(-exponent))
  • 源代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
double Power(double base, int exponent) {
double result = 1;
int flag = 0; //定义一个标记变量,用来区分不同的情况
if (exponent<0) {
if (base==0) {
return false;
}else {
exponent = -exponent;
flag = 1; //表明此时为指数小于0的情况
}
}
for (int i=0;i<exponent;i++) {
result*=base;
}
if (flag == 1) {
result = 1/result;
}
return result;
}
};

快速幂

在这里扩展一下关于快速幂的知识点。

快速幂就是快速算底数的n次幂,时间复杂度为$O(log_2N)$。
该题即是求幂运算的过程,在前面的解法中,我们利用了累乘进行求解,时间复杂度为$O(N)$,换用快速幂方式可以提高时间效率。

  • 原理:

以求$a^b$来进行介绍,我们需要将指数b转换为二进制数,然后利用位运算来实现。

b&1 : 取指数b的二进制最低位,判断和1是否相同,相同返回1,不同返回0(用于判断所在位为1还是0)
b>>1 : 把b的二进制右移一位(每次判断完之后将最后一位去掉,便于判断下一位置)

  • 源代码:
1
2
3
4
5
6
7
8
9
int pow(int a,int b) {
int r = 1,base = a; //变量r为最终结果,base为底数
while(b) {
if (b&1) r*=base; //当前二进制位为1,需要参与运算
base*=base;
b>>=1;
}
return r;
}
  • 实例分析:

求解$3^11$,我们首先需要将指数11转换为二进制数

$$
11_{10} => 1011_2
11 = 2^01 + 2^11 + 2^20 + 2^31
3^11 = 3^{2^0} 3^{2^1} 3^{2^3} = 3 3^2 3^8

指数b最低位 当前结果 底数 指数b右移后
1 1*3 base=3^2 101
1 133^2 base=3^4 10
0 133^2 base=3^8 1
1 133^2*3^8 base=3^16 NULL

$$

当指数b为NULL时,程序结束,返回最终结果$r=133^2*3^8$

-------------The End-------------