Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/29.html
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.
Constraints:
-231 <= dividend, divisor <= 231 - 1
divisor != 0
Algorithm
To perform Bit Manipulation, you can utilize another artifact bit. The algorithm operates as follows:
- Check if the dividend is greater than or equal to the divisor. If it is, initialize a variable
t
to be equal to the divisor and a count variablep
to 1. - While twice
t
is less than or equal to the dividend, doublet
, doublep
, and update the result. - Continue the above step until
t
is greater than the dividend. - Determine the sign of the result based on the signs of the dividend and divisor. Use a long integer type for calculations and multiply the result by the sign.
- Handle special cases like when the divisor is 0 or the dividend is -2147483648 and the divisor is -1. For such cases, return INT_MAX.
Code
-
/* * converting int to larger size type like long, or BigInteger. * since overflow on -2147483648 must be handled */ public class Divide_Two_Integers { public static void main(String[] args) { Divide_Two_Integers out = new Divide_Two_Integers(); Solution_recursion s = out.new Solution_recursion(); System.out.println(s.divide(101, 10)); System.out.println(s.divide(-2147483648, 2)); } // @note: give up on bit operation, biggest issue is, bit and negative int are hard to handle public class Solution_bit_on_int { public int divide(int n, int dsor) { if(dsor == 0 || (n == Integer.MIN_VALUE && dsor == -1)) { return Integer.MAX_VALUE; } // save operations if(dsor == 1) { return n; } if(dsor == -1) { return n * -1; } int flag = 1; if(n < 0) { flag *= -1; n *= -1; // @note: overflow... -2147483648/2 } if(dsor < 0) { flag *= -1; dsor *= -1; } int count = 0; // while(n > 0) { // n -= dsor; // count++; // } // moving faster than above while while(n > 0 && n >= dsor) { // while(n > 0) { @note: I missed case: 1/2 int shift = 0; // bit shift /* @note: below bit operation causes issue. 2147483647/1 last loop, shift=31, dsor=1 should not enter below while, but when divisor is 1 or 2 or 4, etc: 1<<31=(-2147483648) 2<<30=(-2147483648) 4<<29=(-2147483648) so, originally I was using "(dsor << shift)" as probe to see if over divident then I change it to be an int, and add extra overflow check */ // while((dsor << shift) <= n) { while((dsor << shift) <= n) { //@note: <n is non-stop loop, should be <=n. eg. 1/1 n -= dsor << shift; count += 1 << shift; // check bit overflow if((Integer.MAX_VALUE >> 1) <= (dsor << shift)) { break; } shift++; } } return count * flag; } } public class Solution_recursion { int result = 0; /* * my way of acceleration, increase step size each iteration, * * eg: * * 101 / 10: * 101 - 10*1 = 91 * 91 - 10*2 = 71 * 71 - 10*4 = 31 * * now 31 is less then 10*8, count=1+2+4=7 ok, send to next recursion * * 31 / 10: and repeat above acceleration, start again from step=1 * 31 - 10*1 = 21 * 21 - 10*2 = 1 * * now 1 is less than 10*4, this recurion count=1+2=3 * * add up all count=7+3=10 */ public int divide(int dividend, int divisor) { // convert to long long n = (long)dividend; long dsor = (long)divisor; if(dsor == 0 || (n == Integer.MIN_VALUE && dsor == -1)) { return Integer.MAX_VALUE; } // save operations if(dsor == 1) { return (int)n; } if(dsor == -1) { return (int)(n * -1); } int flag = 1; if(n < 0) { flag *= -1; n *= -1; // @note: overflow... -2147483648 } if(dsor < 0) { flag *= -1; dsor *= -1; } dfs(n, dsor); return flag * result; } public void dfs(long n, long dsor) { // if(n <= 0) { if(n < dsor) { // @note: missed here, end condition is not n return; } int step = 1; while (n >= (dsor * step)) { // @Note: should be >= , eg: 2/2 = 1 n -= (dsor * step); result += step; step *= 2; // acceleration of step size } // now start again with no acceleration dsor dfs(n, dsor); } } // @note: just convert to long, and solution AC. But code is ugly... public class Solution { public int divide(int nn, int ddsor) { // convert to long long n = (long)nn; long dsor = (long)ddsor; if(dsor == 0 || (n == Integer.MIN_VALUE && dsor == -1)) { return Integer.MAX_VALUE; } // save operations if(dsor == 1) { return (int)n; } if(dsor == -1) { return (int)(n * -1); } int flag = 1; if(n < 0) { flag *= -1; n *= -1; // @note: overflow... -2147483648 } if(dsor < 0) { flag *= -1; dsor *= -1; } int count = 0; // while(n > 0) { // n -= dsor; // count++; // } // moving faster than above while while(n > 0 && n >= dsor) { // while(n > 0) { @note: I missed case: 1/2 int shift = 0; // bit shift /* @note: below bit operation causes issue. 2147483647/1 last loop, shift=31, dsor=1 should not enter below while, but when divisor is 1 or 2 or 4, etc: 1<<31=(-2147483648) 2<<30=(-2147483648) 4<<29=(-2147483648) so, originally I was using "(dsor << shift)" as probe to see if over divident then I change it to be an int, and add extra overflow check */ // while((dsor << shift) <= n) { while((dsor << shift) <= n) { //@note: <n is non-stop loop, should be <=n. eg. 1/1 n -= dsor << shift; count += 1 << shift; // check bit overflow if((Integer.MAX_VALUE >> 1) <= (dsor << shift)) { break; } shift++; } } long result = count * flag; if(result > Integer.MAX_VALUE) { return Integer.MAX_VALUE; } else if(result < Integer.MIN_VALUE) { return Integer.MIN_VALUE; } else { return (int)result; } } } public class Solution_over_time_limit { public int divide(int n, int dsor) { if(dsor == 0 || (n == Integer.MIN_VALUE && dsor == -1)) { return Integer.MAX_VALUE; } int flag = 1; if(n < 0) { flag *= -1; n *= -1; } if(dsor < 0) { flag *= -1; dsor *= -1; } int count = 0; while(n > 0) { n -= dsor; count++; } return count * flag; } } } ############ class Solution { public int divide(int a, int b) { int sign = 1; if ((a < 0) != (b < 0)) { sign = -1; } long x = Math.abs((long) a); long y = Math.abs((long) b); long tot = 0; while (x >= y) { int cnt = 0; while (x >= (y << (cnt + 1))) { cnt++; } tot += 1L << cnt; x -= y << cnt; } long ans = sign * tot; if (ans >= Integer.MIN_VALUE && ans <= Integer.MAX_VALUE) { return (int) ans; } return Integer.MAX_VALUE; } }
-
// OJ: https://leetcode.com/problems/divide-two-integers/ // Time: O(logD) where D is |dividend| // Space: O(1) class Solution { public: int divide(int dividend, int divisor) { if (!divisor) return 0; // divide-by-zero error bool pos1 = dividend > 0, pos2 = divisor > 0, pos = !(pos1^pos2); if (pos1) dividend = -dividend; if (pos2) divisor = -divisor; int q = 0, d = divisor, t = 1; while (t > 0 && dividend < 0) { if (dividend - d <= 0) { dividend -= d; q -= t; if ((INT_MIN >> 1) < d) { t <<= 1; d <<= 1; } } else { d >>= 1; t >>= 1; } } return pos? -q : q; } };
-
class Solution: def divide(self, a: int, b: int) -> int: INT_MAX = (1 << 31) - 1 INT_MIN = -(1 << 31) sign = -1 if a * b < 0 else 1 a = abs(a) b = abs(b) tot = 0 while a >= b: cnt = 0 while a >= (b << (cnt + 1)): cnt += 1 tot += 1 << cnt a -= b << cnt return sign * tot if INT_MIN <= sign * tot <= INT_MAX else INT_MAX ############ class Solution(object): def divide(self, dividend, divisor): """ :type dividend: int :type divisor: int :rtype: int """ if divisor == 0: return 0x7fffffff sign = 1 if dividend * divisor < 0: sign = -1 ans = 0 cnt = 1 dividend = abs(dividend) divisor = abs(divisor) subsum = divisor while dividend >= divisor: while (subsum << 1) <= dividend: cnt <<= 1 subsum <<= 1 ans += cnt cnt = 1 dividend -= subsum subsum = divisor return max(min(sign * ans, 0x7fffffff), -2147483648)
-
func divide(a int, b int) int { sign, ans, INT32_MAX, INT32_MIN, LIMIT := false, 0, 1<<31-1, -1<<31, -1<<31/2 if (a > 0 && b < 0) || (a < 0 && b > 0) { sign = true } a, b = convert(a), convert(b) for a <= b { cnt := 0 // (b<<cnt) >= LIMIT 是为了避免 b<<(cnt+1) 发生溢出 for (b<<cnt) >= LIMIT && a <= (b<<(cnt+1)) { cnt++ } ans = ans + -1<<cnt a = a - b<<cnt } if sign { return ans } if ans == INT32_MIN { return INT32_MAX } return -ans } func convert(v int) int { if v > 0 { return -v } return v }
-
public class Solution { public int Divide(int dividend, int divisor) { return (int)DivideInternal(dividend, divisor); } public long GetHighestBit(long x) { if (x == 0) return 0; long k = 0x80000000; while ((x & k) == 0) { k >>= 1; } return k; } public long DivideInternal(long dividend, long divisor) { int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1; if (dividend < 0) dividend = -dividend; if (divisor < 0) divisor = -divisor; long result = 0; long pointer = GetHighestBit(dividend); long currentHeader = 1; dividend = dividend ^ pointer; while (pointer > 0) { result <<= 1; if (currentHeader >= divisor) { ++result; currentHeader -= divisor; } pointer >>= 1; bool nextIsOne = (dividend & pointer) != 0; currentHeader = (currentHeader << 1) + (nextIsOne ? 1 : 0); dividend = dividend ^ (nextIsOne ? pointer : 0); } result = sign * result; if (result > int.MaxValue || result < int.MinValue) { return int.MaxValue; } return result; } }