两个整数相除

描述

将两个整数相除，要求不使用乘法、除法和 mod 运算符。
如果溢出，返回 2147483647 。

注意事项

整数的顺序将表示为一个字符串。

样例
给定被除数 = 100 ，除数 = 9，返回 11。
考察点
  • 使用移位运算符
  • 处理溢出问题
答案（参考的别人的算法）
int divide(int dividend, int divisor) {
    //注意不要忽略负数的情况，如-10/2 = -5 , -2/10 = 0
    //思路先求|dividend|/|divisor|，不断减去被除数，通过对被除数加倍，而加速求解过程，否则结果会超时
    //当dividend = INT_MAX时，-dividend会溢出，所以用long long
    long a = dividend >= 0 ? dividend : -(long) dividend;
    long b = divisor >= 0 ? divisor : -(long) divisor;

    long result = 0;
    while (a >= b) {
        long c = b;
        //i随着c的加倍而加倍，循环结束条件是除数c加倍到比被除数a大，这时结束循环，使得除数又恢复为初始值b，继续循环
        //c <<= 1 表示c = 2 * c
        for (int i = 0; a >= c; ++i, c <<= 1) {
            a -= c;
            result += 1 << i;//移位运算符优先级较高，1向左移i位即是2^i
        }
    }
    //如果同号则结果为正，异号结果为负，(dividend^divisor) >> 31表示把符号位异或后向右移动31位
    //return ((dividend^divisor) >> 31) ? (-result) : (result);
    if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0))
        result = -result;
    if (result > Integer.MAX_VALUE) {
        return 2147483647;
    } else if (result < Integer.MIN_VALUE) {
        return 2147483647;
    }
    return (int) result;
}