Divide Two Integers

编号 : 29      
难度 : <font color="orange">Medium</font>

# 题目 :  
>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: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

# 解 :  
```C#
public class Solution {
    public int Divide(int dividend, int divisor) {
        bool sign1 = dividend > 0;
        bool sign2 = divisor > 0;
        
        /* 因为负值的范围更大，所以全部使用负值进行计算 */
        if(sign1)
            dividend = -(dividend);
        if(sign2)
            divisor = -(divisor);
        
        /* 返回值，也使用负值暂存 */
        int ret = 0;
        
        /* |dividend| > |dividend| */
        while(dividend <= divisor)
        {
            /* 通过位运算将[除数的绝对值]进行放大
             * 减少减法运算的次数
             */
            int bigDivisor = divisor;
            int temp = 1; // 放大了多少倍
            while(bigDivisor >= dividend && bigDivisor >= Int16.MinValue)
            {
                bigDivisor <<= 1;
                temp <<= 1;
            }
            
            /* 上面循环会多一次 */
            if(bigDivisor < dividend)
            {
                bigDivisor >>= 1;
                temp >>= 1;
            }
            
            /* 被除数减去该值 */
            dividend -= bigDivisor;
            ret -= temp;
        }
        
        /* 处理符号 */
        if(sign1 == sign2)
        {
            if(ret != int.MinValue)
                ret = -ret;  // 恢复为正数
            else
                ret = int.MaxValue; // 溢出了
        }
        
        return ret;
    }
}
```

# 分析 :  
这道题要求实现32位有符号整数的除法运行，要求不能使用乘法运算符(`*`)、除法运算符(`/`)和模运算符(`%`)。  

> 另外题目假设所属环境只能保存32位有符号整数，所以严格来讲不能使用`Int64`和`Uint32`

上述解法总体而言，是将除法转换为减法，非常简单，但是纯粹的使用减法一次次减去除数，运算次数太多，因此使用位运算将除数进行放大后再减。  

由于负数的范围比正数多一，如果在运算过程中使用正数保存中间值，有可能溢出，因此使用负数来保存中间值，最后给结果添加正负号。  

之前的题目我都使用`C++`解答，而上述解法我使用的是`C#`，这是因为**在`C++`中，负数的位左移运算是未定义行为(Undefined Behavior)**，并且**有符号数的位移运算都不建议使用**。

>在`C++`中，由于`bigDivisor`和`temp`是负数，因此不能进行左移运算。
>```C++
>while(bigDivisor >= dividend && bigDivisor >= Int16.MinValue)
>{
>   bigDivisor <<= 1;
>   temp <<= 1;
>}
>````