For any integer, or long, "<< n" means multiply by 2 ^ n. And ">> n" means divide by 2 ^ n.
dividend = 45, divisor = 7
shift = 3, 7 * 2 * 2 * 2 = 56 > 45, the number of 7 that add up to be larger than 56 is 2 * 2 * 2 = 8
ans = 2 * 2 = 4, a = 45 - 7 * 2 * 2= 17
shift = 2, 7 * 2 * 2 = 28 > 17,
ans = 4 + 2 = 6, a = 17 - 7 * 2 = 3 < divisor
Note that since it is possible to overflow, we need to convert both dividend and divisor to long. ans should also be long type.
Update 2016-05-23:
45 ~ 7 * 6 = 7 * (2^2 + 2 ^ 1).
public int divide(int dividend, int divisor) { if (divisor == 0) return Integer.MAX_VALUE; boolean isNegative = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0); long a = Math.abs((long)dividend); long b = Math.abs((long)divisor); if (a < b) return 0; long ans = 0; while (a >= b) { int shift = 0; while ((b << shift) <= a) shift++; ans += ((long)1 << (shift - 1)); a = a - (b << (shift - 1)); } if (!isNegative && ans > (long)Integer.MAX_VALUE) return Integer.MAX_VALUE; return isNegative ? (int)-ans : (int)ans; }
No comments:
Post a Comment