剑指offer：数值的整次数方

帅地

发布于 2019-03-11 07:44:51

50300

代码可运行

文章被收录于专栏：苦逼的码农苦逼的码农

运行总次数：0

代码可运行

前言

本来是打算次条每天更新面试题和算法刷题的，加上头条一共要三篇文章，实在更不来，而且两篇都看的人也不多，所以我就算法刷题和面试题论着更新，更新的时候多更新几道。

题目描述

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

解答

方法1：暴力法

这道题就简单的方法就是暴力法了，就是让 base 乘以 exponent 次 base。

代码如下：

 1    public double Power(double base, int exponent) {
 2        // 任何数的 0 次方都是 1(0除外，不过题目并没有说 base=0时怎么处理)
 3        if (exponent == 0) {
 4            return 1;
 5        }
 6        double temp = base;
 7        int n = exponent;
 8        if (n < 0) {
 9            n = -n;
10        }
11        for (int i = 1; i < n; i++) {
12            base *= temp;
13        }
14        return exponent < 0 ? 1 / base : base;
15    }

方法2：位运算

我直接举个例子吧，例如 base = 2, exponent = 13，则 exponent 的二进制表示为 1101, 那么 2 的 13 次方可以拆解为:

2^1101 = 2^0001 * 2^0100 * 2^1000。

我们可以通过 & 1和 >>1 来逐位读取 1101，为1时将该位代表的乘数累乘到最终结果。

代码如下：

 1    public double Power(double base, int exponent) {
 2        if(exponent == 0)
 3            return 1.0;
 4        int n = exponent;
 5        if (n < 0) {
 6            n = -n;
 7        }
 8        double sum = 1;
 9        double temp = base;
10        while (n != 0) {
11            if ((n & 1) != 0) {
12                sum *= temp;
13            }
14            temp *= temp;
15            n = n >> 1;
16        }
17        return exponent < 0 ? 1 / sum : sum;
18  }