剑指offer——实现函数double Power(double base,int exponent),求base的exponent次方，不得使用库函数，同时不需要考虑大数问题。
自以为题目简单的解法：用for或者while循环
double Poweruint(double a, unsigned int ex) { double ret = 1.0; while (ex--){ ret *= a; } return ret; }可是这个程序只包括了指数是正数的情况，指数是负数和零的时候怎么办？我们都知道，
任何非零数的零次方为1，0的0次方没有意义，因此输出0或1都是可以接受的。指数为负数时，先对指数求绝对值，然后算出次方的结果再求倒数。底数为0，指数为负数时，要对0求倒数会导致程序运行出错，因此要做特殊处理，可以采用三种方法：返回值，全局代码和异常。 这个题的解法中我们采用了全局变量来标识是否出错，如果出错则返回0值。为了区分返回的0值是输出结果还是出错处理，再定义一个变量flag，初始化为0，如果是出错导致结果输出为0则令flag=1来标识。计算机表示小数都有误差，我们不能直接用等号（==）判断，要使两个数的差值在一个精度内。在考虑了指数的各种情况后，我们可以考虑优化次方函数，如输入的指数为32，在for循环中需要做31次乘法。但我们可以换一种思路：
目标次数是32，如果知道了它的16次方，那么在16次方基础上平方就可以了。而16次方是8次方的平方，以此类推，求32次方只需要做5次乘法：先求平方，再平方基础上求4次方，4次方基础上求8次方，8次方基础上求16次方，16次方，基础上求32次方。
可以用下面的公式求解：
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> int equal(double a, double b)//比较两个浮点数是否相等 { if ((a - b) > -0.000001 && (a - b) < 0.000001){ return 1; } else{ return 0; } } double Poweruint1(double a, unsigned int ex)//低效率 { double ret = 1.0; //for (unsigned int i = 0; i <= ex; i++){ // ret *= a; //} while (ex--){ ret *= a; } return ret; } double Poweruint2(double a, unsigned int n)//位运算效率比乘除法和求余运算高 { if (0 == n){ return 1.0; } if (1 == n){ return a; } double ret = Poweruint2(a, n >> 1); //double ret = Poweruint2(a, n/2); ret *= ret; if (1 == (n & 1)){ ret *= a; } //if (1 == (n % 2)){ // ret *= a; //} return ret; } double Power(double base, int exponent) { int flag = 0; double result = 1.0; unsigned int ex = (unsigned int)exponent; if (equal(base, 0.0) && exponent < 0){//底数为0并且指数小于0 flag = 1; return 0.0; } if (exponent < 0){//指数为负数时先转化为正数 ex = (unsigned int)(-exponent); } /*result = Poweruint1(base, ex);*/ result = Poweruint2(base, ex); if (exponent < 0){ result = 1.0 / result; } return result; } int main() { double result = Power(0,0); printf("%f\n", result); system("pause"); return 0; }
