Problem description
Given two integers: dividend and divisor, return dividend/divisor without using multiplication, division, and mod operator.
The integer division should truncate toward zero, which means just discard fractional part.
Example:
Input: dividend = 10, divisor = -3
Output: -3
Explanation: 10/(-3) = -3.3333..., which should be truncated to -3.
Notes:
The dealing with an environment which could only store integers within 32-bit signed integer range: ([-2^{31},\ 2^{31}-1]).
If the quotient is greater than (2^{31}-1), return (2^{31}-1).
If the quotient is less than (-2^{31}), return (-2^{31}).
Problem analysis
Firstly, we should consider the sign of divisor and dividend, in order to ignore different sign, we can turn them to same sign first. In this question, the integer bound are 32-bit signed integers, so we can only turn the divisor and dividend into negative(otherwise turn (-2^{32}) to positive will overflow).
Now let’s consider the division between two negative number.
We can easily come up with a naive solution: continually minus divisor to dividend till dividend become larger than divisor. In this process, we count how many divisor are subtracted.
But it’s obviously inefficient, we can minus multiple divisor one time! Suppose (m/n=11), (11) is 1011 in binary, which means:
[m/n\Rightarrow m-1\times n\times 2^4-0\times n\times 2^3-1\times n\times 2^2-1\times n\times 2^1 ]
We can find the smallest (n\cdot2^k) such that (n\cdot2^k>m), then minus (m) with (n\cdot2^k), and continually minus (n\cdot2^{k-1},\ n\cdot2^{k-2},\ …) till (n
Original: https://www.cnblogs.com/liuzhch1/p/leetcode29-divide-two-integers.html
Author: liuzhch1
Title: LeetCode_29. 两数相除Divide Two Integers｜商的二进制表示与除数的关系
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/606696/
转载文章受原作者版权保护。转载请注明原作者出处！