题目描述
给你两个整数,被除数 dividend 和除数 divisor。将两数相除,要求 不使用 乘法、除法和取余运算。
整数除法应该向零截断,也就是截去(truncate)其小数部分。例如,8.345 将被截断为 8 ,-2.7335 将被截断至 -2 。
返回被除数 dividend 除以除数 divisor 得到的 商 。
注意:假设我们的环境只能存储 32 位 有符号整数,其数值范围是 $[−2^{31}, 2^{31} − 1]$ 。本题中,如果商 严格大于 $2^{31} − 1$ ,则返回 $2^{31} − 1$ ;如果商 严格小于 $−2^{31}$ ,则返回 $−2^{31}$ 。
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = 3.33333.. ,向零截断后得到 3 。
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = -2.33333.. ,向零截断后得到 -2 。
提示:
- $−2^{31} <= dividend, divisor <= 2^{31} − 1$
- divisor != 0
解决方法
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| class Solution { public: int divide(int dividend, int divisor) { if (dividend == INT_MIN && divisor == -1) { return INT_MAX; } int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1; long long absDividend = llabs(static_cast<long long>(dividend)); long long absDivisor = llabs(static_cast<long long>(divisor)); long long result = 0; while (absDividend >= absDivisor) { long long temp = absDivisor, multiple = 1; while (absDividend >= (temp << 1)) { temp <<= 1; multiple <<= 1; } absDividend -= temp; result += multiple; } result *= sign; return static_cast<int>(std::min(std::max(result, static_cast<long long>(INT_MIN)), static_cast<long long>(INT_MAX))); } };
|
结果
执行用时 : 0 ms, 击败 100.00% 使用 C++ 的用户
内存消耗 : 7.50 MB, 击败 5.02% 使用 C++ 的用户
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| class Solution { public int divide(int dividend, int divisor) { if (dividend == Integer.MIN_VALUE && divisor == -1) { return Integer.MAX_VALUE; } int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1; long absDividend = Math.abs((long)dividend); long absDivisor = Math.abs((long)divisor); long result = 0; while (absDividend >= absDivisor) { long temp = absDivisor, multiple = 1; while (absDividend >= (temp << 1)) { temp <<= 1; multiple <<= 1; } absDividend -= temp; result += multiple; } result *= sign; return (int)Math.min(Math.max(result, (long)Integer.MIN_VALUE), (long)Integer.MAX_VALUE); } }
|
结果
执行用时 : 1 ms, 击败 72.66% 使用 Java 的用户
内存消耗 : 39.83 MB, 击败 20.23% 使用 Java 的用户
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| class Solution(object): def divide(self, dividend, divisor): """ :type dividend: int :type divisor: int :rtype: int """ if dividend == 0: return 0 INT_MAX = 2**31 - 1 INT_MIN = -2**31 sign = -1 if (dividend < 0) ^ (divisor < 0) else 1 abs_dividend = abs(dividend) abs_divisor = abs(divisor) quotient = 0 while abs_dividend >= abs_divisor: temp, multiple = abs_divisor, 1 while abs_dividend >= (temp << 1): temp <<= 1 multiple <<= 1 abs_dividend -= temp quotient += multiple result = sign * quotient return min(max(result, INT_MIN), INT_MAX)
|
结果
执行用时 : 19 ms, 击败 89.54% 使用 Python 的用户
内存消耗 : 11.37 MB, 击败 92.81% 使用 Python 的用户
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution: def divide(self, dividend: int, divisor: int) -> int: if dividend == 0: return 0 INT_MAX = 2**31 - 1 INT_MIN = -2**31 sign = -1 if (dividend < 0) ^ (divisor < 0) else 1 abs_dividend = abs(dividend) abs_divisor = abs(divisor) quotient = 0 while abs_dividend >= abs_divisor: temp, multiple = abs_divisor, 1 while abs_dividend >= (temp << 1): temp <<= 1 multiple <<= 1 abs_dividend -= temp quotient += multiple result = sign * quotient return min(max(result, INT_MIN), INT_MAX)
|
结果
执行用时 : 30 ms, 击败 98.48% 使用 Python3 的用户
内存消耗 : 16.41 MB, 击败 32.61% 使用 Python3 的用户
C
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| int divide(int dividend, int divisor) { if (dividend == 0) { return 0; } int MAX_INT = INT_MAX; int MIN_INT = INT_MIN; int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1; long long absDividend = labs((long long)dividend); long long absDivisor = labs((long long)divisor); long long quotient = 0; while (absDividend >= absDivisor) { long long temp = absDivisor, multiple = 1; while (absDividend >= (temp << 1)) { temp <<= 1; multiple <<= 1; } absDividend -= temp; quotient += multiple; } long long result = sign * quotient; return (int)fmin(fmax(result, (long long)MIN_INT), (long long)MAX_INT); }
|
结果
执行用时 : 0 ms, 击败 100.00% 使用 C 的用户
内存消耗 : 5.20 MB, 击败 98.80% 使用 C 的用户
C#
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| public class Solution { public int Divide(int dividend, int divisor) { if (dividend == 0) { return 0; } int MAX_INT = int.MaxValue; int MIN_INT = int.MinValue; int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1; long absDividend = Math.Abs((long)dividend); long absDivisor = Math.Abs((long)divisor); long quotient = 0; while (absDividend >= absDivisor) { long temp = absDivisor, multiple = 1; while (absDividend >= (temp << 1)) { temp <<= 1; multiple <<= 1; } absDividend -= temp; quotient += multiple; } long result = sign * quotient; return (int)Math.Min(Math.Max(result, (long)MIN_INT), (long)MAX_INT); } }
|
结果
执行用时 : 24 ms, 击败 70.97% 使用 C# 的用户
内存消耗 : 26.63 MB, 击败 12.90% 使用 C# 的用户
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
|
var divide = function(dividend, divisor) { let sign = ''; dividend > 0 ? (dividend = -dividend) : (sign = '-'); divisor > 0 ? (divisor = -divisor) : (sign = sign ? '' : '-'); let quotient = 0; while (dividend) { let i = 0; while ( i <= 31 && divisor >= (-1 << (31 - i)) && divisor << i >= dividend && ++i ) {} if (i === 0) { break; } dividend = dividend - (divisor << --i); quotient += 2 ** i; } return parseInt(sign + (!sign && quotient >= 2147483648 ? 2147483647 : quotient)); };
|
结果
执行用时 : 74 ms, 击败 64.44% 使用 JavaScript 的用户
内存消耗 : 53.24 MB, 击败 5.34% 使用 JavaScript 的用户
TypeScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| function divide(a: number, b: number): number { const sign: number = (Number(a > 0) ^ Number(b > 0)) ? -1 : 1; let result: number = 0; if (a === 2 ** 31 - 1 && b === 1) { return 2 ** 31 - 1; } if (a === -(2 ** 31) && b === 1) { return -(2 ** 31); } if (a === -(2 ** 31) && b === -1) { return 2 ** 31 - 1; } if (a === 2 ** 31 - 1 && b === -1) { return -(2 ** 31 - 1); } a = Math.abs(a); b = Math.abs(b); for (let x = 31; x >= 0; x--) { if ((a >>> x) >= b) { a -= (b << x); result += (1 << x); } } return sign === 1 ? result : -result; }
|
结果
执行用时 : 98 ms, 击败 7.81% 使用 TypeScript 的用户
内存消耗 : 53.46 MB, 击败 6.25% 使用 TypeScript 的用户
PHP
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| class Solution {
function divide($dividend, $divisor) { $INT_MAX = pow(2, 31) - 1; $INT_MIN = pow(-2, 31); if ($dividend === 0) { return 0; } $sign = ($dividend > 0) ^ ($divisor > 0) ? -1 : 1; $dividend = abs($dividend); $divisor = abs($divisor); $quotient = 0; while ($dividend >= $divisor) { $tempDivisor = $divisor; $multiple = 1; while ($dividend >= $tempDivisor << 1) { $tempDivisor <<= 1; $multiple <<= 1; } $dividend -= $tempDivisor; $quotient += $multiple; } $result = $sign * $quotient; if ($result > $INT_MAX) { return $INT_MAX; } elseif ($result < $INT_MIN) { return $INT_MIN; } return $result; } }
|
结果
执行用时 : 12 ms, 击败 40.00% 使用 PHP 的用户
内存消耗 : 19.82 MB, 击败 -% 使用 PHP 的用户
Swift
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| class Solution { func divide(_ dividend: Int, _ divisor: Int) -> Int { let INT_MAX = Int32.max let INT_MIN = Int32.min if dividend == 0 { return 0 } let sign = (dividend > 0) != (divisor > 0) ? -1 : 1 var dividend = abs(dividend) let divisor = abs(divisor) var quotient = 0 while dividend >= divisor { var tempDivisor = divisor var multiple = 1 while dividend >= tempDivisor << 1 { tempDivisor <<= 1 multiple <<= 1 } dividend -= tempDivisor quotient += multiple } let result = sign * quotient if result > Int32(INT_MAX) { return Int(INT_MAX) } else if result < Int32(INT_MIN) { return Int(INT_MIN) } return result } }
|
结果
执行用时 : 3 ms, 击败 90.00% 使用 Swift 的用户
内存消耗 : 15.00 MB, 击败 10.00% 使用 Swift 的用户
Kotlin
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| class Solution { fun divide(dividend: Int, divisor: Int): Int { val INT_MAX = Int.MAX_VALUE val INT_MIN = Int.MIN_VALUE if (dividend == 0) { return 0 } val sign = (dividend > 0) xor (divisor > 0) var dividend = Math.abs(dividend.toLong()) val divisor = Math.abs(divisor.toLong()) var quotient = 0L while (dividend >= divisor) { var tempDivisor = divisor var multiple = 1L while (dividend >= tempDivisor shl 1) { tempDivisor = tempDivisor shl 1 multiple = multiple shl 1 } dividend -= tempDivisor quotient += multiple } val result = if (sign) -quotient else quotient if (result > INT_MAX) { return INT_MAX } else if (result < INT_MIN) { return INT_MIN } return result.toInt() } }
|
结果
执行用时 : 155 ms, 击败 40.00% 使用 Kotlin 的用户
内存消耗 : 33.58 MB, 击败 8.00% 使用 Kotlin 的用户
Dart
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| class Solution { int divide(int dividend, int divisor) { const int INT_MAX = 2147483647; const int INT_MIN = -2147483648; if (dividend == 0) { return 0; } bool isNegative = (dividend > 0) ^ (divisor > 0); int longDividend = dividend.abs(); int longDivisor = divisor.abs(); int quotient = 0; while (longDividend >= longDivisor) { int tempDivisor = longDivisor; int multiple = 1; while (longDividend >= tempDivisor << 1) { tempDivisor <<= 1; multiple <<= 1; } longDividend -= tempDivisor; quotient += multiple; } int result = isNegative ? -quotient : quotient; if (result > INT_MAX) { return INT_MAX; } else if (result < INT_MIN) { return INT_MIN; } return result; } }
|
结果
执行用时 : 327 ms, 击败 50.00% 使用 Dart 的用户
内存消耗 : 147.92 MB, 击败 50.00% 使用 Dart 的用户
Go
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| func divide(dividend int, divisor int) int { const INT_MAX = int(^uint32(0) >> 1) const INT_MIN = ^INT_MAX if dividend == 0 { return 0 } isNegative := (dividend > 0) != (divisor > 0) longDividend := abs(dividend) longDivisor := abs(divisor) quotient := 0 for longDividend >= longDivisor { tempDivisor := longDivisor multiple := 1 for longDividend >= tempDivisor<<1 { tempDivisor <<= 1 multiple <<= 1 } longDividend -= tempDivisor quotient += multiple } result := quotient if isNegative { result = -quotient } if result > INT_MAX { return INT_MAX } else if result < INT_MIN { return INT_MIN } return result } func abs(n int) int { if n < 0 { return -n } return n }
|
结果
执行用时 : 0 ms, 击败 100.00% 使用 Go 的用户
内存消耗 : 2.20 MB, 击败 69.90% 使用 Go 的用户
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
|
def divide(dividend, divisor) int_max = (2**31 - 1) int_min = -(2**31) return 0 if dividend == 0 is_negative = (dividend > 0) ^ (divisor > 0) long_dividend = dividend.abs long_divisor = divisor.abs quotient = 0 while long_dividend >= long_divisor temp_divisor = long_divisor multiple = 1 while long_dividend >= temp_divisor << 1 temp_divisor <<= 1 multiple <<= 1 end long_dividend -= temp_divisor quotient += multiple end result = is_negative ? -quotient : quotient if result > int_max return int_max elsif result < int_min return int_min end result end
|
结果
执行用时 : 59 ms, 击败 75.00% 使用 Ruby 的用户
内存消耗 : 206.44 MB, 击败 -% 使用 Ruby 的用户
Scala
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| object Solution { def divide(dividend: Int, divisor: Int): Int = { val INT_MAX = Int.MaxValue val INT_MIN = Int.MinValue if (dividend == INT_MIN) { if (divisor == 1) return INT_MIN else if (divisor == -1) return INT_MAX } if (divisor == 0) return 0 var rev = false var dividendVar = dividend var divisorVar = divisor if (dividend > 0) { dividendVar = -dividend rev = !rev } if (divisor > 0) { divisorVar = -divisor rev = !rev } var left = 1 var right = INT_MAX var ans = 0 while (left <= right) { val mid = left + ((right - left) >> 1) val check = quickAdd(divisorVar, mid, dividendVar) if (check) { ans = mid if (mid == INT_MAX) { return if (rev) -ans else ans } left = mid + 1 } else { right = mid - 1 } } if (rev) -ans else ans } def quickAdd(y: Int, z: Int, x: Int): Boolean = { var result = 0 var add = y var zVar = z while (zVar != 0) { if ((zVar & 1) != 0) { if (result < x - add) { return false } result += add } if (zVar != 1) { if (add < x - add) { return false } add += add } zVar >>= 1 } true } }
|
结果
执行用时 : 440 ms, 击败 100.00% 使用 Scala 的用户
内存消耗 : 51.39 MB, 击败 100.00% 使用 Scala 的用户
Rust
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
| impl Solution { pub fn divide(dividend: i32, divisor: i32) -> i32 { const INT_MAX: i32 = i32::MAX; const INT_MIN: i32 = i32::MIN; if dividend == INT_MIN { if divisor == 1 { return INT_MIN; } else if divisor == -1 { return INT_MAX; } } if divisor == 0 { return 0; } let mut rev = false; let mut dividend_var = dividend; let mut divisor_var = divisor; if dividend > 0 { dividend_var = -dividend; rev = !rev; } if divisor > 0 { divisor_var = -divisor; rev = !rev; } let mut left = 1; let mut right = INT_MAX; let mut ans = 0; while left <= right { let mid = left + ((right - left) >> 1); let check = Solution::quick_add(divisor_var, mid, dividend_var); if check { ans = mid; if mid == INT_MAX { return if rev { -ans } else { ans }; } left = mid + 1; } else { right = mid - 1; } } if rev { -ans } else { ans } } fn quick_add(y: i32, z: i32, x: i32) -> bool { let mut result = 0; let mut add = y; let mut z_var = z; while z_var != 0 { if z_var & 1 != 0 { if result < x - add { return false; } result += add; } if z_var != 1 { if add < x - add { return false; } add += add; } z_var >>= 1; } true } }
|
结果
执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户
内存消耗 : 2.14 MB, 击败 18.92% 使用 Rust 的用户
Racket
暂时未解决
结果
执行用时 : ms, 击败 % 使用 Racket 的用户
内存消耗 : MB, 击败 % 使用 Racket 的用户
Erlang
暂时未解决
结果
执行用时 : ms, 击败 % 使用 Erlang 的用户
内存消耗 : MB, 击败 % 使用 Erlang 的用户
Elixir
暂时未解决
结果
执行用时 : ms, 击败 % 使用 Elixir 的用户
内存消耗 : MB, 击败 % 使用 Elixir 的用户