Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

如果可以用乘的话，二分搜索倒是不错的解法。
否则，只能寄希望于位符操作了。

基本思想就是把除数向左移位(×2)然后与被除数比较，直到发现仅次于被除数的那个值，减去该值后继续。也可以用递归做，这里图省事，就是一个循环了事。

 1 public class Solution {
 2     public int divide(int dividend, int divisor) {
 3         // Note: The Solution object is instantiated only once and is reused by each test case.
 4         //return dividend / divisor;
 5         if(divisor == 1) return dividend;
 6         if(divisor == -1) return -dividend;
 7         if(dividend == 0) return 0;
 8         int sig = -1;
 9         if((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0))
10             sig = 1;
11         long idividend = Math.abs((long)dividend);
12         long idivisor = Math.abs((long)divisor);
13         int result = 0;
14         while (idividend >= idivisor) {
15             long d = idivisor;
16             int temp = 1;
17             while (idividend >= d << 1) {
18                 d = d << 1;
19                 temp = temp << 1;
20             }
21             idividend -= d;
22             result += temp;
23         }
24         return result * sig;
25     }
26 }

做这一题的时候要回归到除法的定义去：

（3）二进制数的乘法

　　二进制数乘法过程可仿照十进制数乘法进行。但由于二进制数只有0或1两种可能的乘数位，导致二进制乘法更为简单。二进制数乘法的法则为：

0×0＝0
0×1＝1×0＝0
1×1＝1

　　例如：1001和1010相乘的过程如下：

　　由低位到高位，用乘数的每一位去乘被乘数，若乘数的某一位为1，则该次部分积为被乘数；若乘数的某一位为0，则该次部分积为0。某次部分积的最低位必须和本位乘数对齐，所有部分积相加的结果则为相乘得到的乘积。

（4）二进制数的除法

　　二进制数除法与十进制数除法很类似。可先从被除数的最高位开始，将被除数（或中间余数）与除数相比较，若被除数（或中间余数）大于除数，则用被除数（或中间余数）减去除数，商为1，并得相减之后的中间余数，否则商为0。再将被除数的下一位移下补充到中间余数的末位，重复以上过程，就可得到所要求的各位商数和最终的余数。

例如：100110÷110的过程如下：

所以，100110÷110＝110余10。

当然也可以用10进制的来做。

 1 public class Solution {
 2     public int divide(int dividend, int divisor) {
 3         // Note: The Solution object is instantiated only once and is reused by each test case.
 4         int o=1;
 5         long a = dividend; 
 6         long b = divisor;
 7         if(dividend < 0){
 8             o ^= 1;
 9             a = -a;
10         }
11         if(b < 0){
12             o ^= 1;
13             b = -b;
14         }
15         long result = 0, bit = 0;
16         for(long i = a; i > b; i >>= 1){
17             bit ++;
18         }
19         
20         while(a >= b){
21             if(a >= (b << bit)){
22                 a -= b << bit;
23                 result |= 1 << bit;
24             }
25             bit --;
26         }
27         if(o == 1) return (int)result;
28         else return (int)(-result);
29     }
30 }

这题有两个地方比较麻烦：

一个是要转换成long 进行运算。以防符号位的影响。

在一个就是首先就要转成long 后面都只能用long 来运算，如果看负数的时候使用int 就会出错。

第三遍：

test case:

1. dividend & divisor can be negtive.

2. handle divisor == 1