[leetcode] Divide Two Integers | 用移位做除法
Posted October 19, 2013
on:不让用*, /, %号做整数除法。基本只能bit了。但是bit操作都是跟2有关的,所以到最后还得不断缩小范围,好能贴近结果。
算法:a / b
- a本来是想一直-b,然后减到<0了,算counter。但是这样慢,所以类似c++ vector的思路,每次发现还没减没,那减数就翻倍(b <<= 1)
- 然后到了一定程度,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; }
1 | DIVIDE TWO INTEGERS | jingchen87
April 22, 2014 at 11:03 pm
[…] From <https://leetcodenotes.wordpress.com/2013/10/19/divide-two-integers/> […]