邦泽网站建设,建设网站的法律声明,wordpress ping大全,excel做注册网站目录
剑指 Offer 16. 数值的整数次方
题解#xff1a;
知识点#xff1a;
代码#xff1a;
结果#xff1a; 实现 pow(x, n) #xff0c;即计算 x 的 n 次幂函数#xff08;即#xff0c;xn#xff09;。不得使用库函数#xff0c;同时不需要考虑大数问题。 示例…
目录
剑指 Offer 16. 数值的整数次方
题解
知识点
代码
结果 实现 pow(x, n) 即计算 x 的 n 次幂函数即xn。不得使用库函数同时不需要考虑大数问题。 示例 1 输入x 2.00000, n 10 输出1024.00000 示例 2 输入x 2.10000, n 3 输出9.26100 示例 3 输入x 2.00000, n -2 输出0.25000 解释2-2 1/22 1/4 0.25 提示 -100.0 x 100.0 -231 n 231-1 n 是一个整数 要么 x 不为零要么 n 0 。 -104 xn 104 题解 快速幂的思想 将指数11 可以转成二进制数1011则原来的式子可以转化成 此时只运算了3次乘积时间复杂度降至O(logn) 首先判断底数x是否为0如果是0则直接返回0将指数n转化为长整型变量b避免在处理负数时出现溢出问题初始化结果res为1.0如果指数b小于0说明底数x取倒数同时将指数b取相反数进入循环当指数b大于0时继续执行循环体内的操作使用位运算判断指数b的最后一位是否为1如果是1则将结果res乘以底数x更新底数x为x的平方将指数b右移一位相当于将其除以2循环结束后返回结果res 利用了位运算来判断指数的最后一位是否为1从而确定是否需要乘以底数x。同时通过不断平方底数x和右移指数b实现了快速求幂的效果 知识点 位运算 位运算是计算机中对二进制数据进行操作的一种运算方式。它直接在二进制位上进行操作可以高效地进行一些常见的运算如与、或、异或和移位等。 以下是一些常用的位运算符 与运算按位进行与运算两个位都为1时结果为1否则为0。或运算|按位进行或运算两个位中只要有一个为1时结果为1否则为0。异或运算^按位进行异或运算两个位相同为0不同为1。非运算~按位进行非运算将每个位取反。左移运算将二进制数向左移动指定的位数相当于乘以2的幂。右移运算将二进制数向右移动指定的位数相当于除以2的幂。 位运算在计算机领域的应用非常广泛包括但不限于以下方面 位掩码使用位运算来创建、修改和查询特定位的值用于标记或设置某些状态。压缩算法利用位运算来压缩数据减少存储空间。加密和解密位运算可用于实现加密和解密算法中的位级操作。优化算法某些算法可以使用位运算进行优化例如快速求幂、快速排序等。 代码 class Solution {public double myPow(double x, int n) {if(x0) return x;long bn;//将指数n转化为长整型变量b避免在处理负数时出现溢出问题。//负数幂if(b0){x1/x;b-b;}double res1.0;//快速幂思想二进制角度while(b0){if((b1)1){res*x;}x*x;b1;}return res;}
} 结果
