剑指Offer II 001.整数除法

题目描述

整数除法：给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

注意：

• 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
• 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31−1]。本题中，如果除法结果溢出，则返回 2^31−1。

解题分析

1. 不使用 * 、%、/。
   a/b=c 可转化成 a=b*c，然后通过快速乘算法运算。快速加过程中要小心加结果溢出，所以当加得结果大于a时及时停止。
2. 截去小数部分。
   运用二分查找，先取c=a，然后折半取值，直到 0<=a-b*c<b，找到合适的C。
3. 数值范围。
   分情况讨论32位有符号数由补码表示，取值范围在[−2^31, 2^31−1]，可能的取值分类如下：
   *溢出：a=−2^31，b=-1，此时 2^31−1；
   *若 b=INT_MIN，且 a<INT_MIN ，则 c=0；
   *若 b=INT_MIN，且 a=INT_MIN，则 c=1；
   *若 b=1，则 c=a；
   *若 b=-1，则 c=-a；
   *若 a-b * c>b，则c估值过小，向上折半取值；
   *若 a-b * c<0，则c估值过大，向下折半取值。
4. 化简运算。
   直接取除数和被除数的负数进行运算，能兼顾所有数据且不会导致溢出。如果两数同符号，结果不变；如果两数符号相反，结果加上负号。

Python代码

分类讨论

#溢出
if a == INT_MIN and b == -1:
    c = INT_MAX

#除数绝对值大于或等于被除数绝对值
elif abs(b) > abs(a):
    c = 0
elif abs(b) == abs(a):
    if a != b:
        c = -1
    elif a == b:
        c = 1 
    
#被除数等于1或-1
elif b == 1:
    c = a
elif b == -1:
    c = -a

#其他情况下用二分查找
else:
    left = INT_MIN
    right = -1
    mid = 0
    c = 0
    while left <= right:
        mid = right + ((left - right) >> 1 )
        ans = quickMult (-abs(a), -abs(b), abs(mid)) 
        if ans == 1: # c过大，向右折半
            left = mid + 1
        elif abs(a) - abs(ans) >= abs(b): # c过小，向左折半
            right = mid - 1
        elif abs(a) - abs(ans) < abs(b): # c合适，输出
            if (a < 0 and b > 0) or (a > 0 and b < 0):
                c = mid
            else:
                c = -mid
            break

快速乘算法

def quickMult( a, b, c ):#小心溢出
    ans = 0
    while c:
        if b < a: # b已经超过a，结果过大向左折半
            return 1
        if c & 1:
            if a - ans > b :# b*c > a 结果过大向左折半
                return 1
            ans += b
        b += b
        c >>= 1
    return ans