問題簡述
寫一個程序來實現(xiàn)兩個非負(fù)整數(shù)的除法，只允許以下操作：
- 賦值
- 位操作温兼，例如>>,<<,&,|,^,~
- 邏輯判斷
思路闡述
這道題的意思就是用位操作來實現(xiàn)乘法秸滴。
暴力破解的思路就是重復(fù)加一個數(shù)字，例如3x5就是5個3相加募判，但是這樣做的復(fù)雜度太高——O(2^n)荡含，其中n為輸入的比特數(shù)。
一個更合適的方法是利用加法操作和位移操作結(jié)合來實現(xiàn)乘法届垫。3x5=0b11*0b101=(0b10*0b101) + (0b1*0b101)= 0b101<<1+0b101<<0.
具體操作内颗，就是把乘數(shù)的每一位抽出來，然后如果是1敦腔，被乘數(shù)做對應(yīng)位移均澳，然后再加到和上。
這里可以思考符衔，能不能只抽1找前？看上去，如果只抽1的話判族，當(dāng)乘數(shù)0比較多的時候效率更高躺盛，但其實從最壞情況來說，只抽1的復(fù)雜度和每一位都抽取是一樣的形帮，而且這樣抽取出來還得判斷要位移多少位槽惫，相對而言一位位地位移更簡單，因為位移多少位一直都是知道的辩撑。
此外界斜，還需要實現(xiàn)一個加法，這個主要用進(jìn)位實現(xiàn)合冀，一位一位加各薇，沒什么太好說的。
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;
}
加法的時間復(fù)雜度是O(n)君躺，n是操作數(shù)的寬度峭判。乘法的時間復(fù)雜度是O(n^2)开缎。
