数值的整数次方

Java基础

浏览数:180

2019-3-22

AD:资源代下载服务

前言

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

题目描述

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

解答

方法1:暴力法

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

代码如下:

    public double Power(double base, int exponent) {
        // 任何数的 0 次方都是 1(0除外,不过题目并没有说 base=0时怎么处理)
        if (exponent == 0) {
            return 1;
        }
        double temp = base;
        int n = exponent;
        if (n < 0) {
            n = -n;
        }
        for (int i = 1; i < n; i++) {
            base *= temp;
        }
        return exponent < 0 ? 1 / base : base;
    }

方法2:位运算

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

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

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

代码如下:

    public double Power(double base, int exponent) {
        if(exponent == 0)
            return 1.0;
        int n = exponent;
        if (n < 0) {
            n = -n;
        }
        double sum = 1;
        double temp = base;
        while (n != 0) {
            if ((n & 1) != 0) {
                sum *= temp;
            }
            temp *= temp;
            n = n >> 1;
        }
        return exponent < 0 ? 1 / sum : sum;
  }

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

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