Divide Two Integers
LeetCode笔记 阅读(402)
编号 : 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; >} >````