程序员面试题精选100题(44)－数值的整数次方

题目：实现函数double Power(double base, int exponent)，求base的exponent次方。不需要考虑溢出。

不明白就看这个网址：
http://zhedahht.blog.163.com/blog/static/254111742009101563242535/

如何将指数分解为一个或若干个2的整数次方。我们把指数表示为二进制数再来分析。比如6的二进制表示为110，在它的第2位和第3位为1，因此6=2^(2-1)+2^(3-1) 。也就是说只要它的第n位为1，我们就加上2的n-1次方。
5^6=5^2*((5^2)^2)

double PowerWithUnsignedExponent(double base, unsigned int exponent)
{
    std::bitset<32> bits(exponent);
    if(bits.none())
        return 1.0;
    int numberOf1 = bits.count();
    double multiplication[32];
    for(int i = 0; i < 32; ++i)
    {
        multiplication[i] = 1.0;
    }
    // if the i-th bit in exponent is 1,
    // the i-th number in array multiplication is base ^ (2 ^ n)
    int count = 0;
    double power = 1.0;
    for(int i = 0; i < 32 && count < numberOf1; ++i)
    {
        if(i == 0)
            power = base;
        else
            power = power * power;
        if(bits.at(i))
        {
            multiplication[i] = power;
            ++count;
        }
    }
    power = 1.0;
    for(int i = 0; i < 32; ++i)
    {
        if(bits.at(i))
            power *= multiplication[i];

    }
    return power;
}

a^n = a^(n/2) * a^(n/2) 当n为偶数时候
       =a^((n-1)/2)*a^((n-1)/2)*a 当a为基数

所以设a^n = f(a,n) 然后就按照语义来做就是了

double PowerWithUnsignedExponent(double base, unsigned 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 *= base;
    return result;
}