算法第五周作业01

Description

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

Solution

 假定计算10 / 3，其中left = 10， right = 3，使用<<1 平移操作代替乘2运算，进而代替乘法运算。 1. 首先让10与3（即right<<0）比较，由于10>3，则继续下轮；     让10与6 （ 即right<<1）比较，由于10>6，则继续下轮； 让10与12（ 即right<<2） 比较，由于10<12，那么选择上轮结果2（2是这轮 10/3 的子结果）。 2. 让4（即10-6）与3比较，由于4>3，则继续下轮； 让4（即10-6）与6比较，由于4<6，那么选择上轮结果1（1是这轮 4/3 的子结果）。 3. 让1（即4-3）与3比较，由于首轮中1<4，那么此次运算子结果为0（0时1/3的子结果）。 4. 综上，10/3 的结果为2+1+0， 余数为1%3 = 1. ps: 代码中考虑到了数值溢出问题，所以将其转为long类型，并判断溢出情况，JAVA中int范围-2147483648 ~ 2147483647

Code

public int divide(int dividend, int divisor) { if (divisor == 0) { return Integer.MAX_VALUE; } // 转为long类型，方便识别溢出 long left = dividend > 0 ? dividend : -(long) dividend; long right = divisor > 0 ? divisor : -(long) divisor; long result = 0; while (true) { long subRes = 0; long div = right; // 分别跟divisor的1倍、2倍、4倍...比较 while (div <= left) { if(subRes == 0){ subRes = 1; } else { subRes = subRes << 1; } div = div << 1; } if (div == left) { // 如果左值恰好是divisor的2^n倍 result += subRes; break; } else if(subRes == 0){ // 如果左值比右值还小，则直接退出 break; } else { // 计算剩余部分，赋予左值 result += subRes; left -= div>>1; } } // 符号和溢出判断 if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) { return -(int) result; } else if (result > Integer.MAX_VALUE) { return Integer.MAX_VALUE; } else { return (int) result; } }