一. 題目描述
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
二. 題目分析
題目的意思簡單明了，就是要求不使用乘法、除法和取余mod，輸入兩個整數，輸出除法操作的結果。
出去乘除法，剩下的只有加減法和位運算，這是不難想到的，而直接使用減法，對被除數逐次減去除數大小的值，記錄被減次數，肯定是可以得出和除法操作一樣的結果，但該方法比較傻瓜，且會超時，時間復雜度為O(n)。
使用位運算可以做到O(logn)的復雜度，但要一步想到具體操作卻也不那麼簡單，首先，我們知道任何一個整數都可以表示成以2的冪為底的一組基的線性組合，即num = flag0 * 2^0 + flag1 * 2^1 + flag2 * 2^2 + ... + flagn * 2^n 其中，flag0, flag1, flag2, ..., flagn 取值為0 & 1。
基於以上事實，如果令：dividend / divisor = num，則有：
dividend = divisor * num = divisor * (flag0 * 2^0 + flag1 * 2^1 + flag2 * 2^2 + ... + flagn * 2^n)
對於除數，使用移位操作<<使其每次翻倍，從而減少減法求商的次數。以下是步驟：
當被除數大於除數時，對除數乘2（代碼中使用變量step用於記錄每次除數乘2），直到step大於被除數為止。記錄移位操作的次數i。 如果被除數大於除數，那麼被除數減去step。直到被除數小於除數。保存結果。 輸出結果result。注：
byte：128~127 (1Byte)
short ：32768~32767 (2Bytes)
int：-2147483648~2147483647 (4Bytes)
long：-9223372036854774808~9223372036854774807 (8Bytes)
三. 示例代碼
class Solution {
public:
int divide(int dividend, int divisor) {
if (dividend == 0 || divisor == 0) return 0;
if (dividend == INT_MIN && divisor == -1) return INT_MAX; // 溢出
bool negative = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);
long positiveDividend = abs(long(dividend));
long positiveDivisor = abs(long(divisor));
long result = 0;
while (positiveDividend >= positiveDivisor) // 被除數大於除數
{
long step = positiveDivisor;
for (int i = 0; positiveDividend >= step; ++i, step <<= 1)
{
positiveDividend = positiveDividend - step;
result += 1 << i;
}
}
return negative ? -result : result;
}
};
四. 小結
使用位運算來解決此類問題，是挺容易想到的，但是具體如何操作又是另外一回事。
