剑指offer专项突击版

第一章 整数

剑指 Offer II 001. 整数除法

难度简单37

给定两个整数 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

解题思路

​ 一切运算的核心其实都是加法，减法也是加法的运算，题目要求不能使用乘法，除法和取余运算，所以回归本质，比如15/2，其实就是看15可以容纳多少个2，当我们一个一个加的时候，当加到14的时候发现，再加一个就超过了15，所以15/2的商就是7

​ 优化思路: 我们发现这样一个一个得加或者减太费时间了，比如一个数为2^{31-1,除数为1，那么要循环2}31-1次，效率太低，实际上可以通过倍增法来进行加速，原理就是通过每次把除数增加为原来的两倍，同时记录相对于原来的除数增加了多少倍，最后当除数比被除数大的时候退出循环，结果就是商。见代码

考虑情况

• 负数的情况，其实就是判断最后符号的问题，联系我们刚开始学负数的时候，只需要判断最后的符号就行了，代入到程序里面，就是使用一个flag，来记录其符号情况，在最终的运算结果添加判断
• 边界情况，由于只能存储[-2^31,2^31-1]有符号数，之所以这个范围要明白什么是有符号整数，有符号数表示有个标志位，正数为0，负数为1；那么在这里要考虑越界情况只有最后结果为正数的情况，
• 为什么要转为负数来计算？因为如果是-2^31,转为正数计算就超出范围了

实际代码

class Solution {
        public int divide(int a, int b) {
        int max_value = Integer.MAX_VALUE;
        // 处理边界情况,正数越界的情况
        if(a == Integer.MIN_VALUE && b == 1) {
            return max_value;
        }
        // 记录符号位
        int flag = 1;
        if((a > 0 && b < 0) || (a < 0 && b > 0)) {
            flag = -1;
        }
        // 把两个数都转成负数，避免转换的时候越界
        if(a > 0) a = -a;
        if(b > 0) b = -b;
        // 另写一个方法处理两个正数除法
        int res = divideTwoNumbers(a, b);
        return flag == 1 ? res: -res;
    }

    private int divideTwoNumbers(int dividend, int divisor) {
        int count = 0;
        while(dividend <= divisor) {
            int value = divisor; // 记录当前叠加后的值
            // 比如第一轮 ： 7/2 当2叠加到4的时候，就不满足条件了，此时7-4 = 3，所以得重新计算包含几个2
            int quotient = 1; // 记录当前翻倍的次数
            while(value >= 0xc0000000 && dividend <= value + value) {
                // 0x0000000表示-2^30;
                quotient+=quotient;
                value+=value;
            }
            count+=quotient;
            dividend-=value;
        }
        return count;
    }
}
}

相关题目