剑指 Offer II 001. 整数除法

此题与LeetCode主站的 29. 两数相除相同

题目描述

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

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

回顾JavaScript中的数字类型

不像别的语言数字分整数和浮点数，在JavaScript中只有一个数字类型。它是一个双精度的64位的number。Number 类型使用IEEE 754格式表示整数和浮点值。

由内置数字类型表示的整数限制最大值是 $2^{53} - 1$ 用Number.MAX_SAFE_INTEGER来表示；最小值是 $2^{53} + 1$ Number.MIN_SAFE_INTEGER。

Number.MAX_SAFE_INTEGER === 9007199254740991
Number.MIN_SAFE_INTEGER === -9007199254740991

在这种情况下，安全性指的是该值不能是存在舍入（round）误差的结果。

这些不安全的值在 +1或者-1（舍入）之后，会远离安全的值。任何加法或减法都会导致结果的舍入。

let a = Number.MAX_SAFE_INTEGER
console.log(a + 1 === a + 2) // true

let b = Number.MIN_SAFE_INTEGER
console.log(b - 1 === b - 2) // true

为了检查是否安全，可以使用ES6的 Number.isSafeInteger。

Number.isSafeInteger(a) // true
Number.isSafeInteger(a + 1) // false

分析（朴素解法）

这题限制我们不能使用 *、/、% 运算符，所以比较容易想到的就是使用减法来模拟除法

要计算 a/b，可以使用 a-b 得到结果与 b 进行判断，比 b 大就继续减，比 b 小就停止操作，计算减的次数就是所求的商

例如计算 9/2： ① 9-2=7>2 ② 7-2=5>2 ③ 5-2=3>2 ④ 3-2=1<2 所以商是4

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var divide = function(a, b) {
    let result = 0
    while(a >= b){
        a -= b
        result++
    }
    return result
};

考虑正负问题

上述讨论假设被除数和除数都是正整数。如果有负数则可以将它们先转换成正数，计算正数的除法之后再根据需要调整商的正负号。

由于题目要求不能使用乘法，所以我们使用异或操作符^来判断结果的正负符号sign

var divide = function(a, b) {

    let sign = (a>0) ^ (b>0) // 同（正）0 异（负）1

    a = a > 0 ? a : -a
    b = b > 0 ? b : -b

    let result = 0
    while(a >= b){
        a -= b
        result++
    }
    
    return sign ? -result : result
};

我们还没有考虑溢出问题，因为题目要求 假设我们的环境只能存储 32 位有符号整数

考虑溢出问题

对于32位的整数而言，最小的整数是 $2^{31}$ ，最大的整数是 $2^{31}-1$ 。

由于是整数的除法并且除数不等于0，因此商的绝对值一定小于或等于被除数的绝对值。因此，int型整数的除法只有一种情况会导致溢出：即 $2^{31}$ / $? 1$ 。这是因为最大的正数为 $2^{31} - 1$ ，如果将 $2^{31}$ 转换为正数则会导致溢出，即 $2^{31}$ 超出了正数的范围。

var divide = function(a, b) {
    // 解决溢出问题
    if(a === -(2**31) && b === -1) return 2**31-1

    let sign = (a>0) ^ (b>0) // 同（正）0 异（负）1

    a = a > 0 ? a : -a
    b = b > 0 ? b : -b

    let result = 0
    while(a >= b){
        a -= b
        result++
    }
    
    return sign ? -result : result
};

性能优化

上面这种很直观的解法存在一个问题：当被除数很大但除数很小时，减法操作执行的次数会很多。
如果被除数是N，那么这种解法的时间复杂度为O(N)，所以我们需要对这种解法进行优化。我们要将O(N)的时间复杂度优化到O(logN)

可以将上述解法稍做调整。当被除数大于除数时，继续比较判断被除数是否大于除数的2倍，如果是，则继续判断被除数是否大于除数的4倍、8倍等。

如果被除数最多大于除数的 $2^k$ 倍，那么将被除数减去除数的 $2^k$ 倍，然后将剩余的被除数重复前面的步骤。

由于每次将除数翻倍，因此优化后的时间复杂度是O(logN)。

下面以15/2为例：

$15$ 大于 $2$ ，也大于 $2*2^1=4$ ，还大于 $2*2^2=8$ ，但小于 $2*2^3=16$ 。将 $15$ 减去 $2*2^2=8$ ，剩 $7$ 。由于减去的是除数的 $2^2=4$ 倍，减去这部分对应的商是4
接下来对剩余的 $7$ 和除数 $2$ 进行比较， $7$ 大于 $2$ ，大于 $2 ? 2 = 4$ ，但小于 $2*2^2=8$ ，于是将 $7$ 减去 $4$ ，还剩余 $3$ 。这次减去的是除数 $2$ 的 $2$ 倍，对应的商是2
然后对剩余的 $3$ 和除数 $2$ 进行比较， $3$ 大于 $2$ ，但 $2 ? 2 = 4$ ，于是将 $3$ 减去 $2$ ，还剩余 $1$ 。这一次减去的是除数的 $1$ 倍，对应的商是1
最后剩余的数字是 $1$ ，比除数 $2$ 小，不能再减去除数了
于是15/2的商是4+2+1，即7

题解

下面用代码实现，由于题目要求不能使用 * ，所以这里使用加法代替乘法

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var divide = function(a, b) {
    // 解决溢出问题
    if(a === -(2**31) && b === -1) return 2**31-1

    let sign = (a>0) ^ (b>0) // 同（正）0 异（负）1

    a = a > 0 ? a : -a
    b = b > 0 ? b : -b

    let result = 0

    while(a >= b){

        let value = b
        let k = 1

        while(value >= -(2**30) && a >= value + value){
            k += k
            value += value
        }

        result += k
        a -= value
    }

    return sign ? -result : result
};