面试题1：整数除法
题目：输出2个int型整数，它们进行除法计算并返回商，要求不得应用乘号'*'、除号'/'及求余符号'%'。当产生溢出时，返回最大的整数值。假如除数不为0。例如，输出15和2，输入15/2的后果，即7。
- 减法实现除法
被除数顺次减去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 = 2if(a>0) { nagative -= 1}if(b>0) { nagative -= 1}若nagative为1，则为正数
或则利用异或判断
// 1 ^ 1 = 0，0 ^ 0 = 0，1 ^ 0 = 1const sign = (a>0)^(b>0))sign = (a > 0) ^ (b > 0)，为 1 时，表明是正数，为 0 时，表明是负数