這題在 Leetcode 上是一題倒讚數遠大於讚數的一道題目，一般來說這種題目應該直接跳過，但這題我個人認為是可以學習到如何處理 overflow 和 edge case 的好題目。
理解題意
題目要求你實現除法，但是不能使用乘法、除法和取餘數。
題目有兩個限制需要注意：
- 所有 integer 只能以 signed integer 的範圍內來儲存，換言之，不能偷懶用
long或更大範圍型態的 data type 來避開 overflow 的問題。 - 如果除法結果是小於 INT_MIN 或大於 INT_MAX ，需分別以 INT_MIN 或 INT_MAX 來表示。
寫下幾個 test case 並討論 input/output 格式
-
題目的 Input 為 [-2^31, 2^31-1] ，如果要對
INT_MIN取絕對值， 就會造成 overflow ，因為正數無法表達 2^31 ，是否要針對 -2^31 來做 edge case 處理？- 換個角度想，其實負數可以表達的範圍反而更大，何不就用負數來進行操作，當計算結束後，最後再來處理答案應該為正或負。
-
除法過程中，要怎麼找出 overflow 並處理呢？
- 試想 a / b = c ，若 a 跟 b 都是正整數，則 c 肯定比 a 跟 b 更靠近 0 ，換言之，不可能會發生 overflow 的狀況。若是 a 跟 b 中，有一個或都為負整數，那除法結果 c 還是會更靠近 0 。
- 唯一當被除數為 INT_MIN (-2^31) ，除數為 -1 ，則答案為 2^31，即發生 overflow 了，只有這個 edge case 需要特別處理。
-
最後答案為正數還是負整數？
- 題目要求不能使用乘法或除法，最簡單方式就是如果兩數為一正一負，則答案必定為負整數。
方法 1 Strightforward Substraction (Not accepted)
class Solution {
public:
int divide(int dividend, int divisor) {
bool neg_flag = false;
if (dividend == INT_MIN && divisor == -1)
return INT_MAX;
if (dividend > 0)
{
dividend = -dividend;
neg_flag = !neg_flag;
}
if (divisor > 0)
{
divisor = -divisor;
neg_flag = !neg_flag;
}
int result = 0;
while (dividend <= divisor)
{
dividend -= divisor;
result++;
}
if (neg_flag)
result = -result;
return result;
}
};Time Complexity O(n)
Space Complexity O(1)
遇到以下 input 會發生 TLE ，雖然 time complextity 僅為 O(n) ，但 n 卻可以大到 $2^{31}$ 。
-2147483648
1在解釋方法 2 之前，我想先解釋方法 1 存在的一個問題，在遇到以下 edge case 時將發生 overflow ：
INT_MIN
1以方法 1 來說， 一律將 dividend 和 divisor 都強制換為負整數，在 while 迴圈中，result 會不斷被加到 INT_MAX+1 的大小，這時候將發生 overflow ，因此上面方法 1 中的 result 每次應該遞增 -1 。
方法 2 Exponential substraction
既然會遇到 TLE , 代表需要想辦法優化方法 1 ，比起不斷的減去 divisor ，嘗試將 divisor 做加倍，dividend 可以一次盡可能減去 divisor 的倍數。
舉例來說，如果 dividend 和 divisor 分別為 20 和 2 ， 不斷嘗試將 2 加倍，並不斷跟 dividend 比較，當 2 加倍到 16 時，已經無法再往上增加了，因次將 20 減去 16 ，剩下的 4 再跟 divisor 2 再做一輪同樣的處理。
這個方法有效降低時間複雜度到 O ( log^2 n ) 。
在加倍 divisor 時候，要避免發生 overflow 狀況，當 divisor 已經倍增到大於 INT_MIN 的一半時，就應該停止遞增。
class Solution {
public:
int divide(int dividend, int divisor) {
if (dividend == INT_MIN && divisor == -1)
{
return INT_MAX;
}
bool neg_flag = false;
if (dividend > 0)
{
dividend = -dividend;
neg_flag = !neg_flag;
}
if (divisor > 0)
{
divisor = -divisor;
neg_flag = !neg_flag;
}
int HALF_INT_MIN = INT_MIN >> 1;
int result = 0;
while (dividend <= divisor)
{
int big_divisor = divisor;
int power_of_two = -1;
while (big_divisor > HALF_INT_MIN
&& dividend <= big_divisor+big_divisor)
{
big_divisor += big_divisor;
power_of_two += power_of_two;
}
dividend -= big_divisor;
result+= power_of_two;
}
if (!neg_flag)
result = -result;
return result;
}
};方法 3 Use array to store exponential search value
前一個方法透過不斷將 divisor 加倍，來加速減法過程，每次加倍過程，都是以同樣的除數當基底，與其每輪都從除數開始重複加倍，不如就在第一次加倍時候，把結果存在 array 內，下次就再從 array 內拿出來做比較就好。
class Solution {
public:
int divide(int dividend, int divisor) {
if (dividend == INT_MIN && divisor == -1)
{
return INT_MAX;
}
bool neg_flag = false;
if (dividend > 0)
{
dividend = -dividend;
neg_flag = !neg_flag;
}
if (divisor > 0)
{
divisor = -divisor;
neg_flag = !neg_flag;
}
int HALF_INT_MIN = INT_MIN >> 1;
vector<int> double_cache, two_cache;
int double_divisor = divisor;
int power_of_two = -1;
double_cache.push_back(double_divisor);
two_cache.push_back(power_of_two);
/* Build cache array to store doubles */
while (double_divisor >= HALF_INT_MIN
&& dividend <= double_divisor+double_divisor)
{
double_divisor += double_divisor;
power_of_two += power_of_two;
double_cache.push_back(double_divisor);
two_cache.push_back(power_of_two);
}
int result = 0;
// Iteration starts from the largest index
for (int i=double_cache.size()-1; i>=0; i--) {
if (double_cache[i] >= dividend) {
dividend -= double_cache[i];
result += two_cache[i];
}
}
if (!neg_flag)
result = -result;
return result;
}
};Time Complexity O(log n)
Space Complexity O(log n)