【面试题011】数值的整数次方

【面试题011】数值的整数次方

不能用等号判断不精确数字是不是相等，在软件开发过程中，永远不变的就是需求会一直改变。

实现函数 double Power(double base, int exponent),求base的exponent次方，不得使用库函数，

同时步需要考虑大数问题。这个指数可能是0，正数，或者负数。

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

Power.cpp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

bool g_InvalidInput = false;

bool equal(double num1, double num2)
{
    if((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001))
    {
        return true;
    }
    else
    {
        return false;
    }
}

/*
double PowerWithUnsignedExponent(double base, unsigned int exponent)
{
    double result = 1.0;
    /
    for(int i = 1; i <= exponent; ++i)
        result *= base;

    return result;
}
*/

double PowerWithUnsignedExponent(double base, unsigned int exponent)
{
    if(exponent == 0)
    {
        return 1;
    }
    if(exponent == 1)
    {
        return base;
    }
    /*除2运算用右移运算来实现效率更高*/
    double result = PowerWithUnsignedExponent(base, exponent >> 1);
    result *= result;
    /*判断是奇数还是偶数*/
    if((exponent & 0x1) == 1)
    {
        result *= base;
    }
    return result;
}

double Power(double base, int exponent)
{
    g_InvalidInput = false;

    if(equal(base, 0.0) && exponent < 0)
    {
        g_InvalidInput = true;
        return 0.0;
    }

    unsigned int absExponent = (unsigned int)(exponent);
    if(exponent < 0)
    {
        absExponent = (unsigned int)(-exponent);
    }
    double result = PowerWithUnsignedExponent(base, absExponent);
    if(exponent < 0)
    {
        result = 1.0 / result;
    }

    return result;
}

int main()
{
    // 底数、指数都为正数
    double base = 2;
    int exponent = 3;
    double expectedResult = 8;
    double result = Power(base, exponent);
    if(abs(result - expectedResult) < 0.00000001
            && g_InvalidInput == false)
        printf("Test passed. ");
    else
        printf("Test failed. ");

    return 0;
}

运算结果：

Test passed.

Makefile

1
2
3
4
5
6
7
8
9
10
11
12

.PHONY:clean
CPP=g++
CFLAGS=-Wall -g
BIN=test
OBJS=Power.o
LIBS=
$(BIN):$(OBJS)
    $(CPP) $(CFLAGS) $^ -o $@ $(LIBS)
%.o:%.cpp
    $(CPP) $(CFLAGS) -c $< -o $@
clean:
    rm -f *.o $(BIN)