引子

    某天研究 fail-fast机制的时候，去看了看hashCode的实现方式，然后发现每个对象的实现都不一样；于是研究一个String的；于是看到公式：

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

于是很不解，这个公式很明显会溢出(超过2^32)，尝试了几次发现系统会输出hashCode为负数的值，就默默地去回顾一下二进制的加减乘除

准备工作：

-2 = 0xfffffffe
-1 = 0xffffffff
0 = 0x0
1 = 0x1
2 = 0x2
max = 0x7fffffff = 2147483647
min = 0x80000000 = -2147483648

3 + 5 = 8
==>
  0 0 1 1  -> 3
+ 0 1 0 1  -> 5
----------
= 1 0 0 0  -> 8

1 + -1(0x7fffffff) = 0
==>
 ?_ 0 0 ... 1  -> 1
+?_ 1 1 ... 1  -> -1
--------------
=1_ 0 0 ... 0  -> 0

3 * 5 = 15
==>
0 0 1 1 -> 3
* 0 1 0 1 -> 5
-------------
0 1 0 1 -> 5
+ 0 1 0 1 -> 10
-------------
1 1 1 1 -> 15

14 / 3 = 4 余 2
14(1110[被除数])、3(11[除数])、4([结果])、2([余数])
==>
1 0 0 --> 结果[4]
-----------
1 1 / 1 1 1 0
---------------
1 1
---------------
0 1
---------------
1 0
---------------
1 0 --> 余数[2]

回顾之前的问题，公式溢出问题：

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

就很容易解释了，

1，31^(n-1)的结果，高位会被省去

2，加法结果的结果，高位会被省去，这也是为什么会计算出负数的原因

1. 加法

当二进制加法没有进位时，两个数的加法其实就是按位异或，例如3 + 4 = 7，011 + 100 = 111，这个结果就是按位异或得到的结果，但是我们的加法肯定是存在进位的，那我们进位怎么表示呢，我们想一下，我同样使用异或运算，当只考虑一位的时候（a表示其中一个数的第i位，b表示另外一个数的第i位），只有两个1才会有进位，这就和与运算是一样的，但是进位肯定是要往前移位的，所以进位可以表示为 a & b << 1

递归写法

public int sum(int a, int b) {
    // 如果b为0，则表示没有进位了，那么a就是结果
    if (b == 0) {
        return a;
    }
    return sum(a ^ b, (a & b) << 1);
}

非递归写法

public int sum(int a, int b) {
    while (b != 0) {
        // 保留a的值
        int t = a;
        a = a ^ b;
        b = (t & b) << 1;
    }
    return a;
}

2. 减法

减法可以转换为加法，就不赘述了，例如a - b = a + (-b)

3. 乘法

关于二进制的乘法，例如 110 * 1010101，a * b 我们可以以其中a为基准，判断a的最低位是否为1，如果最低位是1，则结果加上b，然后a右移一位，b左移一位，直到a等于0，最后的结果就是结果 + b，我们判断最低位是否为1是因为我们右移的时候会丢失这个1，其实就是一个数除2，另外一个数乘2，对于结果是没有影响的，例如 6 * 43 = 3 * 86 = 86 + (1 * 172) = 86 + 172，就是这样的一个过程
代码实现

public int mul(int a, int b) {
    int res = 0;
    while (a != 0) {
        if ((a & 1) == 1) {
            res += b;
        }
        a >>= 1;
        b <<= 1;
    }
    return res;
}

4. 除法（整数除法）

关于二级制的除法，其实和乘法是相反的，分为以下几个步骤，a / b，默认 b < a

1. 将 b 的位数通过移位与 a 对齐，记为b1
2. 如果 a >= b1，则 a = a - b1，res += 2 的（b的位数- b1的位数）次方，然后 b1 右移一位
3. 如果 b1 大于等于 b，继续步骤 2
4. 最后得到结果res，a 就是 a / b 的余数

整体过程描述：10 / 3

• a = 10 b = 3 res = 0 b1 = 12
• a = 10 b = 3 res = 0 b1 = 6
• a = a - b1 = 4 b = 3 res += 2 ^ (3 - 2) = 2 b1 = 3
• a = a - b1 = 1 b = 3 res += 2 ^ (2 - 2) = 2 + 1 = 3 b1 = 1

即最后的结果 res = 3，余数 a = 1
代码实现

// 默认a b和运算中的结果都在int范围内
// 默认都是正数，如果出现负数，则符号统一处理
public int div(int a, int b) {
    // 如果 a < b，直接返回0
    if (a < b) {
        return 0;
    }
    int count = 0; // 记录b移位的次数，即 b 和 b1 相差位数（二进制）
    int b1 = b;
    int res = 0; // 记录结果
    // 模拟移位
    while (b1 < a) {
        ++count;
        b1 <<= 1;
    }
    while (b1 >= b) {
        if (a >= b1) {
            a -= b1;
            res += (1 << count);
        }
        b1 >>= 1;
        --count;
    }
    return res;
}

PS: 这个除法并不适用于所有的 int 整数的除法，当出现一些特殊值时，可能导致溢出，例如Integer.MIN_VALUE等

常用的位运算符：

与（&） 同1出1，有0出0

或（|）有1出1，全0出0

异或（^）相同出0，不同出1

非（~）又叫取反 

左移 <<  （即乘2，最右边加个0）

右移 >>  （即除2删掉最右边一位）

做法：

求加法主要用到 异或 (^) 和 与(&) 这两个运算符

异或 用来求不需要进位的位相加。（都是0的时候是0，单独一个1的时候就是本位的值，都是1要进位）

与  用来求进位的和（因为相同出1，相同的时候肯定是需要进位的），因为是进位，所以需要左移一位，要不然就错了（如 101 & 101 结果是101，我们要的是1010，因为是进位）

本位跟进位都求好，在用它重复上面的做法即可，把它重新当做个新加法算。（最后进位为0的时候就结束了）

代码如下：

 public int add(int a, int b) {
     while(b != 0){
         int c = (a & b) << 1;
         a = a ^ b;
         b = c;
     }
     return a;
 }

注：此处代码是32位以内的运算，因为是int类型（若要更多位数，用long类型需要）