Leetcode 29 Divide Two Integers 位操作的巧妙运用

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

If it is overflow, return MAX_INT.

题意很简单,实现两数除法,但是不能用乘法,除法和取模。

怎么样?第一感觉就是用减法,但是被除数很大,除数为1的时候肯定会超时,

那就模拟手工除法,按位减呗,这样每一位减的次数最多不会超过10次,

很好,问题又来了,在不允许乘除取模的情况下,如何获取高位?

卡住了。。。

我想了一种列出10,100,1000....位表的方法,通过对每一位反复减去对应位表的数的操作获取每一位的数字,可是这种方法实现起来细节太过繁琐了。

我看了一下discuss,他们用了一种类似进制转换的方法,用位操作代替了*2的操作,想法很好,

其实本质也是模拟除法,只不过它以除数为基,每次扩大为原来的两倍,精髓在于能想到位操作。

注意溢出的边界和中间变量的类型,已标在代码中。

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(divisor==0 || (dividend == INT_MIN && divisor == -1)) return INT_MAX;//两种溢出的情况
        int flag1=dividend<0?-1:1,flag2=divisor<0?-1:1;
        int pre=flag1==flag2?1:-1;
        long long dividend2=flag1==1?dividend:-(long long)dividend; //转正数,int类型在INT_MIN值下会炸
        long long divisor2=flag2==1?divisor:-(long long)divisor;
        int result=0;
        while(dividend2>=divisor2) 
        {
            long long rm=divisor2,base=1;
            while(dividend2>=rm)
            {
                rm<<=1;
                base<<=1;
            }
            rm>>=1;
            base>>=1;
            dividend2-=rm;
            result+=base;
        }
        result=pre==1?result:-result; //符号
        return result;
    }
};

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏五分钟学算法

每天一算:Minimum Size Subarray Sum

leetcode上第209号问题:Minimum Size Subarray Sum

7710
来自专栏Hongten

一看就懂的快速排序方法_java版

=================================================

2.4K20
来自专栏ThoughtWorks

TW洞见 | 崔鹏飞:Scala中Stream的应用场景及其实现原理

假设一个场景 需要在50个随机数中找到前两个可以被3整除的数字。 听起来很简单,我们可以这样来写: ? 一个产生50个随机数的函数; 一个检查某数字是否能被3...

35740
来自专栏Golang语言社区

map按key和按value排序

看一个题: 查找和排序 题目:输入任意(用户,成绩)序列,可以获得成绩从高到低或从低到高的排列,相同成绩 都按先录入排列在前的规则处理。 例示: jack 70...

59080
来自专栏小文博客

小文’s blog–插入排序–《蓝桥杯代码笔记5》

17320
来自专栏yl 成长笔记

UML 类图基础

定义:两个类之间的强依赖关系, 可以为单向,亦可为双向。常见表现形式 为 A 类中有 B 类型的成员变量。

12040
来自专栏云霄雨霁

排序----选择排序

17000
来自专栏Golang语言社区

map按key和按value排序

看一个题: 查找和排序 题目:输入任意(用户,成绩)序列,可以获得成绩从高到低或从低到高的排列,相同成绩 都按先录入排列在前的规则处理。 例示: jack 70...

39830
来自专栏python成长之路

集合常用操作

17640
来自专栏搞前端的李蚊子

JS使用循环按指定倍数分割数组组成新的数组的方法

 今天一个新人同事问了我一个问题,就是有一个像下边这种不知道具体长度的数组,想以每4个为一组,重新组合为一个二维数组,很简单的需求只需要用到一个循环再去取余数就...

48170

扫码关注云+社区

领取腾讯云代金券