《剑指offer》面试题16:数值的整数次方（C++实现）

题目描述解决思路思路一：补充布尔型标志位代表无效输入思路二：用位运算符来提高我们的计算效率小结参考文献

题目描述

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

求数值的整数次方多简单哦，小老板，直接一手for循环，exponent个base相乘不就搞定了啊？ 说干就干。

//case通过率40% class Solution { public: double Power(double base, int exponent) { double result = 1.0; for(int i = 1;i<=exponent;i++) result *=base; return result; } };

得到的输出结果是：

您的代码已保存 答案错误:您提交的程序没有通过所有的测试用例 case通过率为40.00%

用例: 2,-3 对应输出应该为: 0.12500 你的输出为: 1.00000

原来是没有考虑指数为负数的情况啊。 再把代码进行修改。

//运行时间：4ms //运行内存：456K class Solution { public: double Power(double base, int exponent) { double result = 1.0; for(int i = 1;i<=abs(exponent);i++) result *=base; if(exponent<0) result = 1/result;//如果指数是负数 求结果的倒过来数 return result; } };

显示我通过了这道题。不过这样并不能让面试官满意。

解决思路

不过这道题的解决重点在于两个地方。 1.对指数整数范围的充分考虑，一般正数很好解决，负数和0怎么处理呢？ 特别是可以提问，0的负整数次方还有0⁰ 没有意义，应当如何处理。 2.对于求正整数次方，除了for循环，还有别的更高效的计算方法。

思路一：补充布尔型标志位代表无效输入

//运行时间：4ms //运行内存：456K class Solution { public: bool g_InvalidInput = false;//设置输入变量标志位，True代表出现0的非正整数次方计算 double Power(double base, int exponent) { g_InvalidInput = false; if((base==0.0)&&exponent<=0)//计算0的非正整数次方,标志为为true,返回0.0 { g_InvalidInput = true; return 0.0; } double result = PowerCompute(base,exponent);//获取base的真整数次方 if(exponent<0) result = 1/result;//如果指数是负数 求结果的导数 return result; } //计算base的正整数次方 double PowerCompute(double base,int exponent) { double result = 1.0; for(int i = 1;i<=abs(exponent);i++) result *=base; return result; } };

思路二：用位运算符来提高我们的计算效率

如果我们求一个数字的32次方。除了用32个这个数字相乘。 我们还可以，求2数字的平方。在平方的基础上，求4次方。4次方的基础上，求8次方。8次方的基础上，求16次方。16次方的基础上，求32次方。 那么我们一定会用到下面的公式。

$$a^n=\{\begin{array}{rlr}{a}^{n/2}\ast a^{n/2}& & \text{n为偶数}\\ a^{(n-1)/2}\ast a^{(n-1)/2}\ast a& & \text{n为奇数}\end{array}$$ 那么我们需要对于计算base的正整数次方计算进行优化。(PowerCompute) 实现上述的方式使用递归。

//运行时间：3ms //占用内存：480K class Solution { public: bool g_InvalidInput = false;//设置输入变量标志位，True代表出现0的非正整数次方计算 double Power(double base, int exponent) { g_InvalidInput = false; if((base==0.0)&&exponent<=0)//计算0的非正整数次方,标志为为true,返回0.0 { g_InvalidInput = true; return 0.0; } double result = PowerCompute(base,exponent);//获取base的真整数次方 if(exponent<0) result = 1/result;//如果指数是负数 求结果的导数 return result; } //计算base的正整数次方 double PowerCompute(double base,int exponent) { if(exponent==0) return 1; if(exponent==1) return base; double result =PowerCompute(base,exponent/2); //可替换代码1：double result =PowerCompute(base,exponent>>1);用右移运算符代替除以2//可能会显示超出内存 result *=result; if(exponent%2) //可替换代码2：if(exponent &0x1 ==1) 用位与运算符代替求余运算符号 result *= base; return result; } };

小结

解决思路里虽然代码可以提交，但是对没有意义的输入没有考虑，代码不够鲁棒性。 思路一对非法输入做了补充，另外采用循环计算次方。 思路二相对于思路一而言，在计算次方上提升了计算效率，为所有思路中的最佳。

整体而言，思路二最佳。

参考文献

《剑指offer》

牛课网刷题链接link.