leetcode算法题第29道，难度为medium。从题目描述上来看，这道题考察两数相除的计算，貌似很简单，但如果仔细研究下来，就会发现这道题所考察的知识很综合。

Description

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Note:

  • Both dividend and divisor will be 32-bit signed integers.
  • The divisor will never be 0.
  • Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

来源：leetcode 29 divide to integers

Solution

Approach 1 brute force

使用暴力解法，将被除数减去除数，记录被除数可被减去的次数。这种方法必定能够得到结果，只是耗时很多，提交leetcode的结果为超时。

int divide(int dividend, int divisor) {
    std::int64_t d1 = dividend;
    std::int64_t d2 = divisor;
    // 符号转换
    bool neg = false;
    if (d1 < 0) {
	neg = !neg;
	d1 = -d1;
    }
    if (d2 < 0) {
	neg = !neg;
	d2 = -d2;
    }
    // 这样两个数的符号都是正的了
    int ans = 0;
    while (d1 >= d2) {
	d1 -= d2;
	++ans;
	// overflow
	if (ans < 0) {
	    return 0x7fffffff;
	}
    }
    if (neg) {
	return -ans;
    }
    return ans;
}

对溢出问题的思考
为了防止结果溢出，上面的方法使用了 int64_t 作为中间内容的存储。在解这个问题的过程中，我对整数的存储形式进行了比较，发现了一些比较有趣的现象。

NO. pow hex dec type
1 - 0x0000 0005 5 int32_t
2 - 0xffff fffb -5 int32_t
3 231 0x8000 0000 2147483648 int64_t
4 -231 0x8000 0000 -2147483648 int32_t
5 231 - 1 0x7fff ffff 2147483647 int32_t

从上面的表格中可以看出正负数以及的他们的存储形式的一些特点。

  • 通过比较第1条和第2条信息，可以发现正数和负数的存储是完全不同的。最高bit位代表的是符号位，0表示正数，1表示负数。通过16进制 解析出其10进制形式的步骤为：按位取反再加1。
  • 通过比较第3条和第4条信息，可以发现相同的二进制内容，放在不同宽度的数据上具有不同的数值表示。当然第三条数据的宽度为64bit，其高位都是0，所以略去了，这使其在进行符号判断时为正数。
  • 第5条数据所表示的是宽度为32bit的有符号数所能存储的最大正数值。可以从16进制的表示上来看，如果再加1，则它就会从正数变为负数。
  • 第4条数据所表示的是宽度为32bit的有符号数所能存储的最大负数值。同理，如果再减1，它就会变为正数。有趣的是，最大正数和最小负数只有一步之遥。

Approach 2 bit move

这个答案从leetcode的discuss中找到的，使用位操作的方法完成。
举一个例子，在计算 10/3 时，可以将10分解为 3*21 + 3*20 + 1，而每次向左移位代表着数值上扩大两倍，这样就能够通过移位操作将除数成倍放大。这实际上是借助按位左移的数值特性使用了精简版的乘法操作。

int divide(int dividend, int divisor) {
    if (!divisor || (dividend == INT_MIN && divisor == -1))
	return INT_MAX;
    int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
    long long dvd = labs(dividend);
    long long dvs = labs(divisor);
    int res = 0;
    while (dvd >= dvs) {
	long long temp = dvs, multiple = 1;
	while (dvd >= (temp << 1)) {
	    temp <<= 1;
	    multiple <<= 1;
	}
	dvd -= temp;
	res += multiple;
    }
    return sign == 1 ? res : -res;
}

Approach 3 bit move reversed

这个方法是从leetcode的submission提取出来的sample，是耗时最短的解法之一。
我之前都是以除数为操作对象的，而这个方法使用被除数作为操作对象。这相当于使用从大到小的方向进行除数的搜索。这个解法使用无符号数对中间结果进行存储，这样就不需要提高数据的宽度了。

int divide(int dividend, int divisor) {
    unsigned int a = (dividend >= 0)
	? static_cast<unsigned int>(dividend)
	: (0 - static_cast<unsigned int>(dividend));

    unsigned int b = (divisor >= 0)
	? static_cast<unsigned int>(divisor)
	: (0 - static_cast<unsigned int>(divisor));

    unsigned int n = 0;
    for (unsigned i = a; i >= b; i = i >> 1) {
	++n;
    }
    unsigned int result = 0;
    for (int i = n - 1; i >= 0; --i) {
	if (a >= (b << i)) {
	    result = result | (1 << i);
	    a -= (b << i);
	}
    }
    if ((dividend >= 0) == (divisor >= 0)) {
	return static_cast<int>(min(result, static_cast<unsigned int>(INT_MAX)));
    } else {
	return static_cast<int>(0 - result);
    }
}