資訊專欄INFORMATION COLUMN
摘要：原題給定兩個(gè)整數(shù)，被除數(shù)和除數(shù)。將兩數(shù)相除，要求不使用乘法除法和運(yùn)算符。返回被除數(shù)除以除數(shù)得到的商。右移位，等價(jià)于，除以的次方。當(dāng)除以時(shí)，結(jié)果相較于除數(shù)會(huì)非常的小。我們使用循環(huán)逐漸減少右移的位數(shù)，逐漸逼近除數(shù)，當(dāng)時(shí)等于，大于等于。
原題
給定兩個(gè)整數(shù)，被除數(shù)?dividend?和除數(shù)?divisor。將兩數(shù)相除，要求不使用乘法、除法和 mod 運(yùn)算符。
返回被除數(shù)?dividend?除以除數(shù)?divisor?得到的商。
示例?1:
輸入: dividend = 10, divisor = 3 輸出: 3
示例?2:
輸入: dividend = 7, divisor = -3 輸出: -2
說(shuō)明：
被除數(shù)和除數(shù)均為 32 位有符號(hào)整數(shù)。
除數(shù)不為?0。
假設(shè)我們的環(huán)境只能存儲(chǔ) 32 位有符號(hào)整數(shù)，其數(shù)值范圍是 [?2^31,? 2^31?? 1]。本題中，如果除法結(jié)果溢出，則返回 231?? 1。
思路解題思路來(lái)自評(píng)論區(qū)的foxleezh大神。題目中明確不能使用/, 我們可以右移模擬除法，右移可以等價(jià)于下面的等式
右移1位，等價(jià)于，除以2的1次方。
右移2位，等價(jià)于，除以2的2次方。
右移3位，等價(jià)于，除以2的3次方。
a / 2 === a >> 1 a / 4 === a >> 2 a / 8 === a >> 3
被除數(shù) / 除數(shù) === 商……余數(shù) 等價(jià)于 ?? 被除數(shù) === (商 * 除數(shù)) + 余數(shù) 等價(jià)于 ?? (被除數(shù) - 余數(shù)) / 商 === 除數(shù)
假設(shè)，我們的被除數(shù)等于100，除數(shù)等于5。
根據(jù)等式(被除數(shù) - 余數(shù)) / 商 == 除數(shù)，我們首先要找到，100除以多少最接近于除數(shù)（或者說(shuō)，除以多少時(shí)會(huì)大于等于除數(shù)）。
當(dāng)100除以2^31時(shí)，結(jié)果相較于除數(shù)會(huì)非常的小。我們使用循環(huán)逐漸減少右移的位數(shù)，逐漸逼近除數(shù)，當(dāng)100 >>> 4（100 / 16）時(shí)等于6，大于等于5。
這時(shí)，我們可以肯定商是大于16（2的四次方）的某個(gè)數(shù)（或者說(shuō)，100至少包含16個(gè)5）。
我們使用被除數(shù) = 被除數(shù) - 16 * 除數(shù)等于還剩下的沒(méi)有除干凈的數(shù)。目前還剩下20。我們?cè)俅问褂蒙鲜龅姆椒?，再次逼近除?shù)（獲取20里還有幾個(gè)5）。最終得到最后的結(jié)果。
代碼
/**
* @param {number} dividend
* @param {number} divisor
* @return {number}
*/
var divide = function(dividend, divisor) {
// 判斷結(jié)果是否為負(fù)數(shù)
const isNegative = (dividend ^ divisor) < 0
// 統(tǒng)一按正數(shù)處理
dividend = Math.abs(dividend)
divisor = Math.abs(divisor)
if (dividend === 0) {
return 0
}
if (dividend === 2147483648 && divisor === 1) {
// 避免結(jié)果溢出
return isNegative ? -dividend/divisor : dividend/divisor - 1
}
let result = 0
for (let i = 31; i >= 0; i--) {
// 注意這里需要使用無(wú)符號(hào)右移
if ((dividend >>> i) >= divisor) {
result += Math.pow(2, i)
dividend -= Math.pow(2, i) * divisor
}
}
return isNegative ? -result : result
};
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/106965.html
摘要：給定兩個(gè)整數(shù)，被除數(shù)和除數(shù)。將兩數(shù)相除，要求不使用乘法除法和運(yùn)算符。返回被除數(shù)除以除數(shù)得到的商。示例輸入輸出示例輸入輸出說(shuō)明被除數(shù)和除數(shù)均為位有符號(hào)整數(shù)。假設(shè)我們的環(huán)境只能存儲(chǔ)位有符號(hào)整數(shù)，其數(shù)值范圍是。 給定兩個(gè)整數(shù)，被除數(shù) dividend和除數(shù) divisor。將兩數(shù)相除，要求不使用乘法、除法和 mod 運(yùn)算符。 返回被除數(shù) dividend 除以除數(shù) divisor 得到的商。...
摘要：分布式的管理和當(dāng)我在談?wù)摷軜?gòu)時(shí)我在談啥狀態(tài)碼詳解無(wú)狀態(tài)協(xié)議和請(qǐng)求支持哪些方法分層協(xié)議棧有哪些數(shù)據(jù)結(jié)構(gòu)運(yùn)用場(chǎng)景說(shuō)說(shuō)你常用的命令為什么要有包裝類面向?qū)ο蟮奶卣魇巧妒巧队惺裁春锰幭到y(tǒng)設(shè)計(jì)工程在線診斷系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理軟技能 HTTP 【HTTP】分布式session的管理 【HTTP】Cookie和Session 【HTTP】當(dāng)我在談?wù)揜estFul架構(gòu)時(shí)我在談啥？...
摘要：兩數(shù)相除不允許使用高級(jí)運(yùn)算實(shí)現(xiàn)兩整數(shù)相除，不允許使用乘法除法和取余運(yùn)算。如果左移一位的除數(shù)過(guò)大，除數(shù)還原。注意處理除法運(yùn)算中正負(fù)號(hào)的問(wèn)題。代碼本題以及其它題目代碼地址地址 兩數(shù)相除——不允許使用高級(jí)運(yùn)算 Divide Two Integers 實(shí)現(xiàn)兩整數(shù)相除，不允許使用乘法、除法、和取余運(yùn)算。 如果結(jié)果溢出（int范圍為-2147483648 ~ 2147483647），返回MAX_...
摘要：題目要求在不使用乘法，除法和求余操作的情況下，計(jì)算兩個(gè)整數(shù)相除的結(jié)果。如果溢出了，則返回最大值。在這里核心思路是使用逆向二分法和遞歸的思路來(lái)進(jìn)行計(jì)算。在這里我們使用取值范圍更廣的來(lái)處理數(shù)值溢出的場(chǎng)景。 題目要求 Divide two integers without using multiplication, division and mod operator. If it is o...
摘要：很容易想到，我們每次用被除數(shù)減去除數(shù)，進(jìn)行減法的次數(shù)就是最終結(jié)果。這道題的采取了一種類似二分查找的思想。除了這些，這道題還要注意一些邊界情況的判斷，例如除數(shù)或被除數(shù)為，值溢出等。 題目詳情 Divide two integers without using multiplication, division and mod operator.If it is overflow, retu...
閱讀 920·2023-04-26 01:37
閱讀 3396·2021-09-02 15:40
閱讀 987·2021-09-01 10:29
閱讀 2915·2019-08-29 17:05
閱讀 3443·2019-08-28 18:02
閱讀 1204·2019-08-28 18:00
閱讀 1510·2019-08-26 11:00
閱讀 2642·2019-08-26 10:27
