首先回顾一下位运算

与（&） 两者均为1才为1，也就是遇0则0。（1001 & 1110 = 1000）

或（|） 两者均为0才是0，也就是遇1则1。（1001 | 1110 = 1111 ）

异或（^）相同为0，不同为1。（1001 ^ 1110 = 0111）

左移（<<）A<<B，将A的值向左移动B的位数。左移一位相当于A乘2，左移B位相当于A乘2^B（101110<<3 ==110000 ）

右移（>>和>>>）>>代表带符号右移，最高位补符号位 >>>代表不带符号右移，最高位补0。右移一位相当于除2，右移B位相当于除以2^B

(01110(14)>>2=00011(3)）

(1111 0010(-14)>>2=1111 1100(-4))

---

加法

异或运算也叫无进位相加

1001 0110

^ 1110 0111

= 0111 0001

可以看出来0+1=1 1+1进位得0，但下一位运算忽略进位得1+1依然是0

进位信息可由与运算得出

/\1001 0110

& 1110 0111

= 1000 0110

进位信息是与运算的下一位也就是左移一位

/*
A+B = A ^ B + A & B << 1
    =(A^B) ^ (A & B << 1) + (A ^ B) & (A & B << 1) << 1
    =……
*/

这个过程可以一直进行下去，直到进位信息为0，结果就出来了。

用代码可以这样实现

public static int add(int a, int b) {
   int sum = a;//假如b一开始为0，答案就是a
      while (b != 0) {//进位信息为0结束
          sum = a ^ b;//无进位相加
          b = (a & b) << 1;//进位信息
          a = sum;
      }
   return sum;
}

减法

减法可作为加法的逆运算

A-B = A + (-B)

先写一个转换相反数的方法，即取反加一

public static int negNum(int n) {
    return add(~n, 1);
}

再调用加法即可

public static int minus(int a, int b) {
    return add(a, negNum(b));
}

乘法

/*
1010 * 101 = 1010 * 2^0 + 1010 * 2^2 
           = 1010 + 00000 + 101000
*/

这个好理解，101转换过来就是2^2+2^0，用乘法分配律就能转化，然后，根据左移的意义(左移B位相当于A乘2^B)也就很好理解。

public static int multi(int a, int b) {
    int res = 0;//初始为0
    while (b != 0) {//直到b彻底走完
        if ((b & 1) != 0) {//判断是否为1
            res = add(res, a);//为1就加进去
        }
        a <<= 1;//将a进行左移
        b >>>= 1;//b进行减少
    }
    return res;
}

除法

emmm

a/b=c
假设c为1001
a = b*2^0+b*2^3
c为0为上有1，3位位上有1
其余为0
所以计算c只需要知道c那些位置上需要1
假设a为1110，b为0101，找到c为1的位置，只需要去让b左移去够到a，但不超过a就可以，对应的c的位数上就应该为1，
b左移一位不超过a，左移两位大于a，所以c的第一位就是1，第0位是0
现在就需要将a减去刚刚左移出1位的b，也就是a - (b << 1) = 1110 - 1010 = 0100
接着发现0100与0101，0101已经大于0100，所以答案就是0010
看代码会发现并没有左移b，而是右移a，这是因为，假如一直左移b，会出现最高位也就是符号位变号，影响判断。
------

   public static int div(int a, int b) {
        int x = isNeg(a) ? negNum(a) : a;
        int y = isNeg(b) ? negNum(b) : b;//全弄成正数
        int res = 0;
        for (int i = 30; i >= 0; i = minus(i, 1)) {//x为非负，没必要右移31位
            if ((x >> i) >= y) {//不移动y是因为怕符号位影响判断
                res |= (1 << i);//移动i位上设置为1
                x = minus(x, y << i);
            }
        }
        return isNeg(a) ^ isNeg(b) ? negNum(res) : res;//符号不相同就为负
    }

leetcode题目-两数相除

这道题同样可以用上述方法解决

再添加一个方法，其中最为关键是int的系统最小（Integer.MIN_VALUE）是在int范围没有相反数，这就需要分类讨论，

1.两个都是最小，相除得1

2.除数是最小，无论被除数为多少，结果都为0.（int）

3.被除数为最小，当除以-1时，题目要求返回系统最大，

其余数字可以这样计算先最小值加一，先计算一次结果，再与差再进行一次除法，举个例子

假设-20~19是一个范围，-20就是最小

计算-20/10。因为在（-20，19）内没有20，所以先计算

（-20+1）/ 10 = -1

-1*10 = -10

-20-(-10) = -10

-10 / 10 = -1

-1+(-1) = -2即为答案

 public static int divide(int a, int b) {
    if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
        return 1;
    } else if (b == Integer.MIN_VALUE) {
        return 0;
    } else if (a == Integer.MIN_VALUE) {
        if (b == negNum(1)) {
            return Integer.MAX_VALUE;
        } else {
            int c = div(add(a, 1), b);
            return add(c, div(minus(a, multi(c, b)), b));
        }
    } else {
        return div(a, b);
    }
 }