29. Divide Two Integers

[hwangnk1004]

풀이

• 문제를 보며 곱셈, 나눗셈 그리고 나머지 연산을 사용하지 않고 나눗셈 연산을 하라고 ? 도저히 아이디어가 떠오르질 않았음.
  그래서 찾아본 결과, 비트연산을 응용하는 문제 라는 것을 발견했으나, 그 역시 쉽지 않았음.
  결국, 다른 사람의 코드를 보고 분석하는 방식으로 문제를 접근함.

1. 음수의 경우에는 비트 연산을 할 수 없어, 양수로 바꿔주는 사전작업을 진행한 후 dividend와 divisor의 음수 여부를 통해 예외 처리를 진행
2. 주어진 변수가 int형이라, 연산 과정에서 오버플로우가 발생할 가능성이 존재함
3. 따라서, int보다 더 큰 값을 저장할 수 있는 long 변수를 활용하여, 연산 결과가 int 범위를 벗어나게 되는 경우를 예외 처리함

class Solution {
    public int divide(int dividend, int divisor) {
        long dividend2 = dividend;
        boolean isDividendMinus = dividend < 0;
        if(isDividendMinus)
            dividend2 = -dividend2;

        long divisor2 = divisor;
        boolean isDivisorMinus = divisor < 0;
        if(isDivisorMinus)
            divisor2 = -divisor2;

        long ret = 0;
        while(divisor2 <= dividend2){
            int mask;
            for(mask = 0; mask <= 30; ++mask){
                if((divisor2 << (mask + 1)) > dividend2)
                    break;
            }

            ret += (1L << mask);
            dividend2 -= (divisor2 << mask);
        }

        if((isDividendMinus && !isDivisorMinus) || (!isDividendMinus && isDivisorMinus)){
            if(-ret < Integer.MIN_VALUE)
                ret = (Integer.MIN_VALUE + 1);
            return (int)-ret;
        }

        if(ret > Integer.MAX_VALUE)
            ret = Integer.MAX_VALUE;

        return (int)ret;
    }

}