Lexi's Leetcode solutions

[leetcode] Divide Two Integers | 用移位做除法

Posted on: October 19, 2013

不让用*, /, %号做整数除法。基本只能bit了。但是bit操作都是跟2有关的,所以到最后还得不断缩小范围,好能贴近结果。

算法:a / b

  1. a本来是想一直-b,然后减到<0了,算counter。但是这样慢,所以类似c++ vector的思路,每次发现还没减没,那减数就翻倍(b <<= 1)
  2. 然后到了一定程度,b实在太大了,大于a剩余的部分了,那么就停止。然后剩下的a再一点点开始减,b回归成最开始的值,重做这两步。

重点是一旦超过,b应该不要一下回到原始值,而是应该一点一点/2这样做。最刁钻的地方是test case全是各种Integer.MINVALUE之类的,搞得各种溢出,然后才发现Math.abs(MIN_VALUE)其实还是-2147483648(坑爹呢吧abs还是负数),而不是2147483648。

下面的解法是能跑过的。因为测试数据出现了-2147483648,还不能把它转成正的(2147483648就溢出了),所以直接全转换成long(64位),跑一遍就过了。

public int divide(int dividend, int divisor) {
    if (dividend == 0)
        return 0;
    if (divisor == 1)
        return dividend; //纯粹是为了防止超时
    boolean positive = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0);
    long absDividend = dividend < 0 ? 0 - (long) dividend : (long) dividend;
    long absDivisor = divisor < 0 ? 0 - (long) divisor : (long) divisor;
    int result = dividePositive(absDividend, absDivisor, absDivisor);
    return positive ? result : 0 - result;
}
private int dividePositive(long p, long q, long originalDivisor) { // p / q
    if (p < q)
        return 0; //这个十分必要,否则会因为p > 0而直接下一层递归,pq永远不变,死循环了就。
    int result = 0;
    int e = 0;
    while (p >= q) { //等于应该也进去。
        result += 1 << e;
        p -= q;
        q = q << 1;
        e++;
    }
    return p > 0 ? result + dividePositive(p, originalDivisor, originalDivisor) : result;
 }
Advertisements
Tags: , ,

1 Response to "[leetcode] Divide Two Integers | 用移位做除法"

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: