题目

        实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

解题思路

        对exponent进行分类讨论，同时也对base是否为0进行讨论。

        exponent分为大于0，小于0，等于0。

        当exponent大于0的时候，

                base大于0，利用快速乘方的方法来计算。

                base小于0，利用快速乘方来实现。

                base等于0，结果为0（也是用快速乘方实现）。

        当exponent小于0的时候，

                base大于0，结果需要求倒数。

                base小于0，结果需要求倒数。

                base等于0，对0求倒数会导致出现一些问题，程序运行会出错。

               这里的处理方式为，设定一个全局变量来标识是否出错。如果出错，则返回值为0，并且将全局变量改为true。

        当exponent等于0的时候，

                base大于0，结果为1。

                base等于0，结果为1。（0的0次方我们设定结果为1）

                base小于0，结果为1。

        再编写一个专门做乘方的函数，利用快速做乘方的方法，递归实现我们求乘方的过程，原理是：

        当我们要输出一个数字的32次方时，用普通方法需要做31次循环。

        我们也可以使用另一种方法，当我们知道一个数的32次方的时候，如果我们知道它的16次方，只需要在这个基础上平方即可。16又是8的平方。一次类推我们需要做5次方法即可。2---4---8---16---32，一共5次方。

代码

参考了这个博主的https://www.cnblogs.com/yongh/p/9664297.html

package myNewSwordOffer; public class powerWithUnsignedExponent { boolean IsInvalid = false;//用全局变量标记是否出错 public double power(double base, int exponent) { IsInvalid = false; double result; // double类型 if (exponent > 0) { result = powerCore(base, exponent); } else if (exponent < 0) { if (base == 0) { IsInvalid = true; //0的负数次方不存在 return 0; } result = 1 / powerCore(base, -exponent); } else { return 1; //这里0的0次方输出为1 } return result; } private double powerCore(double base, int exponent) { if (exponent == 1) return base; if (exponent == 0) return 1; double result = powerCore(base, exponent >> 1); result *= result; if ((exponent & 0x1) == 1) result *= base; return result; } // ========测试代码======== void test(String testName, double base, int exponent, double expected, boolean expectedFlag) { if (testName != null) System.out.print(testName + ":"); if (power(base, exponent) == expected && IsInvalid == expectedFlag) { System.out.println("passed."); } else { System.out.println("failed."); } } void test1() { test("test1", 0, 6, 0, false); } void test2() { test("test2", 0, -6, 0, true); } void test3() { test("test3", 0, 0, 1, false); } void test4() { test("test4", 2, 6, 64, false); } void test5() { test("test5", 2, -3, 0.125, false); } void test6() { test("test6", 5, 0, 1, false); } void test7() { test("test7", -2, 6, 64, false); } public static void main(String[] args) { powerWithUnsignedExponent demo = new powerWithUnsignedExponent(); demo.test1(); demo.test2(); demo.test3(); demo.test4(); demo.test5(); demo.test6(); demo.test7(); } }

小结

1、使用位运算代替除法：使用右移运算>>代替处以2。

2、使用位运算代替求余运算：判断奇偶数，if((exponent & 0x1) == 1) 为真就是奇数，否则就是偶数。

3、快速做乘方：

4、不要忽略底数为0而指数为负的情况

当底数是0，且指数是负数的时候，如果步进行特殊处理，就会出现对0求倒数的情况，从而导致程序出错。