作者:翟天保Steven 题目描述:实现函数 double Power(double base, int exponent),求base的exponent次方。 注意: 1.保证base和exponent不同时为0。 2.不得使用库函数,同时不需要考虑大数问题 3.有特殊判题,不用考虑小数点后面0的位数。 数据范围: ∣base∣≤100 ,∣exponent∣≤100 ,保证最终结果一定满足∣val∣≤104 示例:输入: 2.00000,-2 返回值: 0.25000 说明: 2的-2次方等于1/4=0.25 解题思路:本题考察位运算。三种解题思路。 1)暴力法 循环累乘即可。复杂度O(n)。 2)位运算-快速幂 对次方数进行位运算即可实现快速幂计算。复杂度O(logn)。 如13次方是1101,分别是1、4、8,也就是说base的13次方等于base的1次方*base的4次方*base的8次方。以此为例,下面文字讲述过程便于理解。 a)首次进入循环后,当前次方数是1101,&1可得true,result乘base,然后将base*=base,base就变成了2次方,位运算右移得到0110。 b)第二次循环,&1得到false,也就是说当前低位是0,result不需要乘base,继续累乘base,base就变成了4次方,位运算右移得到0011。 c)第三次循环,&1得到true,result乘base,此时的base是4次方,result就变成base的5次方,然后累乘base,base变成8次方,位运算右移得到0001。 d)第四次循环,&1得到true,result乘base,base是8次方,result就变成了base的13次方,然后累乘base,base变成16次方,位运算右移得到0000。 e)退出循环,返回result。 测试代码:1)暴力法
2)位运算-快速幂
|
|