Given two integers dividend
and divisor
, divide two integers without using multiplication, division, and mod operator.
The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345
would be truncated to 8
, and -2.7335
would be truncated to -2
.
Return the quotient after dividing dividend
by divisor
.
Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]
. For this problem, if the quotient is strictly greater than 231 - 1
, then return 231 - 1
, and if the quotient is strictly less than -231
, then return -231
.
Example 1:
Input: dividend = 10, divisor = 3 Output: 3 Explanation: 10/3 = 3.33333.. which is truncated to 3.
Example 2:
Input: dividend = 7, divisor = -3 Output: -2 Explanation: 7/-3 = -2.33333.. which is truncated to -2.
Example 3:
Input: dividend = 0, divisor = 1 Output: 0
Example 4:
Input: dividend = 1, divisor = 1 Output: 1
Constraints:
-231 <= dividend, divisor <= 231 - 1
divisor != 0
Solution: Binary / Bit Operation
The answer can be represented in binary format.
a / b = c
a >= b * Σ(di*2i)
c = Σ(di*2i)
e.g. 1: 10 / 3
=> 10 >= 3*(21 + 20) = 3 * (2 + 1) = 9
ans = 21 + 20 = 3
e.g. 2: 100 / 7
=> 100 >= 7*(23 + 22+21) = 7 * (8 + 4 + 2) = 7 * 14 = 98
ans = 23+22+21=8+4+2=14
Time complexity: O(32)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: int divide(int A, int B) { if (B == INT_MIN) return A == INT_MIN ? 1 : 0; if (A == INT_MIN) { if (B == -1) return INT_MAX; return B > 0 ? divide(A + B, B) - 1 : divide(A - B, B) + 1; } int a = abs(A); int b = abs(B); int ans = 0; for (int x = 31; x >= 0; --x) if (a >> x >= b) ans += 1 << x, a -= b << x; return (A > 0) == (B > 0) ? ans : -ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment