一、问题描述
输入2个int型整数，它们进行除法计算并返回商，要求不得使用乘号'*'、除号'/'及求余符号'%'。 当发生溢出时，返回最大的整数值。假设除数不为0。例如，输入15和2，输出15/2的结果，即7。
二、问题分析
可以使用的运算符号是加法和减法，处理好边界值(除数是-2^31,除数是-1时，会产生溢出)
方法1、使用被除数减去除数的方式，计算商；时间复杂度O(n)。
方法2、使用被除数减去除数的倍数的方式，计算商；时间复杂度O(logn)。
三、代码实现
/** * @param dividend 被除数 * @param divisor 除数 * @return 商 * 被除数÷除数=商 */ public int divide(int dividend, int divisor) { //除数是-2^31,除数是-1时，会产生溢出，返回最大值(int范围-2^31————2^31-1)； if (dividend == Integer.MIN_VALUE && divisor == -1) { return Integer.MAX_VALUE; } //将正数转换为负数计算(正数转换为负数不会溢出) int negative = 2; if (dividend > 0) { negative--; dividend=-dividend; } if (divisor > 0) { negative--; divisor=-divisor; } int result = divideCore(dividend, divisor); //如果除数和被除数有一个数是负数，结果为负数； return negative == 1 ? -result : result; } private int divideCore(int dividend, int divisor) { int result = 0; while (dividend <= divisor) { int value = divisor; int quotient = 1; //0xc0000000为-2^30，避免溢出，如果被除数小于除数的2倍切除数不小于-2^30 while (value >= 0xc0000000 && dividend<= value + value) { //商和除数翻倍 quotient += quotient; value += value; } result += quotient; dividend -= value; } return result; }
四、测试
divide(15, 7); //2 divide(-99, -1);//99 divide(100, -6);//-16 divide(Integer.MIN_VALUE, -1);//2147483647
