剑指 Offer II 001. 整数除法减法&&位运算

最新推荐文章于 2023-12-31 17:32:35 发布

别摸我的键盘

最新推荐文章于 2023-12-31 17:32:35 发布

阅读量548

点赞数

分类专栏：算法 leetcode 文章标签： leetcode 位运算剑指offer

本文链接：https://blog.csdn.net/SpringBoots/article/details/123204146

版权

算法同时被 2 个专栏收录

40 篇文章

订阅专栏

leetcode

35 篇文章

订阅专栏

本文介绍了如何在不允许使用乘除和求余运算符的情况下，通过减法和位运算来计算两个整数的除法结果。文章提供了两种实现方式，一种基于减法，另一种基于位运算，并给出了详细的代码实现。测试用例涵盖了正负数和边界情况，确保了算法的正确性。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

文章目录

1.问题描述

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

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

本题中，如果除法结果溢出，则返回 231 − 1

2.测试用例

示例 1

输入：a = 15, b = 2
输出：7
解释：15/2 = truncate(7.5) = 7

示例2

输入：a = 7, b = -3
输出：-2
解释：7/-3 = truncate(-2.33333..) = -2

示例3

输入：a = 0, b = 1
输出：0

示例4

输入：a = 1, b = 1
输出：1

3.提示

-231 <= a, b <= 231 - 1
b != 0

4.代码

1.减法思路

int res = 0;
//越界问题
if (a == Integer.MIN_VALUE && b == -1) {
    return Integer.MAX_VALUE;
}
//标记负数
boolean tag = (a > 0) ^ (b > 0);
//规避Math.abs Integer.MIN_VALUE 等于他自己问题
if (a > 0) {
    a = -a;
}
if (b > 0) {
    b = -b;
}
//小于
while (a <= b) {
    a -= b;
    res++;
}
return tag ? -res : res;

2.位运算

public int divide2(int a, int b) {
    int res = 0;
    //负数标记
    boolean flag = (a > 0) ^ (b > 0);
    if (a == 1 << 31 && b == -1) {
        return (1 << 31) - 1;
    }
    //忽略正负数
    a = Math.abs(a);
    b = Math.abs(b);
    for (int i = 31; i >= 0; i--) {
        //两个注意点
        //1.b做有符号左移(b << i) 存在溢出问题
        //2.b有可能为负数，( a >>> i) >= b  有可能一直成立
        if ((a >>> i) - b >= 0) {
            a -= (b << i);
            res += (1 << i);
        }
    }
    return flag ? -res : res;
}