问题简述
写一个程序来实现两个非负整数的除法，只允许以下操作：
- 赋值
- 位操作，例如>>,<<,&,|,^,~
- 逻辑判断
思路阐述
这道题的意思就是用位操作来实现乘法。
暴力破解的思路就是重复加一个数字，例如3x5就是5个3相加，但是这样做的复杂度太高——O(2^n)，其中n为输入的比特数。
一个更合适的方法是利用加法操作和位移操作结合来实现乘法。3x5=0b11*0b101=(0b10*0b101) + (0b1*0b101)= 0b101<<1+0b101<<0.
具体操作，就是把乘数的每一位抽出来，然后如果是1，被乘数做对应位移，然后再加到和上。
这里可以思考，能不能只抽1？看上去，如果只抽1的话，当乘数0比较多的时候效率更高，但其实从最坏情况来说，只抽1的复杂度和每一位都抽取是一样的，而且这样抽取出来还得判断要位移多少位，相对而言一位位地位移更简单，因为位移多少位一直都是知道的。
此外，还需要实现一个加法，这个主要用进位实现，一位一位加，没什么太好说的。
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;
}
加法的时间复杂度是O(n)，n是操作数的宽度。乘法的时间复杂度是O(n^2)。
