[LeetCode] Divide two integers

這題之前實驗室同學面試前有刷過，前陣子聚餐好像有聽到她在說這題

https://leetcode.com/problems/divide-two-integers/description/

不能用 * / % 這幾個operator

所以能用的其實就滿少的，跟加減乘除有關係的大概就只剩加減號XDD

但總不可能用慢慢減的，所以想這應該是跟 shift有關係的 <<

乍看之下<<這個operator好像只跟2有關係

不過後來想想任何數字都能用bits 2的冪次做表示啊，代表商數也可以

舉個例子 86除以3 可以看成 86=3*24+2

24這個商數可以看成 16+8=2^4+2^3

然後86可以看成 = 3(2^4+2^3)+2

所以第一步驟就是找到組成商數裡的那個最大2冪次

然後 86-24*3 = 14 再繼續重複剛剛的步驟

一直拆解到最後不能再除為止

上述所說的就是loop裡面在做的事

其餘是一些邊界case的判斷、解overflow的方式

class Solution {
public:
    int divide(int dividend, int divisor) {
        
        if (!divisor || (dividend == INT_MIN && divisor == -1))
            return INT_MAX;        
        
        int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;        
        int ans = 0;  
             
        
        long long divid = labs(dividend);
        long long divis = labs(divisor);
        
        while(divid >= divis)
        {
            long long tmp = divis;
            long long tmp_multiple = 1;
            
            while(divid >= tmp)
            {
                tmp = tmp << 1; 
                tmp_multiple = tmp_multiple << 1;
            }
                    
            divid -= tmp >> 1;
            ans += tmp_multiple >> 1;
        }        
        
        return sign == 1 ? ans : -ans; 
    }
};