[leetcode]29. Divide Two Integers

29. Divide Two Integers

 

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3 Output: 3

Example 2:

Input: dividend = 7, divisor = -3 Output: -2

 

class Solution(object):
    def divide(self, dividend, divisor):
        if dividend == 0: return 0

        # initialize
        i, result, p, q = map(abs, (0, 0, dividend, divisor))

        # phase 1
        while q << i <= p: i += 1

        # phase 2
        for j in reversed(range(i)):
            if q << j <= p: p, result = p - (q << j), result + (1 << j)

        # stupid leetcode restrictions
        if (dividend > 0) != (divisor > 0) or result < -1 << 31: result = -result
        return min(result, (1 << 31) - 1)

이거는 손계산할때 나눗셈하는 것과 같은 원리이다.

phase 1은 

divisor을 왼쪽으로 몇번 쉬프트 할때까지 dividend보다 작은지를 체크한다. 

그말은 몫이 2진수로 몇자리가 되는지를 체크하는것

그다음 큰수부터 나누면서 dividend를 나눈만크 줄여주고, 결과는 나눈 수 만큼 더해준다.

그리고 음수거나 , 음수범위보다 더 크면 부호를 바꿔서 

dividend나 divisor중에 하나라도 음수면 음수의 결과가 나올 수 있도록 하고, 

음수 범위보다 더 크면 부호를 바꿔서 양수이면서 integer범위보다 더 큰 수가 될것이고 

그러면 return시에 min에서 1<<31 -1보다 크므로 1<<31 -1이 나올 수 있도록 처리된다.

 

어려웠다.... 개념적으로는 알겠는데

이걸 구현하려니까 어떻게 해야할지 잘 모르겠었고 

2진수로 만들려니까 어렵다........