剑指 Offer II 001. 整数除法

剑指 Offer II 001. 整数除法
剑指 Offer II 001. 整数除法
力扣上的剑指offer第一道“简单”题,提交了n遍心态已崩,下面代码是题解中的代码
代码如下:
(使用减法代替除法,这里采用2倍增的方法减小复杂度)

class Solution {
public:
    int divide(int a, int b) {
    if (a == INT_MIN && b == -1) return INT_MAX;
//注意一种特殊情况:当a为最小值b为-1的时候,两者相除就会超出最大值,此时除法结果溢出
    int sign = (a > 0) ^ (b > 0) ? -1 : 1;
//使用异或的方法判断除法结果的正负
    if (a > 0) a = -a;
    if (b > 0) b = -b;
//因为将 -2147483648 转成正数会越界,但是将 2147483647 转成负数,则不会
// 所以,我们将 a 和 b 都转成负数
    unsigned int res = 0;
    while (a <= b) {
        int value = b;
        // 如果不用 unsigned 的话,那么当 a = -2147483648, b = 1 的时候,k 会越界
        unsigned int k = 1;
        // 0xc0000000 是十进制 -2^30 的十六进制的表示
        // 判断 value >= 0xc0000000 的原因:保证 value + value 不会溢出
        // 可以这样判断的原因是:0xc0000000 是最小值 -2^31 的一半,
        // 而 a 的值不可能比 -2^31 还要小,所以 value 不可能比 0xc0000000 小
        while (value >= 0xc0000000 && a <= value + value) {
            k += k;
            value += value;
        }
        a -= value;
        res += k;
    }

    // bug 修复:因为不能使用乘号,所以将乘号换成三目运算符
    return sign == 1 ? res : -res;
}
};

  • unsigned:int分为无符号unsigned和signed有符号两种类型,默认是有符号的,二者的区别是无符号类型能保存两倍有符号类型的数据,所以k使用无符号类型,避免导致除法结果溢出。
    剑指 Offer II 001. 整数除法
    思路:对照上面的图片,value+=value,此时k+=k,当被除数大于等于value的时候就一直进行此循环,当小于时,就退出循环,注意外面还有一层大循环,就是当被除数>除数的时候就一直让被除数-除数,此时k=1。最后k就是除法结果。注意一种特殊情况除法结果溢出,还要注意避免其他结果除法溢出

采用位运算:
代码如下:

int divide(int a, int b) {
    if (a == INT_MIN && b == -1) return INT_MAX;

    int sign = (a > 0) ^ (b > 0) ? -1 : 1;
//转换成正数要定义为unsigned类型否则可能会导致溢出
    unsigned int ua = abs(a);
    unsigned int ub = abs(b);
    unsigned int res = 0;
//从int存储最大的数开始,即从2的31次方开始
    for (int i = 31; i >= 0; i--) {
        if ((ua >> i) >= ub) {
            ua = ua - (ub << i);
            res += 1 << i;
        }
    }
    // bug 修复:因为不能使用乘号,所以将乘号换成三目运算符
    return sign == 1 ? res : -res;
}
  • 左移右移:A<<B代表A*2的B次方;A>>B代表A/2的B次方
    剑指 Offer II 001. 整数除法
上一篇:2021-10-25如何下载.001的压缩文件


下一篇:Java基础_61.数组_内存分配