29两数相除

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

提示：

被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返+ 回 231 − 1。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/divide-two-integers 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1

位运算（转化为正数，并且用long防止溢出）
执行用时：0 ms
内存消耗：5.1 MB

int divide(int dividend, int divisor)
{
    if (divisor == 0)
        return 0; //error
    if (dividend == -2147483648 && divisor == -1)
        return 2147483647;
    long a = dividend > 0 ? dividend : (dividend == -2147483648 ? 2147483648 : -dividend);
    long b = divisor > 0 ? divisor : (divisor == -2147483648 ? 2147483648 : -divisor);
    long div = b;
    long result = 0; // result = a / b = dividend / divisor
    int sign = ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) ? 0 : 1;

    while (b <= a)
        b <<= 1;
    b >>= 1;
    while (b >= div)
    {
        result <<= 1;
        if (a >= b)
        {
            a = a - b;
            result++;
        }
        b >>= 1;
    }
    if (sign)
        result = -result;
    return (int)result;
}