题目:实现函数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;
}
分享到:
相关推荐
程序员面试题精选100题
程序员面试题精选100题
程序员面试题精选程序员面试题精选程序员面试题程序员面试题精选精选
程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试...
程序员面试题精选100题-何海涛 程序员 面试题 算法 数据结构
程序员面试题精选100题(2008)程序员面试题精选100题(2008)
一份可以让大家在求职时更能自信的题解,经典的100题,让大家可以感受到算法的经典,当然,自己要更加努力,要懂得举一反三才能更上一层楼!
程序员面试题精选100题
程序员面试题精选100题
程序员面试题精选100题,以前下过的不全,自己在网上搜了搜,整理了一下。
程序员面试题精选100例.doc