Divide Two Integers

	Divide two integers without using multiplication, division and mod operator.
	"Time complexity: [(log(dividend/divisor)](not sure)"
	public class Solution {
	public int divide(int dividend, int divisor) {
	if (divisor==0){
	// throw new InvalidInputException("Divisor can not be 0");
	}
	/*
	Integer.MIN_VALUE is -2147483648, but the highest value a 32 bit integer can contain is +2147483647.
	Attempting to represent +2147483648 in a 32 bit int will effectively "roll over" to -2147483648.
	This is because, when using signed integers, the two's complement binary representations of
	+2147483648 and -2147483648 are identical. This is not a problem, however, as +2147483648
	is considered out of range.
	*/
	// conver the diviedend and divisor to long before apply Math.abs()
	long a=Math.abs((long)dividend);
	long b=Math.abs((long)divisor);
	long result=0;
	while (a>=b){
	long c=b;
	int i=0;
	while(c<=a){
	a=a-c;
	c=c<<1;
	result+=1<<i;
	i++;
	}
	}
	if (dividend<0&&divisor>0||dividend>0&&divisor<0){
	result=-result;
	}
	return (int)result;
	}
	}

view raw Divide Two Integers.java hosted with ❤ by GitHub