兩數(shù)相除——不允許使用高級運(yùn)算

_Zhao 發(fā)布于2019-07-30 14:26 / 1832人閱讀

摘要：兩數(shù)相除不允許使用高級運(yùn)算實(shí)現(xiàn)兩整數(shù)相除，不允許使用乘法除法和取余運(yùn)算。如果左移一位的除數(shù)過大，除數(shù)還原。注意處理除法運(yùn)算中正負(fù)號的問題。代碼本題以及其它題目代碼地址地址

兩數(shù)相除——不允許使用高級運(yùn)算 Divide Two Integers

實(shí)現(xiàn)兩整數(shù)相除，不允許使用乘法、除法、和取余運(yùn)算。

如果結(jié)果溢出（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

思路

利用減法，將被除數(shù)減去除數(shù)，減去的次數(shù)累計即為最后結(jié)果

為了解決效率問題，可以減去除數(shù)的倍數(shù)，利用位運(yùn)算，每次除數(shù)左移一位（2倍），次數(shù)相應(yīng)加對應(yīng)的倍數(shù)。

如果左移一位的除數(shù)過大，除數(shù)還原。

注意處理除法運(yùn)算中正負(fù)號的問題。

代碼

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地址

云服務(wù)器 GPU云服務(wù)器 python兩數(shù)相除不允許的字符 linux不允許切換 php 不允許緩存

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/40711.html

相關(guān)文章

「leetcode」29.兩數(shù)相除

摘要：原題給定兩個整數(shù)，被除數(shù)和除數(shù)。將兩數(shù)相除，要求不使用乘法除法和運(yùn)算符。返回被除數(shù)除以除數(shù)得到的商。右移位，等價于，除以的次方。當(dāng)除以時，結(jié)果相較于除數(shù)會非常的小。我們使用循環(huán)逐漸減少右移的位數(shù)，逐漸逼近除數(shù)，當(dāng)時等于，大于等于。 showImg(https://segmentfault.com/img/remote/1460000020181895); 原題給定兩個整數(shù)，被除數(shù)?d...

googollee 2019-08-26 11:00 評論0 收藏0
LeetCode29.兩數(shù)相除 JavaScript

摘要：給定兩個整數(shù)，被除數(shù)和除數(shù)。將兩數(shù)相除，要求不使用乘法除法和運(yùn)算符。返回被除數(shù)除以除數(shù)得到的商。示例輸入輸出示例輸入輸出說明被除數(shù)和除數(shù)均為位有符號整數(shù)。假設(shè)我們的環(huán)境只能存儲位有符號整數(shù)，其數(shù)值范圍是。給定兩個整數(shù)，被除數(shù) dividend和除數(shù) divisor。將兩數(shù)相除，要求不使用乘法、除法和 mod 運(yùn)算符。返回被除數(shù) dividend 除以除數(shù) divisor 得到的商。...

shiyang6017 2019-08-23 15:16 評論0 收藏0
python基礎(chǔ)教程：運(yùn)算對象、運(yùn)算符、表達(dá)式和語句

摘要：用一行表示它們的關(guān)系就是運(yùn)算對象運(yùn)算符表達(dá)式語句運(yùn)算對象和運(yùn)算符構(gòu)成表達(dá)式，表達(dá)式構(gòu)成語句運(yùn)算對象運(yùn)算對象就是由各種對象構(gòu)成的集合，這些對象里面有些是常量，有些是變量。編程的本質(zhì)就是數(shù)據(jù)和運(yùn)算，數(shù)據(jù)由基本數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)來表示，運(yùn)算就是對這些數(shù)據(jù)的各種操作，基本的加減乘除、是非判斷、流程控制等等。這些操作就是今天我們要講的運(yùn)算符、表達(dá)式和語句。 showImg(http://upl...

stdying 2019-07-31 10:24 評論0 收藏0
C語言入門教程

摘要：語言入門教程一有名有姓的標(biāo)識符語言規(guī)定，標(biāo)識符可以是字母，數(shù)字下劃線組成的字符串，并且第一個字符必須是字母或下劃線。關(guān)系運(yùn)算符語言中的關(guān)系運(yùn)算符關(guān)系表達(dá)式的值是真和假，在程序用整數(shù)和表示。 ...

leiyi 2021-11-16 11:45 評論0 收藏0
RSA加密算法中的數(shù)學(xué)

摘要：背景不對稱加密算法可是算是世界上最重要的加密算法，其中包括我們熟悉的的加密?，F(xiàn)在我們分步來看，這個全球最重要的加密算法，都需要哪些數(shù)學(xué)知識。我們常說的算法中的多少位，就是用二進(jìn)制表示后的位數(shù)，在我們例子就是位。其中表示兩個數(shù)的最大公約數(shù)。背景 RSA不對稱加密算法可是算是世界上最重要的加密算法，其中包括我們熟悉的https的加密。為了完全弄明白他的實(shí)現(xiàn)原理，我們需要對數(shù)論這門學(xué)科，有...

?xiaoxiao, 2019-08-21 17:53 評論0 收藏0