diff options
-rw-r--r-- | divide_2_int.c | 32 | ||||
-rw-r--r-- | divide_2_int.cpp | 32 | ||||
-rw-r--r-- | divide_2_int.py | 32 |
3 files changed, 64 insertions, 32 deletions
diff --git a/divide_2_int.c b/divide_2_int.c new file mode 100644 index 0000000..0e4e754 --- /dev/null +++ b/divide_2_int.c @@ -0,0 +1,32 @@ +// 29. Divide Two Integers +#include "leetcode.h" + +/* + * Given two integers 'dividend' and 'divisor', divide two integers without + * using multiplication, division, or mod operations. the integer division + * should truncate toward zero, which means losing its fractional part. for + * example, 8.345 would be truncated to 8. return the quotient after dividing + * 'dividend' by 'divisor'. + */ + +int divide(int dividend, int divisor) { + if (dividend == INT_MIN && divisor == -1) + return INT_MAX; + long dvd = labs(dividend), dvs = labs(divisor), ans = 0; + int sign = dividend > 0 ^ divisor > 0 ? -1 : 1; + while (dvd >= dvs) { + long temp = dvs, m = 1; + while (temp << 1 <= dvd) { + temp <<= 1; + m <<= 1; + } + dvd -= temp; + ans += m; + } + return sign * ans; +} + +int main() { + printf("%d\n", divide(10, 3)); // expect: 3 + printf("%d\n", divide(7, -3)); // expect: -2 +} diff --git a/divide_2_int.cpp b/divide_2_int.cpp deleted file mode 100644 index 7c172f7..0000000 --- a/divide_2_int.cpp +++ /dev/null @@ -1,32 +0,0 @@ -#include <bits/stdc++.h> - -class Solution { -public: - int divide(int dividend, int divisor) { - if (dividend == divisor) { - if (divisor == -1) - return INT_MAX; - else if (divisor == INT_MIN) - return 1; - else if (divisor < 0) - return 1 + divide(dividend - divisor, divisor); - else - return -1 + divide(dividend + divisor, divisor); - } else if (divisor == INT_MIN) - return 0; - bool negative = (dividend < 0) ^ (divisor < 0); - dividend = abs(dividend); - divisor = abs(divisor); - int result = 0; - for (int i = 31; i >= 0; --i) { - int shiftedDiv = (dividend >> i); - if (shiftedDiv >= divisor) { - result += (1 << i); - dividend -= (divisor << i); - } - } - return (negative ? -result : result); - } -}; - -int main() {} diff --git a/divide_2_int.py b/divide_2_int.py new file mode 100644 index 0000000..8439a1b --- /dev/null +++ b/divide_2_int.py @@ -0,0 +1,32 @@ +# 29. Divide Two Integers + +""" +Given two integers 'dividend' and 'divisor', divide two integers without +using multiplication, division, or mod operations. the integer division +should truncate toward zero, which means losing its fractional part. for +example, 8.345 would be truncated to 8. return the quotient after dividing +'dividend' by 'divisor'. +""" + + +class Solution(object): + def divide(self, dividend, divisor): + """ + :type dividend: int + :type divisor: int + :rtype: int + """ + if dividend == -2147483648 and divisor == -1: + return 2147483647 + dvd, dvs, ans = abs(dividend), abs(divisor), 0 + for i in range(32)[::-1]: + if (dvd >> i) - dvs >= 0: + ans += 1 << i + dvd -= dvs << i + return ans if (dividend > 0) == (divisor > 0) else -ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.divide(dividend=10, divisor=3)) + print(obj.divide(dividend=7, divisor=-3)) |