位运算

# 位运算相加

二进制相加可以用异或操作和与操作得到结果，异或操作得到每一位上的数值，与操作得到需要进位的位置。每次相加需要将异或操作得到值和与操作得到的值左移一位相加，不断循环此操作，直到与操作得到的值为 0，此时不需要进位，异或操作得到的值即为二进制相加的结果。下面为 1203+1111 的实例，对应的二进制为 10010110011+10001010111。

 10010110011    000011100100    100011000010    100010001010    100000001010    100100001010
+10001010111 = +100000100110 = +000001001000 = +000010000000 = +000100000000 = +000000000000 = 100100001010(2314)

Java 代码实现：

public int add(int a, int b) {

    while (b != 0) {

        int t = a ^ b;

        b = (a & b) << 1;

        a = t;

    }

    return a;

}

# 位运算相减

减运算直接转化为加运算即可，将减数转化为其相反数，直接与被减数相加。负数的补码是反码加一，最后附有 Java 位运算符号。

Java 代码实现：

public int subtract(int a, int b) {

    b = add(~b, 1);

    return add(a, b);

}

# 位运算相乘

乘法运算用位移操作和加法操作，先忽略两个乘数的符号，取其绝对值进行相乘。以下为 1203*1111 的实例，对应二进制为 10010110011*10001010111。

 10010110011    100101100110    1001011001100    10010110011000    100101100110000    100101100110000    1001011001100000    10010110011000000    100101100110000000    100101100110000000    1001011001100000000
*10001010111 = *  1000101011 = *    100010101 = *      10001010 = *        1000101 = *         100010 = *           10001 = *             1000 = *               100 = *                10 = *                  1
————————————   —————————————   ——————————————   ———————————————    ———————————————    ———————————————    ————————————————    —————————————————    ——————————————————    ——————————————————    ———————————————————
 10010110011 +  100101100110 +  1001011001100 +  00000000000000 +  100101100110000 +  000000000000000 +  1001011001100000 +  00000000000000000 +  000000000000000000 +  000000000000000000 +  1001011001100000000

Java 实现代码：

public int multiply(int a, int b) {

    // 求 a 和 b 的绝对值

    int multiplier = a < 0 ? add(~a, 1) : a;

    int multiplicand = b < 0 ? add(~b, 1) : b;

    // 求两个绝对值的乘数

    int product = 0;

    while (multiplicand != 0) {

        if ((multiplicand & 1) == 1) {

            product += multiplier;

        }

        multiplier = multiplier << 1;

        multiplicand = multiplicand >> 1;

    }

    // 符号

    if (add(a, b) < 0) {

        product = add(~product, 1);

    }

    return product;

}

# 位运算相除

Java 代码实现：

public int divide(int a, int b) {

    // 求 a 和 b 的绝对值

    int dividend = a < 0 ? add(~a, 1) : a;

    int divisor = b < 0 ? add(~b, 1) : b;

    // 求被除数倒过来的数

    // 以 1 为界限，后面的数为倒过来的数

    int invert = 2;

    while (dividend != 0) {

        invert |= dividend & 1;

        dividend = dividend >> 1;

        invert = invert <<1;

    }

    // 除数过程

    // 商

    int quotient = 0;

    // 余数

    int remainder = 0;

    while (invert > 1) {

        remainder = remainder << 1;

        remainder |= invert & 1;

        invert = invert >> 1;

        quotient = quotient << 1;

        if (remainder >= divisor) {

            quotient |= 1;

            remainder = subtract(remainder, divisor);

        }

    }

    // 符号

    if (add(a, b) < 0) {

        quotient = add(~quotient, 1);

    }

    return quotient;

}

Java 位运算：

• <<(左移)
• >>(右移)
• >>>(无符号右移)
• &(与)
• |(或)
• ^(抑或)
• ~(非)