29. Divide Two Integers

Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
問題解:コアは記号を判断してbit shiftと減算を使用することです.問題を解く過程でいろいろなcorner caseをよく処理しなければならない.例:
divisor=0 dividendまたはdivisor=Integer.MIN_vALUE divisor = Integer.MIN_VALUE

if dividend = Integer.MIN_VALUE, return 1 return 0 dividend = Integer.MIN_VALUE

if divisor = -1, return Integer.MAX_VALUE

if divisor > 0, set divisor = - divisor - calculate everything in the range of negative int Time Complexity - O(1), Space Complexity - O(1).

public class Solution {
    public int divide(int dividend, int divisor) {
        if(divisor == 0) return Integer.MAX_VALUE;
        if(dividend == 0) return 0;
        boolean hasSameSign = (divisor>0) ^ (dividend<0);
        int res = 0;
        if(divisor != Integer.MIN_VALUE && dividend != Integer.MIN_VALUE){
            divisor = Math.abs(divisor);
            dividend = Math.abs(dividend);
            for(int i=0; i<32; i++){//can be extended to binarysearch
                if((dividend>>(31 - i)) >=divisor){
                    dividend -= (divisor<0) divisor = -divisor; // dividend == Integer.MIN_VALUE
            for(int i=0; i<32; i++){//can be extended to binarysearch
                if((dividend>>(31 - i)) <=divisor){
                    dividend -= (divisor<

2ブラシの考え方は、divisor、2 divisor、4 divisor、8 divisorをそれぞれ使って試して、dividendより大きい値を見つけます.その後dividendはそれを減算します.このサイクルを繰り返します.ただし、中間値はlong型整数に変換し、Math.absのcorner case:Integer.MIN_VALUEとInteger.MAX_VALUEの値にエラーが発生しました.

public class Solution {
    public int divide(int dividend, int divisor) {
        if(divisor==0 || (dividend == Integer.MIN_VALUE && divisor == -1)) return Integer.MAX_VALUE;
        int sign = ((dividend<0) ^ (divisor<0))? -1:1;
        long dvd = Math.abs((long)dividend);
        long dvs = Math.abs((long)divisor);
        long res = 0;
        while(dvd>=dvs){
            long temp = dvs, multiple = 1;
            while(dvd>=(temp<<1)){
                temp <<=1;
                multiple <<= 1;
            }
            dvd -= temp;
            res += multiple;
        }
        return sign==1? (int)res : (int)-res;
    }
}