剑指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 }其实有很多题是可以利用位的与，或，异或来解决的，大家可以思考下平时遇到哪些题是用这种方法解决的，我后面会给出几道题，这些题都可以用异或位运算巧妙解决。发的另一道题也用到了位运算。
其实我是想跟大家说，做题的时候，有时候想想是否可以用位运算来解决。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-02-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录