题目：
输入两个 int 型整数（整数范围为 -2^31 ~ 2^31 - 1?），它们进行除法计算并返回商，要求不得使用乘号 '*'、除号 '/' 及求余符号 '%'。当发生溢出时，返回最大的整数值。假设除数不为 0。例如，输入 15 和 2，输出 15 / 2 的结果，即 7。
分析：
这个题目限制我们不能使用乘号和除号进行运算。一个直观的解法是基于减法实现除法。例如，为了求得 15 / 2 的商，可以不断地从 15 里减去 2，当减去 7 个 2 之后余数是 1，此时不能减去更多的 2，因此 15 / 2 的商是 7。我们可以用一个循环实现这个过程。
但这个直观的解法存在一个问题。当被除数很大但除数很小时，减法操作执行的次数会很多。例如，求 (2^31 - 1) / 1，减 1 的操作将执行 2^31 - 1 次，需要很长时间。如果被除数是 n，那么这种解法的时间复杂度为 O(n)。我们需要对这种解法进行优化。
可以将上述解法稍作调整。当被除数大于除数时，判断被除数是否大于除数的 2 倍，如果是，则继续判断被除数是否大于除数的 4 倍、8 倍等。如果被除数最多大于除数的 2^k 倍，那么将被除数减去除数的 2^k 倍，然后将剩余的被除数重复前面的步骤。由于每次将除数翻倍，因此优化后的时间复杂度为 O(logn)。
下面以 15 / 2 为例讨论计算的过程。15 大于 2，也大于 2 的 2 倍（即 4），还大于 2 的 4 倍（即 8），但小于 2 的 8 倍（即 16），于是先将 15 减去 8，还剩余 7。由于减去的是除数的 4 倍，减去这部分对应的商是 4。接下来对剩余的 7 和除数 2 进行比较，7 大于 2，大于 2 的 2 倍（即 4），但小于 2 的 4 倍（即 8），于是将 7 减去 4，还剩余 3。这一次减去的是除数的 2 倍，对应的商是 2。然后对剩余的 3 和除数 2 进行比较，3 大于 2，但小于 2 的 2 倍（即 4），于是将 3 减去 2，还剩余 1。这一次减去的是除数的 1 倍，对应的商是 1。最后剩余的数字是 1，比除数小，不能再减去除数了。于是 15 / 2 的商是 4 + 2 + 1，即 7。
上述讨论假设被除数和除数都是正整数，如果有负数则可以将它们转化成正数，计算正数的除法之后再根据需要调整商的正负号。例如，如果计算 -15 / 2，则可以先计算 15 / 2，得到的商是 7。由于被除数和除数中有一个负数，因此商应该是负数，于是商应该是 -7。
将负数转换成正数存在一个小问题。对于 32 位的整数而言，最小的整数是 -2^31，最大的整数是 2^31 - 1，因此，如果将 -2^31 转换为正数则会导致溢出。由于将任意正数转换为负数都不会溢出，因此可以先将正数都转换成负数，用前面优化之后的减法计算两个负数的除法，然后根据需要调整商的正负号。
最后讨论可能的溢出。由于是整数的除法并且除法不等于 0，因此商的绝对值一定小于或等于被除数的绝对值。因此，int 型整数的除法只有一种情况会导致溢出，即 (-2^31) / (-1)，这是因为最大的正数为 2^31 - 1，2^31 超出了正数的范围。
代码实现：
int divide(int dividend, int divisor)
{
if (dividend == INT_MIN)
? {
? ? ? ?if (divisor == -1)
? ? ? ? ? ?return INT_MAX;
? ? ? ?
? ? ? ?if (divisor == 1)
? ? ? ? ? ?return INT_MIN;
? }
?
int negNum = 2;
if (dividend > 0)
{
--negNum;
dividend = -dividend;
}
if (divisor > 0)
{
--negNum;
divisor = -divisor;
}
?
// 计算两个负数的除法
int total = 0;
while (dividend <= divisor)
{
int tmp = divisor;
int quotient = 1;
? ? ? ?// 0xc0000000 即 -2^30，是 -2^31 的一半
? ? ? ?// 注意：不得使用乘号 *
while (tmp >= 0xc0000000 && dividend <= tmp + tmp) ?
{
quotient = quotient + quotient;
tmp = tmp + tmp;
}
dividend -= tmp;
total += quotient;
}
?
return negNum == 1 ? -total : total;
}