Leetcode 29. Divide Two Integers

亦凉 2022-07-14 12:59 136阅读 0赞

一道有意思的题目，难度不是很大，但是不仅思路多，而且写法也非常多，真是有趣。

第一想法，这不就是大数除法吗，觉得特别麻烦。  
第二想法，发现这并不是大数，于是就有一些有趣的想法了。

## 第一种解法 ##

ab=eIn(a)eIn(b)=eIn(a)−In(b)

class Solution {
        public:
            int divide(int dividend, int divisor) {
                /** a/b = e^(ln(a))/e^(ln(b)) = e^(ln(a)-ln(b)) **/
                if(dividend==0)  return 0;
                if(divisor==0)  return INT_MAX;
    
                double t1=log(fabs(dividend));
                double t2=log(fabs(divisor));
                long long result=double(exp(t1-t2));
                if((dividend<0) ^ (divisor<0))  result=-result;
                if(result>INT_MAX)  result=INT_MAX;
                return result;
            }
        };

## 第二种解法 ##

模拟二进制计算，总结一下规律。  
在计算机内一个正整数

ret=a0\+a1∗2\+a2∗22\+......\+a29∗229\+a30∗230\+a31∗231ai=0 or 1

所以  BA 可以表示为

ret=BA⇒A×(a0\+a1∗2\+a2∗22\+......\+a29∗229\+a30∗230\+a31∗231)=B

1.  我们可以发现，左右两边同时向右移31位可得`A*a_{31} = B>>31`。  
    于是可以得到`if (B>>31) > A, then a31 = 1; else a31 = 0`
2.  左右两边同时向右移30位可得`A*a30 + A*a30*2 = B>>30`，也就是说`a30 = ((B>>30) -a30*A*2)/A`，右式也可以写成`(B-a31*A<<31)>>30`，所以我们设置一个变量`B' = B - a31*A<<31`。  
    于是可以得到`if (B'>>30) > A, then a30 = 1; else a30 = 0`
3.  左右两边同时向右移29位得到`a29 = ((B-a31*A<<31-a30*A<<30)>>29)/A`，我们设置变量`B'' = B' - a30*A<<30` .  
    可得`if (B''>>29) > A, then a29 = 1; else a29 = 0;`

然后以此类推。

class Solution(object):
        def divide(self, dividend, divisor):
            """ :type dividend: int :type divisor: int :rtype: int """
            flag = (dividend > 0) ^ (divisor > 0)
            dividend, divisor = abs(dividend), abs(divisor)
            ans = 0
            for i in range(31, -1, -1):
                if (dividend>>i) >= divisor:
                    ans <<= 1
                    ans |= 1
                    dividend -= (divisor << i)
                else:
                    ans <<= 1
            if flag:
                ans = -ans
            return min(max(-2147483648, ans), 2147483647)

这种方法应该还有一种类似的写法  
证明应该是类似的，都是模拟二进制计算

class Solution:
        # @return an integer
        def divide(self, dividend, divisor):
            positive = (dividend < 0) is (divisor < 0)
            dividend, divisor = abs(dividend), abs(divisor)
            res = 0
            while dividend >= divisor:
                temp, i = divisor, 1
                while dividend >= temp:
                    dividend -= temp
                    res += i
                    i <<= 1
                    temp <<= 1
            if not positive:
                res = -res
            return min(max(-2147483648, res), 2147483647)