软件工程师面试题精选100题(44)-数值的整数次方
程序员面试题精选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)
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 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; }