欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

剑指offer之数值的整数次方(C++/Java双重实现)

程序员文章站 2022-06-17 10:25:44
1.题目描述实现函数double Power(double base, int exponent),求base的exponent次方。不得使用库函数,同时不需要考虑大数问题。示例 1:输入: 2.00000, 10输出: 1024.00000示例 2:输入: 2.10000, 3输出: 9.26100示例 3:输入: 2.00000, -2输出: 0.25000解释: 2-2 = 1/22 = 1/4 = 0.25说明:-100.0 < x < 100.0n 是 3...

1.题目描述

实现函数double Power(double base, int exponent),求base的exponent次方。不得使用库函数,同时不需要考虑大数问题。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:
-100.0 < x < 100.0
n 是 32 位有符号整数,其数值范围是 [−231, 231 − 1] 。

剑指offer之数值的整数次方(C++/Java双重实现)

2.问题分析

思路描述:因为不用考虑大数问题,所以只需要循环地去计算就可以了,但是单纯的循环去算,比如:

for(int i = 1; i < n; i ++)
	x *= x;

是会超时的。
所以这里使用快速幂的方法,那么什么是快速幂呢我们看一个例子:
我们要求29

我们知道9的二进制是1001,也就是1 * 20+0 * 21+0 * 22+1 * 23
那么29 =21 * 20 * 20 * 21*20 * 22*21 * 23
我们发现,每次指数乘的值都是前一个值的2倍,当 n 对应位为0时跳过

3.代码实现:

3.1C++代码

class Solution {
public:
    double myPow(double x, int n) {
        if(x == 1 || n == 0) return 1;
        double ans = 1;
        long num = n;
        if(n < 0){
            num = -num;
            x = 1/x;
        }
        while(num){
            if(num & 1) 
            ans *= x;
            x *= x;
            num >>= 1;
        }
        return ans;
    }
};

1.(num&1)是判断指数的二进制此位是否为1
2.x=x*x:每一次判断一次二进制数就往后移动一位然后x就变为原来的平方

3.2Java代码

class Solution {
    public double myPow(double x, int n) {
     if(x == 1 || n == 0) return 1;
        double ans = 1;
        long num = n;
        if(n < 0){
            num = -num;
            x = 1/x;
        }
        while(num>0){
            if((num&1)==1)
            ans *= x;
            x *= x;
            num >>= 1;
        }
        return ans;
    }
}

本文地址:https://blog.csdn.net/qq_45737068/article/details/107190218