力扣00029.两数相除

发表于 分类于 阅读次数： 本文字数： 2.3k 阅读时长 ≈ 8 分钟
两数相除、位运算、数学、中等

题目描述

给你两个整数，被除数 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
/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
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 {

    /**
     * @param Integer $dividend
     * @param Integer $divisor
     * @return Integer
     */
    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
# @param {Integer} dividend
# @param {Integer} divisor
# @return {Integer}
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

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户