[LeetCode] 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

Note:

• Both dividend and divisor will be 32-bit signed integers.
• The divisor will never be 0.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31,  2^31 − 1]. For the purpose of this problem, assume that your function returns 2^31 − 1 when the division result overflows.

Approach

나누기 문제인데 나누기를 못쓴다.

곱하기도 mod도 못쓴다.

그럼 divisor로 dividend가 divisor보다 작아질때까지 빼면서 얼마나 뺐는지 세야하는데

이를 빨리 하기 위해 divisor를 쉬프트 연산으로 2씩 곱하면서 count의 폭을 늘려나간다.

여기서 주의해야할 점은 음수는 shift가 안되기 때문에 미리 부호는 계산한 후 양수끼리 나누기를 해야하고

쉬프트 연산하다가 int범위를 넘어갈 수 있기 때문에 long long 변수를 사용하고

-2^31에 -1을 곱하면 int범위가 넘어가기 때문에 -2^31 / -1 일때를 예외처리 해야한다.

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_DivideTwoIntegers.cpp

chi3236/algorithm