关于javascript:算法整数

面试题 1：整数除法

题目：输出 2 个 int 型整数，它们进行除法计算并返回商，要求不得应用乘号 ’*’、除号 ’/’ 及求余符号 ’%’。当产生溢出时，返回最大的整数值。假如除数不为 0。例如，输出 15 和 2，输入 15/ 2 的后果，即 7。

1. 减法实现除法

被除数顺次减去 2

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var divide = function(a, b) {if(a == -2147483648 && b === -1) return 2**31-1
    
    let res = 0
    let nagative = 2
    if(a>0) {
        a = -a
        nagative -= 1
    }

    if(b>0) {
        b = -b
        nagative -= 1
    }
    let val = a
    while(val<=b) {
        val -=b
        res++
    }
    return nagative == 1 ? -res : res
};

工夫复杂度 O(n)

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var divide = function(a, b) {if(a == -2147483648 && b === -1) return 2**31-1
    
    let nagative = 2
    if(a>0) {
        a = -a
        nagative -= 1
    }

    if(b>0) {
        b = -b
        nagative -= 1
    }
    const res = dividecore(a, b)
    return nagative == 1 ? -res : res
};

var dividecore = function(a, b) {
    let result = 0
    while(a<=b) {
        let value = b
        let quotient = 1 
        while(a <= value << 0) {
            quotient += quotient
            value += value
        }
        result += quotient
        a -= value
        
    }
    return  result
}

• 利用位运算

实质上还是用减法

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var divide = function(a, b) {const MAX = Math.pow(2, 31) - 1, MIN = -Math.pow(2, 31)
    if (a == MIN && b == -1) return MAX
    if (a == MIN && b == 1) return MIN

    const sign = (a > 0) ^ (b > 0)
    a = Math.abs(a), b = Math.abs(b)
    let n = 0
    for (let i = 31; i >= 0; i--) {if(a >>> i >= b) {
            a -= b << i
            n += 1 << i
        }
    }
    return sign ? -n : n
};

技巧

• 判断符号为正或正数

 let nagative = 2
if(a>0) {nagative -= 1}

if(b>0) {nagative -= 1}

若 nagative 为 1，则为正数

或则利用异或判断

// 1 ^ 1 = 0，0 ^ 0 = 0，1 ^ 0 = 1
const sign = (a>0)^(b>0))

sign = (a > 0) ^ (b > 0)，为 1 时，表明是正数，为 0 时，表明是负数