#LeetCode：29. Divide Two Integers

這題因為有強制限制不可以用乘法、加法、餘數來做，所以我們可以改成利用二進位與位元運算的方式去做除法。一般我們在做除法時算完所得出的解，它其中的每個位數所代表的意思是：將除數根據所位於的進位制(ex. 十進位、二進位)去位移了該位數，然後找出在該位數到底乘以多少後，最大能夠小於等於目前被除數的數值，底下舉個例子。

• 10654 除以 3 等於 3551
  • 第一位的 3 ，是將 3 依照十進位制移到千位數(即 3000)，找出在 0 ~ 9 中 3000 乘上的數字還可以小於 10654 的答案，即是 3 ，並且 10654 – 3000 * 3 = 1654。
  • 第二位的 5 ，是將 3 依照十進位制移到百位數(即 300)，找出在 0 ~9 中 300 乘上的數字還可以小於 1654 的答案，即是 5 ，並且 1654 – 300 * 5 = 154。
  • 第三位的 5 ，是將 3 依照十進位制移到十位數(即 30)，找出在 0 ~ 9 中 30 乘上的數字還可以小於 154 的答案，即是 5 ，並且 154 – 30 * 5 = 4。
  • 第四位的 1 ，是將 3 依照十進位制移到個位數(即 3)，找出在 0 ~ 9 中 3 乘上的數字還可以小於 4 的答案，即是 1 ，並且 4 – 3 * 1 = 1。

但是這中間要做位移會用到被禁止使用的乘法，且要找出 0 ~ 9 去乘的動作也避不掉乘法，但是如果將兩邊改用二進位後，位移的部分就可以使用位元運算子(Bitwise Operator)中的 Shift ，並且因為二進位只會有 0 跟 1 ，所以只要知道位移完的數值有沒有小於剩下的數字即可，底下再舉個例子。

• 10654(10100110011110) 除以 3(11) 等於 3551(110111011111)
  • 第一位的 1 ，是將 11 依照二進位制移到千億位數(即 1100000000000)，找出位移完後的數字有沒有小於 10100110011110 ，有即是 1 ，並且 10100110011110 – 1100000000000 = 1000110011110。
  • 第二位的 1 ，是將 11 依照二進位制移到百億位數(即 110000000000)，找出位移完後的數字有沒有小於 1000110011110 ，有即是 1 ，並且 1000110011110 – 110000000000 = 10110011110。
  • 第三位的 0 ，是將 11 依照二進位制移到十億位數(即 11000000000)，找出位移完後的數字有沒有小於 10110011110 ，沒有即是 0 。
  • 第四位的 1 ，是將 11 依照二進位制移到億位數(即 1100000000)，找出位移完後的數字有沒有小於 10110011110 ，有即是 1 ，並且 10110011110 – 1100000000 = 1010011110。
  • 第五位的 1 ，是將 11 依照二進位制移到千萬位數(即 110000000)，找出位移完後的數字有沒有小於 1010011110 ，有即是 1 ，並且 1010011110 – 110000000 = 100011110。
  • 第六位的 1 ，是將 11 依照二進位制移到百萬位數(即 11000000)，找出位移完後的數字有沒有小於 100011110 ，有即是 1 ，並且 100011110 – 11000000 = 1011110。
  • 第七位的 0 ，是將 11 依照二進位制移到十萬位數(即 1100000)，找出位移完後的數字有沒有小於 1011110 ，沒有即是 0 。
  • 第八位的 1 ，是將 11 依照二進位制移到萬位數(即 110000)，找出位移完後的數字有沒有小於 1011110 ，有即是 1 ，並且 1011110 – 110000 = 101110。
  • 第九位的 1 ，是將 11 依照二進位制移到千位數(即 11000)，找出位移完後的數字有沒有小於 101110 ，有即是 1 ，並且 101110 – 11000 = 10110。
  • 第十位的 1 ，是將 11 依照二進位制移到百位數(即 1100)，找出位移完後的數字有沒有小於 10110 ，有即是 1 ，並且 10110 – 1100 = 1010。
  • 第十一位的 1 ，是將 11 依照二進位制移到十位數(即 110)，找出位移完後的數字有沒有小於 1010 ，有即是 1 ，並且 1010 – 110 = 100。
  • 第十二位的 1 ，是將 11 依照二進位制移到個位數(即 11)，找出位移完後的數字有沒有小於 100 ，有即是 1 ，並且 100 – 11 = 1。

大致上的做法這樣做即可。其他比較需要注意的地方是要先用迴圈找到最高是幾位，以及雖然在 32-bit 整數裡唯一會 Overflow 的除法 -2147483648 除以 -1 ，所以只有這個答案會是直接拿32-bit 整數最大值做答案，但是其實要做 -2147483648 除以其他數字都還是很困難，所以還是用 64-bit 整數解這題會比較方便。

C++(12ms)

/*******************************************************/
/* LeetCode 29. Divide Two Integers                    */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2018/10/24                                 */
/*******************************************************/
#include <cstdlib>
#include <climits>

class Solution {
public:
  int divide(int dividend, int divisor) {
    if(divisor == 0 || (dividend == INT_MIN && divisor == -1)){
      return INT_MAX;
    }

    bool hasSign = ((dividend < 0) != (divisor < 0));
    long long int p = abs((long long int)dividend);
    long long int q = abs((long long int)divisor);

    if(p < q) return 0;

    int maxShiftDigit = 0;
    while((q << maxShiftDigit) <= p) ++maxShiftDigit;

    int result = 0;
    for(int i = maxShiftDigit - 1 ; i >= 0 ; --i){
      unsigned int shiftValue = q << i;
      if(shiftValue <= p){
        result += (1 << i);
        p -= shiftValue;
      }
    }

    return hasSign ? -result : result;
  }
};