两数相除——不允许使用高级运算

_Zhao 发布于2019-07-30 14:26 / 1725人阅读

摘要：两数相除不允许使用高级运算实现两整数相除，不允许使用乘法除法和取余运算。如果左移一位的除数过大，除数还原。注意处理除法运算中正负号的问题。代码本题以及其它题目代码地址地址

两数相除——不允许使用高级运算 Divide Two Integers

实现两整数相除，不允许使用乘法、除法、和取余运算。

如果结果溢出（int范围为-2147483648 ~ 2147483647），返回MAX_INT

题目原文:

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

If it is overflow, return MAX_INT..

example

input: 1001, 2
output: 500

思路

利用减法，将被除数减去除数，减去的次数累计即为最后结果

为了解决效率问题，可以减去除数的倍数，利用位运算，每次除数左移一位（2倍），次数相应加对应的倍数。

如果左移一位的除数过大，除数还原。

注意处理除法运算中正负号的问题。

代码

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        pos = (dividend < 0) is (divisor < 0)
        dividend, divisor = abs(dividend), abs(divisor)
        result = 0
        while dividend >= divisor:
            tmp, i = divisor, 1
            while dividend - tmp >= 0:
                dividend -= tmp
                result += i
                i <<= 1
                tmp <<= 1
        if not pos:
            result = -result
        return min(2147483647, max(result, -2147483648))

本题以及其它leetcode题目代码github地址: github地址

云服务器私有云 python两数相除不允许的字符 linux不允许切换 php 不允许缓存

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/40711.html

「leetcode」29.两数相除

摘要：原题给定两个整数，被除数和除数。将两数相除，要求不使用乘法除法和运算符。返回被除数除以除数得到的商。右移位，等价于，除以的次方。当除以时，结果相较于除数会非常的小。我们使用循环逐渐减少右移的位数，逐渐逼近除数，当时等于，大于等于。 showImg(https://segmentfault.com/img/remote/1460000020181895); 原题给定两个整数，被除数 d...

googollee 2019-08-26 11:00 评论0 收藏0
LeetCode29.两数相除 JavaScript

摘要：给定两个整数，被除数和除数。将两数相除，要求不使用乘法除法和运算符。返回被除数除以除数得到的商。示例输入输出示例输入输出说明被除数和除数均为位有符号整数。假设我们的环境只能存储位有符号整数，其数值范围是。给定两个整数，被除数 dividend和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。...

shiyang6017 2019-08-23 15:16 评论0 收藏0
python基础教程：运算对象、运算符、表达式和语句

摘要：用一行表示它们的关系就是运算对象运算符表达式语句运算对象和运算符构成表达式，表达式构成语句运算对象运算对象就是由各种对象构成的集合，这些对象里面有些是常量，有些是变量。编程的本质就是数据和运算，数据由基本数据类型、数据结构来表示，运算就是对这些数据的各种操作，基本的加减乘除、是非判断、流程控制等等。这些操作就是今天我们要讲的运算符、表达式和语句。 showImg(http://upl...

stdying 2019-07-31 10:24 评论0 收藏0
C语言入门教程

摘要：语言入门教程一有名有姓的标识符语言规定，标识符可以是字母，数字下划线组成的字符串，并且第一个字符必须是字母或下划线。关系运算符语言中的关系运算符关系表达式的值是真和假，在程序用整数和表示。 ...

leiyi 2021-11-16 11:45 评论0 收藏0
RSA加密算法中的数学

摘要：背景不对称加密算法可是算是世界上最重要的加密算法，其中包括我们熟悉的的加密。现在我们分步来看，这个全球最重要的加密算法，都需要哪些数学知识。我们常说的算法中的多少位，就是用二进制表示后的位数，在我们例子就是位。其中表示两个数的最大公约数。背景 RSA不对称加密算法可是算是世界上最重要的加密算法，其中包括我们熟悉的https的加密。为了完全弄明白他的实现原理，我们需要对数论这门学科，有...

?xiaoxiao, 2019-08-21 17:53 评论0 收藏0