剑指offer：数值的整次数方

前言

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

题目描述

给定一个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  }

其实有很多题是可以利用位的与，或，异或来解决的，大家可以思考下平时遇到哪些题是用这种方法解决的，我后面会给出几道题，这些题都可以用异或位运算巧妙解决。发的另一道题也用到了位运算。

其实我是想跟大家说，做题的时候，有时候想想是否可以用位运算来解决。

往期

                关注我 ，每天进步一点点