問(wèn)題簡(jiǎn)述

寫一個(gè)程序來(lái)實(shí)現(xiàn)兩個(gè)非負(fù)整數(shù)的除法，只允許以下操作：

1. 賦值
2. 位操作，例如>>,<<,&,|,^,~
3. 邏輯判斷

思路闡述

這道題的意思就是用位操作來(lái)實(shí)現(xiàn)乘法。
暴力破解的思路就是重復(fù)加一個(gè)數(shù)字，例如3x5就是5個(gè)3相加，但是這樣做的復(fù)雜度太高——O(2^n)，其中n為輸入的比特?cái)?shù)。
一個(gè)更合適的方法是利用加法操作和位移操作結(jié)合來(lái)實(shí)現(xiàn)乘法。3x5=0b11*0b101=(0b10*0b101) + (0b1*0b101)= 0b101<<1+0b101<<0.
具體操作，就是把乘數(shù)的每一位抽出來(lái)，然后如果是1，被乘數(shù)做對(duì)應(yīng)位移，然后再加到和上。
這里可以思考，能不能只抽1？看上去，如果只抽1的話，當(dāng)乘數(shù)0比較多的時(shí)候效率更高，但其實(shí)從最壞情況來(lái)說(shuō)，只抽1的復(fù)雜度和每一位都抽取是一樣的，而且這樣抽取出來(lái)還得判斷要位移多少位，相對(duì)而言一位位地位移更簡(jiǎn)單，因?yàn)槲灰贫嗌傥灰恢倍际侵赖摹?br> 此外，還需要實(shí)現(xiàn)一個(gè)加法，這個(gè)主要用進(jìn)位實(shí)現(xiàn)，一位一位加，沒(méi)什么太好說(shuō)的。

public static long multiply(long x, long y) {
    long sum = 0;
    while (x != 0) {
        // Examines each bit of x.
        if ((x & 1) != 0) {
            sum = add(sum , y);
        } 
        x >>>= 1;
        y <<= 1 ;
    }
    return sum;
}

private static long add(long a, long b) {
    long sum = 0, carryin = 0, k = 1, tempA = a, tempB = b;
    while (tempA != 0 | | tempB != 0) {
        long ak = a & k, bk = b & k ;
        long carryout = (ak & bk) | (ak & carryin)|(bk & carryin);
        sum |= (ak ^ bk ^ carryin);
        carryin = carryout << 1;
        k <<= 1 ;
        tempA >>>= 1 ;
        tempB >>>= 1 ;
    }
    return sum|carryin;
}

加法的時(shí)間復(fù)雜度是O(n)，n是操作數(shù)的寬度。乘法的時(shí)間復(fù)雜度是O(n^2)。