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

Posted by: lexigrey on: October 19, 2013

• In: leetcode | summery
• 1 Comment

不让用*, /, %号做整数除法。基本只能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: bit, hard, math