剑指offer—数值的整数次方 解答

剑指offer—数值的整数次方

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和exponent不同时为0

思路

这题首先考虑到循环遍历数值的大小次,计算出结果,但是还有比这更优的方法:快速幂

快速幂

快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N),比O(N)更快

例如

img

11的二进制是1011

img

因此,我们将a¹¹转化为算

img

  • 快速幂可以帮助我们使用二进制快速计算幂函数和指数函数

在正数情况下,我们每次对指数右移,只要它对应二进制位为1,我们就需要乘上a的2的n次方(n为二进制所在位数),我们可以利用右移每次对一个duoble变量累乘,只要当前位为1就乘上该变量,否则就一直累乘该变量,直到为1的位数,或者指数为0时结束循环。

我们需要用到的:

  • 判断二进制当前位(最右边一位)是否为1
(e&1)==1
  • 每次循环右移
e>>=1  或者   e=e>>1

当然我们需要考虑到指数为负数的情况,我们知道负数的指数函数为正数的倒数,所以如果为负数我们把它取负保存到一个变量(变为正数进行计算),最后输出结果时判断该指数为负数的话则输出倒数,反之输出结果。

代码

public class Solution {
    public double Power(double base, int exp) {
        int e = exp;//存储正数的指数
        double res = 1;//存储结果
        double count = base;//原来存储累乘变量
        if(exp==0){//指数为0返回1
            return 1;
        }else if(exp<1){//小于1取负保存到e中
            e = -exp;
        }
        while(e!=0){//循环计算
            if((e&1)==1){
                res *= count;//利用快速幂,如果当前位为1则相乘
            }
            count *= base;//累乘操作
            e>>=1;//右移
        }
        return exp<0?1/res:res;
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/quick-mi-numm.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!