兩數相除——不允許使用高級運算

_Zhao 發布于2019-07-30 14:26 / 1818人閱讀

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

兩數相除——不允許使用高級運算 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地址

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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