P90、面试题11：数值的整数次方

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

需要注意的地方：

1）输入的指数小于1即是零和负数的情况；

2）指数是负数时需要取倒数，当底数是0时的情况；

3）0的0次方无论输出0或1都可以接受；

4）为了区分是出错的时候返回的0，还是底数为0的时候正常运行返回0，我们需要定义了一个全局变量g_InvalidInput；

5）判断两个小数是否相等，只能判断它们之差的绝对值是不是在一个很小的范围内。如果两个数相差很小，就可以认为它们相等；

6）有个快捷的公式a的n次方={a的n/2次方 * a的n/2次方当n为偶数时； a的(n-1)/2次方 * a的(n-1)/2次方 * a n为奇数}；

7）用右移运算符替代了除以2，用位与运算符代替了求余运算符(%)来判断一个数是奇数还是偶数。

测试用例：

把底数和指数分别设为正数、负数和零。

代码实现：

package com.yyq;

/**
 * Created by Administrator on 2015/9/11.
 */
public class Power {
    public static boolean g_InvalidInput = false;
    public static double Power(double base, int exponent){
        g_InvalidInput = false;
        if(equal(base,0.0) && exponent < 0){
            g_InvalidInput = true;
            return 0.0;
        }
        int absExponent = exponent;
        if (exponent < 0){
            absExponent = -1 * exponent;
        }
        double result = PowerWithUnsignedExponent(base, absExponent);
        if (exponent < 0){
            result = 1.0 / result;
        }
        return result;
    }
    public static double PowerWithUnsignedExponent(double base, int exponent){
        if (exponent == 0)
            return 1;
        if (exponent == 1)
            return base;
        double result = PowerWithUnsignedExponent(base, exponent >> 1);
        result *= result;
        if((exponent & 0x1)==1){
            result = result * base;
        }
        return result;
    }
    public static boolean equal(double num1, double num2){
        if ((num1 - num2 > -0.0000001) && (num1 -num2 < 0.0000001))
            return true;
        else
            return false;
    }


    // ====================测试代码====================
    public static void Test(double base, int exponent, double expectedResult, boolean expectedFlag)
    {
        double result = Power(base, exponent);
        if((result - expectedResult) < 0.00000001 && (result - expectedResult) > -0.00000001
                && g_InvalidInput == expectedFlag)
            System.out.println("Test passed.");
        else
            System.out.println("Test failed.");
        System.out.println();
    }

    public static void main(String[] args){

        // 底数、指数都为正数
        System.out.println("Test1 begins.");
        Test(2, 3, 8, false);

        // 底数为负数、指数为正数
        System.out.println("Test2 begins.");
        Test(-2, 3, -8, false);

        // 指数为负数
        System.out.println("Test3 begins.");
        Test(2, -3, 0.125, false);

        // 指数为0
        System.out.println("Test4 begins.");
        Test(2, 0, 1, false);

        // 底数、指数都为0
        System.out.println("Test5 begins.");
        Test(0, 0, 1, false);

        // 底数为0、指数为正数
        System.out.println("Test6 begins.");
        Test(0, 4, 0, false);

        // 底数为0、指数为负数
        System.out.println("Test7 begins.");
        Test(0, -4, 0, true);

    }
}

输出结果：

Test1 begins.

Test passed.

Test2 begins.

Test passed.

Test3 begins.

Test passed.

Test4 begins.

Test passed.

Test5 begins.

Test passed.

Test6 begins.

Test passed.

Test7 begins.

Test passed.