数值的整数次方

太过爱你忘了你带给我的痛 2023-07-07 08:24 121阅读 0赞

##### 题目描述 #####

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0

##### 解题思路 #####

本题描述的是求数值的次方，该题描述也正是JDK中Math.pow(a,b)方法  
这里给出俩个解法:  
第一个解法是：使用循环不停的迭代乘积，然后返回累计的结果.注意对于指数为负数的情况考虑

public double Power(double base, int exponent) { 
            double result = 1d;
            int symbol = exponent > 0 ? exponent : -exponent;
            for (int i = 0; i < symbol; i++) { 
                result *= base;
            }
            return exponent > 0 ? result : 1 / result;
        }

第二种解法使用的是快速幂的方式，该方式通过位运算，因此它的效率也是最好的，其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高  
首先我们来认识一下快速幂：快速幂指的是快速算底数的n次幂，这里给出百科中计算实例  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ_size_16_color_FFFFFF_t_70]  
对于上面的原理实例我们逐个拆解分析：  
1：对于本题我们肯定要把指数换算成二进制数，比如11，换算成1011  
2：经过换算之后，然后在对比原理实例中最后一行公式，我们可以看到如果二进制位为0，那么将不需要累积结果，因此在代码中我们需要逐位判断当前位是否为0，如果为0，那么该结果不需要累积，否则累积结果.对应着代码的 if((symbol & 1) == 1) res \*= curr;功能实现  
3： 公式是计算整体结果的，但是应该把这个补全，就是在中间缺少a22次方，只不过2的11次方对应位置为0，但是如果先拼接上在看的话，每个位置上的值都是上一个计算结果的翻倍，(a2)2,(a2)3这样看的话清楚 curr \*= curr;代码的含义了.它就是根据截图中的公式进行计算的，不管二进制是否为0，每次都会翻倍，而是否取当前值作为累积乘积看的就是上面的 if ((symbol & 1) == 1)判断了.  
4：现在整体看下while部分的解释，首先不能为0，如果为0那么直接返回res=1，  
然后每次拿指数二进制数和1做与运算，即判断最右一位是否为1，如果是累积乘积当前结果，并且将乘积值翻倍，如果最右一位是否为0，那么不进行累积，且也需要将乘积翻倍，然后都执行右移操作，即判断左边一位，直至二进制位全部取完，即二进制数为1，退出运算，返回结果.

public double Power(double base, int exponent) { 
            double res = 1, curr = base;
            int symbol = exponent > 0 ? exponent : -exponent;
            while (symbol != 0) { 
                if ((symbol & 1) == 1)
                    res *= curr;
                // 不管当前位是否为0都需要进行翻倍
                curr *= curr;
                // 右移一位
                symbol >>= 1;
            }
            return exponent >= 0 ? res : (1 / res);
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200221235331675.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ==,size_16,color_FFFFFF,t_70