剑指offer——数值的整数次方

题目描述 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 方法一：快速幂方法，快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。 然后分别计算拆分后的项，后面项可以由前面项的逐次求平方得到。最后将例如算a¹，需要一次记为A，把A平方就是a²记为B，把B平方就是a⁴记为C，再平方就是a⁸记为D，这样把AXBXD就是结果了。

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

方法二：一般的幂运算

class Solution { public: double Power(double base, int exponent) { if(exponent == 0) return 1; int flag = 0; if(exponent < 0){ flag = 1; exponent = -exponent; } double result = base; for(int i = 1; i < exponent; i++){ result *= base; } if(flag == 1) return 1 / result; else return result; } };