29. Divide Two Integers
給定兩個整數 dividend 和 divisor，在不使用乘法、除法和模運算符的情況下進行整數除法。
整數除法應該向零截斷，這意味著丟失其小數部分。例如，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。
Python
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
# Handle edge cases
if dividend == 0:
return 0
if divisor == 0:
raise ValueError("Division by zero is not allowed.")
# Determine the sign of the result
negative = (dividend < 0) != (divisor < 0)
# Work with positive values
dividend, divisor = abs(dividend), abs(divisor)
# Initialize the quotient
quotient = 0
# Subtract divisor from dividend until dividend is less than divisor
while dividend >= divisor:
temp_divisor, num_divisors = divisor, 1
while dividend >= (temp_divisor << 1):
temp_divisor <<= 1
num_divisors <<= 1
dividend -= temp_divisor
quotient += num_divisors
# Apply the sign to the quotient
if negative:
quotient = -quotient
# Clamp the result to the 32-bit signed integer range
INT_MAX = 2**31 - 1
INT_MIN = -2**31
if quotient < INT_MIN:
return INT_MIN
if quotient > INT_MAX:
return INT_MAX
return quotient
16.44MB, 42ms
C++
#include <climits>
#include <cstdlib> // For abs()
#include <stdexcept> // For invalid_argument
class Solution {
public:
int divide(int dividend, int divisor) {
// Handle edge cases
if (dividend == 0) {
return 0;
}
if (divisor == 0) {
throw std::invalid_argument("Division by zero is not allowed.");
}
// Determine the sign of the result
bool negative = (dividend < 0) != (divisor < 0);
// Work with positive values
long long abs_dividend = std::abs(static_cast<long long>(dividend));
long long abs_divisor = std::abs(static_cast<long long>(divisor));
// Initialize the quotient
long long quotient = 0;
// Subtract divisor from dividend until dividend is less than divisor
while (abs_dividend >= abs_divisor) {
long long temp_divisor = abs_divisor, num_divisors = 1;
while (abs_dividend >= (temp_divisor << 1)) {
temp_divisor <<= 1;
num_divisors <<= 1;
}
abs_dividend -= temp_divisor;
quotient += num_divisors;
}
// Apply the sign to the quotient
if (negative) {
quotient = -quotient;
}
// Clamp the result to the 32-bit signed integer range
if (quotient < INT_MIN) {
return INT_MIN;
}
if (quotient > INT_MAX) {
return INT_MAX;
}
return quotient;
}
};
7.49MB, 0ms
Javascript
/**
* @param {number} dividend
* @param {number} divisor
* @return {number}
*/
var divide = function(dividend, divisor) {
// Handle edge cases
if (dividend === 0) return 0;
if (divisor === 0) throw new Error("Division by zero is not allowed.");
// Determine the sign of the result
const negative = (dividend < 0) !== (divisor < 0);
// Work with positive values
let absDividend = Math.abs(dividend);
let absDivisor = Math.abs(divisor);
// Initialize the quotient
let quotient = 0;
// Subtract divisor from dividend until dividend is less than divisor
while (absDividend >= absDivisor) {
let tempDivisor = absDivisor, numDivisors = 1;
while (absDividend >= (tempDivisor << 1)) {
tempDivisor <<= 1;
numDivisors <<= 1;
}
absDividend -= tempDivisor;
quotient += numDivisors;
}
// Apply the sign to the quotient
if (negative) quotient = -quotient;
// Clamp the result to the 32-bit signed integer range
const INT_MAX = 2 ** 31 - 1;
const INT_MIN = -(2 ** 31);
if (quotient < INT_MIN) return INT_MIN;
if (quotient > INT_MAX) return INT_MAX;
return quotient;
};
52.47MB, 62ms
