剑指 Offer ll 001 整数除法

向右看齐 2024-03-27 09:22 60阅读 0赞

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

注意：

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

示例 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

相关知识点：

1.位运算：

同位与^：同则0，异则1；例 0^0 = 0 1^0 = 1 false^false=false false^true=true

2.int的最大值

int是四个字节，即32个bit位，其中第一用来存储正负号，其他31位用来存储数据。但在正数上0被归为了正数，所以正数最大值是2^31-1，负数最小值就是2^31

## 方法一：减法代替除法 ##

假设是a = 15, b = 2，则15-2=13,13-2=11........3-2=1最终再无法减(a<=b)就结束。

1.其中考虑符号的情况

*  全为正：符号没影响，直接进行计算
 *  一正一负：这时候要考虑符号情况，但计算过程可以依照全为正数的来计算，因此保留符号，然后对数字进行绝对值后再按照全为正的计算。
    
     *  正常的判断逻辑
     *  通过用位运算来进行性能的优化
 *  全为负：符号没影响，直接进行计算

2.同时也要考虑边界问题

因为int是四个字节，是32个bit位，但最大值和最小值不同；32位最大值：2^31-1=2147483647  
32位最小值：-2^31 =-2147483648

因此将所有数字都取绝对值进行优化，因为正数和负数的操作都一样，但正数的最大值的绝对值比负数的最小值的绝对值小，所以都转化做负数来操作一定不越界

## 方法二：优化，降低时间复杂度每次尝试减去除数的倍数 ##

a = 22，b = 3

22-3\*2 k=1  
22- 3\*2\*2= 10 k=2

22-3\*2\*2\*2< 0 k=4  
a = 10，b = 3

10-3\*2= 4 k=1

10-3\*2\*2< 0 k=2  
a= 4，b = 3 k=1

4-3\*2<0  
a= 1，b= 3

a-b\*2^k ==0 ==>k

class Solution {
        public int divide(int a, int b) {
            //32位最大值：2^31-1=2147483647
            //32位最小值：-2^31 =-2147483648
            //当a取-2147483648，b取-1时，2147483648>2147483647就会出现数组越界的情况
            //但2147483647变为负数就不会
            if(a==Interger.MIN_VALUE&&b == -1)
                return Interger.MAX_VALUE;
    
            //优化前
            //if((a>0&&b<0)||(a<0&&b>0)){
            //    sign=-1;
            //}
    
            
            //优化后，采用位运算
            int sign = (a>0)^(b>0)?-1:1;
    
            //优化前
            //a = Math.abs(a);
            //b = Math.abs(b);
    
            //优化后
            //因为正数和负数的操作都一样，但正数的最大值的绝对值比负数的最小值的绝对值小
            //所以转化做负数来操作一定不越界
            if(a>0) a=-a;
            if(b>0) b=-b;
            int res = 0;
            //都改成负号之后要注意这里的条件符号要变
            while(a<=b){
               int value = b;
            int k = 1;
            // 0xc0000000 是十进制 -2^30 的十六进制的表示
            // 判断 value >= 0xc0000000 的原因：保证 value + value 不会溢出
            // 可以这样判断的原因是：0xc0000000 是最小值 -2^31 的一半，
            // 而 a 的值不可能比 -2^31 还要小，所以 value 不可能比 0xc0000000 小
            // -2^31 / 2 = -2^30
            while (value >= 0xc0000000 && a <= value + value) {
                value += value;
                // 代码优化：如果 k 已经大于最大值的一半的话，那么直接返回最小值
                // 因为这个时候 k += k 的话肯定会大于等于 2147483648 ，这个超过了题目给的范围
                if (k > Integer.MAX_VALUE / 2) {
                    return Integer.MIN_VALUE;
                }
                k += k;
            }
            a -= value;
            res += k;
            }
            return sign=1?res:-res;
        }
    }

参考

[简单易懂Java/C++ /Python/js/go - 整数除法(剑指) - 整数除法 - 力扣（LeetCode）][Java_C_ _Python_js_go - _ - _ - _LeetCode]

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/xoh6Oh  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[Java_C_ _Python_js_go - _ - _ - _LeetCode]: https://leetcode.cn/problems/xoh6Oh/solution/jian-dan-yi-dong-javac-pythonjs-zheng-sh-e8r6/