當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

29. Divide Two Integers

發布時間：2024/4/15 编程问答 36 豆豆

生活随笔收集整理的這篇文章主要介紹了 29. Divide Two Integers 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

題目：

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

If it is overflow, return MAX_INT.

鏈接：?http://leetcode.com/problems/divide-two-integers/

題解：

最近在按照leetcode序號從小到大做題。剛做完strStr又要做這個，之后還有好幾道hard，真的很惡心...不過對自己CS知識技巧和理解力不足的認識又上升到一個新的高度。看到這題首先想到的就是看答案，發現很多答案都使用long來解決溢出，碰到嚴格的面試官可能會吃虧，自己面微軟時就吃過，所以我對自己的要求是 - 即使寫得蠢笨，也不可以cheat。

核心是判斷符號后使用bit shift以及減法。做題過程中要仔細處理各種corner case。比如:

　　divisor = 0
　　dividend 或者 divisor = Integer.MIN_vALUE
- divisor = Integer.MIN_VALUE
  - if dividend ?= Integer.MIN_VALUE, ?return 1
  - return 0
- dividend = Integer.MIN_VALUE
  - if divisor = -1, return Integer.MAX_VALUE
  - if divisor > 0, ?set divisor = - divisor ? - ? calculate everything in the range of negative int?

Time Complexity - O(1), Space Complexity - O(1)。 ?

public class Solution {public int divide(int dividend, int divisor) {if(divisor == 0) //corner case: divisor = 0return Integer.MAX_VALUE;boolean isNeg = false; //get sign of resultif((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0))isNeg = true;int res = 0; //resultif(dividend != Integer.MIN_VALUE && divisor != Integer.MIN_VALUE) {dividend = Math.abs(dividend);divisor = Math.abs(divisor);for(int i = 0; i < 32; i++) {res <<= 1;if((dividend >> (31 - i)) >= divisor) { // shift right dividend and compare if >= divisordividend -= (divisor << (31 - i));res++;}}} else { if(divisor == Integer.MIN_VALUE)return dividend == Integer.MIN_VALUE ? 1 : 0; //corner case: divisor = Integer.MIN_VALUEif(divisor == -1) //corner case: Integer.MIN_VALUE / -1return Integer.MAX_VALUE;if(divisor > 0) //calculate result in negative integer rangedivisor = -divisor; for(int i = 0; i < 32; i++) {res <<= 1;if((dividend >> (31 - i)) <= divisor) { // shift right dividend and compare if <= divisordividend -= (divisor << (31 - i));res++;}} }return isNeg ? -res : res;} }

另外的一個想法由于技術太渣沒驗證過，來自本科學過的電路知識。在學CRC冗余碼時好像學過一種技術叫長除法，可以計算兩個binary array相除的結果。可以使用庫函數Integer.toBinaryString把兩個input int轉換為32-bit String，然后利用類似的減，shift，減, shift來得到結果和余數。有機會要驗證試試。心得是后悔沒學好電子工程...有很多知識和技巧可以和CS結合起來，比如LSD, MSD, 真值表，卡諾圖，run-length，Huffman，FFT, DCT, 加法器減法器乘法器除法器等等。在新的領域繼續努力吧。

Follow up 可以是不用四則運算符號求加法，減法，乘法和除法。要好好看一看Computer Arithmetic Algorithms

加法：

public int add(int a, int b) {while(b != 0) {int carry = a & b; //carrya = a ^ b; //sumb = carry << 1;}return a; }

減法：

pubic int minus(int a, int b) {return plus(a, plus(~b, 1)); }

乘法：

也比較麻煩,待補充

除法：

二刷：

Java:

本來嘗試優化舊程序，把dividend和divisor全部轉化為負數然后計算。結果發現負數的位移操作比較復雜。比如 -5 >> 10 = -1, ?-5 >> 3 = -1， ?-5 >> 2 = -2。最小也就是-1了。所以最后還是用老辦法來寫。希望三刷的時候能夠找到這個巧妙規律。

public class Solution {public int divide(int dividend, int divisor) {if (divisor == 0) {return Integer.MAX_VALUE;}boolean hasSameSign = (dividend >= 0) ^ (divisor < 0); int res = 0;if (dividend != Integer.MIN_VALUE && divisor != Integer.MIN_VALUE) {dividend = Math.abs(dividend);divisor = Math.abs(divisor);for (int i = 0; i < 32; i++) {res <<= 1;if ((dividend >> (31 - i)) >= divisor) {dividend -= (divisor << (31 - i));res++;}}} else {if (divisor == -1) {return Integer.MAX_VALUE;}if (divisor == Integer.MIN_VALUE) {return dividend == divisor ? 1 : 0;}if (divisor > 0) {divisor = -divisor;}for (int i = 0; i < 32; i++) {res <<= 1;if ((dividend >> (31 - i)) <= divisor) {dividend -= (divisor << (31 - i));res++;}}}return hasSameSign ? res : -res;} }

三刷:

需要更熟練bit manipulation和比較，以及邊界條件。

Java:

public class Solution {public int divide(int dividend, int divisor) {if (divisor == 0) return Integer.MAX_VALUE;if (dividend == 0) return 0;boolean hasSameSign = (dividend > 0) ^ (divisor < 0);int res = 0;if (dividend != Integer.MIN_VALUE && divisor != Integer.MIN_VALUE) {dividend = Math.abs(dividend);divisor = Math.abs(divisor);for (int i = 0; i < 32; i++) {res <<= 1;if ((dividend >> (31 - i)) >= divisor) {dividend -= (divisor << (31 - i));res++;}}} else {if (divisor == Integer.MIN_VALUE) return dividend == divisor ? 1 : 0;if (divisor == -1) return Integer.MAX_VALUE;if (divisor > 0) divisor = -divisor;for (int i = 0; i < 32; i++) {res <<= 1;if ((dividend >> (31 - i)) <= divisor) {dividend -= (divisor <<(31 - i));res++;}}}return hasSameSign ? res : -res;} }

Update:

上面的 res <<= 1這些運算比較晦澀。

其實就是把除法結果變成 2的第i個bit位的減法。就像 ?15 = 2⁰ + 2¹ + 2² +?2^3?一樣。 ?

注意在dividend = Integer.MIN_VALUE的時候要特殊處理，這時候我們把divisor也變為負的，然后使用類似正數情況下的 shift and minus就可以了。

public class Solution {public int divide(int dividend, int divisor) {if (divisor == 0) return Integer.MAX_VALUE;if (dividend == 0) return 0;boolean sameSign = (divisor > 0) ^ (dividend < 0);int res = 0;if (divisor != Integer.MIN_VALUE && dividend != Integer.MIN_VALUE) {divisor = Math.abs(divisor);dividend = Math.abs(dividend);for (int i = 0; i < 32; i++) {if ((dividend >> (31 - i)) >= divisor) {dividend -= (divisor << (31 - i));res += (1 << (31 - i));}}} else {if (divisor == Integer.MIN_VALUE) return dividend == Integer.MIN_VALUE ? 1 : 0;if (divisor == -1) return Integer.MAX_VALUE;if (divisor > 0) divisor = -divisor;for (int i = 0; i < 32; i++) {if ((dividend >> (31 - i)) <= divisor) {dividend -= (divisor << (31 - i));res += (1 << (31 - i));}}}return sameSign ? res : -res;} }

Reference:

https://leetcode.com/discuss/26270/no-use-of-long-java-solution

轉載于:https://www.cnblogs.com/yrbbest/p/4435159.html

總結

以上是生活随笔為你收集整理的29. Divide Two Integers的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。