题目：
给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。
注意：
- 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
- 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [
]。本题中，如果除法结果溢出，则返回
解答：
解法一（循环相减）：
当被除数大于除数时，继续比较被除数是否大于除数的2倍，如果是，则继续比较是否大于除数的4倍、8倍等。如果被除数最多大于除数的倍，那么将被除数减去除数的
倍，然后将剩余的被除数重复前面的步骤。
- 由于当前环境仅能存储32 位有符号整数，其数值范围是 [
- 当且仅当被除数为
，除数为-1时结果溢出，因此这种情况单独进行考虑。
- 0x80000000为最小的int型整数，即
。
class Solution {
public int divide(int a, int b) {
//防止结果数据溢出
if (a == 0x80000000 && b == -1) {
return Integer.MAX_VALUE;
}
//确定结果符号，当negative为1时结果为负数，其余情况为正数
int negative = 2;
if (a > 0) {
negative --;
a = -a;
}
if (b > 0) {
negative --;
b = -b;
}
int result = divideCore(a, b);
return negative == 1 ? -result : result;
}
private int divideCore(int dividend, int divisor) {
int result = 0;
while (dividend <= divisor) {
int value = divisor;
int quotient = 1;
while (value >= 0xc0000000 && dividend <= value + value) {
quotient += quotient;
value += value;
}
result += quotient;
dividend -= value;
}
return result;
}
}
解法二（位运算）：
思想与解法一相同，被除数与除数的2倍进行比较，若被除数大于除数的2倍，则按此方法将被除数与除数的4倍、8倍等进行比较，如果被除数最多大于除数的倍，那么将被除数减去除数的
倍，然后将剩余的被除数重复前面的步骤。
- 由于当前环境仅能存储32 位有符号整数，其数值范围是 [
- 当且仅当被除数为
- 在比较被除数与除数的
倍的关系时，为了保证计算过程数据不溢出，使用减法，即
，同时为了保证
结果不溢出，被除数为0的情况需要单独进行考虑。
class Solution {
public int divide(int a, int b) {
//防止结果数据溢出
if (a == 0x80000000 && b == -1) {
return Integer.MAX_VALUE;
}
//防止计算过程中a - divisor数据溢出
if (a == 0) {
return 0;
}
//获取结果符号
boolean positive = (a ^ b) >= 0;
//将a,b分别化为负数形式，防止数据溢出
a = a < 0 ? a : -a;
b = b < 0 ? b : -b;
int quotient = 0;
while (a <= b) {
int divisor = b;
int base = 1;
//使用减法，防止计算过程中数据溢出，等同于a <= 2*divisor
while (a - divisor <= divisor) {
divisor <<= 1;
base <<= 1;
}
quotient += base;
a -= divisor;
}
return positive ? quotient : -quotient;
}
}
