专栏首页苦逼的码农剑指offer:数值的整次数方

剑指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  }

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

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

本文分享自微信公众号 - 苦逼的码农(di201805)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-02-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【算法技巧】位运算装逼指南

    版权声明:本文为苦逼的码农原创。未经同意禁止任何形式转载,特别是那些复制粘贴到别的平台的,否则,必定追究。欢迎大家多多转发,谢谢。

    帅地
  • 【二叉树打卡1】二叉搜索树的后序遍历序列

    输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

    帅地
  • 从零打卡leetcode之day 3--最大子序列

    看到三个for循环,时间复杂度的O(n3)。这速度,实在是太慢了。我们来优化优化。

    帅地
  • 深入理解javascript中的继承机制(1)原型链继承机制将共有的属性放进原型中

    javascript中的继承机制是建立在原型的基础上的,所以必须先对原型有深刻的理解,笔者在之前已经写过关于js原型的文章。

    desperate633
  • 利用docker部署深度学习模型的一个最佳实践

    讲道理,docker是天然的微服务,确实是能敏捷高效的解决深度学习这一块的几个痛点。

    Python中文社区
  • 用好这个屏蔽网页广告的神器,你会觉得很爽

    来啦,我没有失踪哈,感谢大家的关心,就是最近有点忙,天天一两点才休息,第二天就没精力更文了,要工作赚饭钱嘛。

    IT小侠公社
  • GPU编程(四): 并行规约优化

    如果之前没有用过gdb, 可以速学一下, 就几个指令. 想要用cuda-gdb对程序进行调试, 首先你要确保你的gpu没有在运行操作系统界面, 比方说, 我...

    sean_yang
  • 有关Java中两个整数的交换问题

      在程序开发的过程,要交换两个变量的内容,是一种比较常见的事情。在排序算法中,就有一种就叫做“交换排序法”。在所有的排序算法,交换要排序的集合中的两个元素,几...

    ccf19881030
  • 求最大公约数

    汐楓
  • Transform 的简单理解 原

    canvas里面的transfrom与css3中的基本是一样的,唯一的不同是原点,canvas的默认原点是图形的左上角,css3是图形的中心,

    tianyawhl

扫码关注云+社区

领取腾讯云代金券