Divide Two Integers 解答

时间:2021-12-21 23:39:13

Question

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

Solution

Divide Two Integers 解答

dividend = divisor * quotient + remainder

而我们知道对于任何一个数可以表示为Σi * 2x  其中i为0或1。所以我们可以用加法实现乘法。

a = a + a 等同于 a = a * 2

因此我们可以通过对divisor乘以2,求出最大的x,然后继续求出第二大,第三大的x', x''..

注意到可能有溢出问题,解决方法是将要计算的所有数先转为long。

 public class Solution {
public int divide(int dividend, int divisor) {
boolean negative = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);
long a = Math.abs((long)dividend);
long b = Math.abs((long)divisor);
if (a < b) {
return 0;
}
long step, sum, result = 0;
while (a >= b) {
step = b;
sum = 1;
while (step + step <= a) {
step += step;
sum += sum;
}
a = a - step;
result += sum;
}
result = negative == true ? -result : result;
if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
return Integer.MAX_VALUE;
}
return (int)result;
}
}

Divide Two Integers 解答的更多相关文章

  1. &lbrack;LeetCode&rsqb; Divide Two Integers 两数相除

    Divide two integers without using multiplication, division and mod operator. If it is overflow, retu ...

  2. Leetcode Divide Two Integers

    Divide two integers without using multiplication, division and mod operator. 不用乘.除.求余操作,返回两整数相除的结果,结 ...

  3. leetcode-【中等题】Divide Two Integers

    题目 Divide two integers without using multiplication, division and mod operator. If it is overflow, r ...

  4. &lbrack;LintCode&rsqb; Divide Two Integers 两数相除

    Divide two integers without using multiplication, division and mod operator. If it is overflow, retu ...

  5. 62&period; Divide Two Integers

    Divide Two Integers Divide two integers without using multiplication, division and mod operator. 思路: ...

  6. Divide Two Integers leetcode

    题目:Divide Two Integers Divide two integers without using multiplication, division and mod operator. ...

  7. Java for LeetCode 029 Divide Two Integers

    Divide two integers without using multiplication, division and mod operator. If it is overflow, retu ...

  8. &lbrack;LeetCode&rsqb; Divide Two Integers&lpar; bit &plus; 二分法 &rpar;

    Divide two integers without using multiplication, division and mod operator. 常常出现大的负数,无法用abs()转换成正数的 ...

  9. LeetCode29 Divide Two Integers

    题目: Divide two integers without using multiplication, division and mod operator. If it is overflow, ...

随机推荐

  1. ios10&period;2真机调试包,ios升级10&period;2后需要添加

    下载地址: http://download.csdn.net/detail/koktear/9710820 添加地址: finder-应用程序-找到Xcode-右击显示包内容-Contents-Dev ...

  2. centOS安装网卡驱动

    作为一个小白来说,安装驱动之类的真是无心下手的感觉,在学习了http://www.centoscn.com/image-text/config/2013/0816/1269.html这篇帖子的步骤之后 ...

  3. poj 1007 &lpar;nyoj 160&rpar; DNA Sorting

    点击打开链接 DNA Sorting Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 75164   Accepted: 30 ...

  4. ASP&period;NET 4&period;0 Webform Bundles 压缩css&comma; js,为什么放到服务器不行

    参考文章: http://blog.csdn.net/dyllove98/article/details/8758149 文章说的很详细. 但是本地是可以完美展示(我的本地环境有4.0 也有4.5) ...

  5. Ogre实现简单地形

    利用SimpleRenderable实现DirectX 9 3D 游戏设计入门中 第十三章 地形渲染基础的简单地形,只是简单的实现了地形的基本框架,顶点,索引,纹理等,为简单起见高度都为1,适合新手做 ...

  6. Android 自动更新 &plus; IIS7 添加APK mime

    如果APK文件放在IIS下面需要添加APK的mime,否则会出现下面错误 可以在IIS上添加mime映射 .apk application/vnd.android   下面内容转自:http://ww ...

  7. 外媒:比特币大陆将于9月IPO 规模或高达180亿美元

    看看你们坚持买的比特币是否值得? 北京时间8月13日上午消息,据CoinDesk获得的文件,比特币大陆将于今年9月申请首次公开募股(IPO),其规模可能高达180亿美元,市值预计在400亿美元到500 ...

  8. 在Centos6或者7上安装Kafka最新版

    一.官网 http://kafka.apache.org/downloads.html 二.Kafka简介 Kafka是由Apache软件基金会开发的一个开源流处理平台,由Scala和Java编写.K ...

  9. Jexus &period;Net at System&period;Net&period;Sockets&period;Socket&period;Connect &lpar;System&period;Net&period;IPAddress&lbrack;&rsqb; addresses&comma; System&period;Int32 port&rpar;

    环境:Jexus(独立版)+MVC(5.2.3) +Redis+EF(6.0) Application Exception System.Net.Sockets.SocketException Con ...

  10. timeStamp(时间戳) 事件属性

    Event 对象 定义和用法 timeStamp 事件属性可返回一个时间戳.指示发生事件的日期和时间(从 epoch 开始的毫秒数). epoch 是一个事件参考点.在这里,它是客户机启动的时间. 并 ...