EPI_PrimitiveTypes_No.003_Comput

问题简述

写一个程序来实现两个非负整数的除法，只允许以下操作：

1. 赋值
2. 位操作，例如>>,<<,&,|,^,~
3. 逻辑判断

思路阐述

这道题的意思就是用位操作来实现乘法。
暴力破解的思路就是重复加一个数字，例如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)。