[LeetCode] 29. Divide Two Integers

轉自LeetCode

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

If it is overflow, return MAX_INT.

<Solution>

這題要來算除法，但是不能用乘除以及餘數的運算子

用加減來算，速度會太慢

還有一個方法，就是用 bit operation

• 每次把除數乘2 (左移一位)，看是不是還小於被除數。如果小於，就重覆此步驟；如果大於，被除數減掉最後的數字

• 同時間也要記錄，到底乘二了多少次

• 重複上述步驟，直到被除數小於除數

用個例子說明 : 102 / 5

round 1: 102 / 5，quotient = 0

被除數    除數    記數
 102      5      1
 102      10     2
 102      20     4
 102      40     8
 102      80     16

round 2 : (102 - 80) / 5，quotient = 16

被除數    除數    記數
 22       5      1
 22       10     2
 22       20     4

22 - 20  = 2 < 5，結束

quotient = 16 + 4 = 20 = 102 / 5

code 如下