位运算之实现加减乘除_按位运算和乘法运算组合

由于不是科班出生，对位运算一直产生抗拒心理，今天接触到相关算法题：用位运算实现加减乘除，在此记录下来。

位运算实现加法

大致分三步：

1. 先求两数不带进位的加法：a和b异或的值
2. 再求两数进位的值：a和b与的结果左移一位
3. 将1，2相加（这里的加法又是以上的2步完成，直到没有进位）

贴代码：

	public static int add(int a,int b){
        int sum = a;
        while (b != 0){
            sum = a ^ b;    //将a，b两值不带进位相加
            b = (a & b) << 1; //b更新为进位的值
            a = sum;   //a更新为不带进位的相加值
        }
        return sum;
    }
1
2
3
4
5
6
7
8
9

位运算实现减法

减法就是：a - b = a + (- b)。说一下-b的实现（发现自己之前都理解错了 ）。
在计算机内存中存放的都是数值的补码（正数的补码为原码本身，负数的补码为原码符号位不变其余位取反然后结果加1；正数的反码为源码本身，负数的反码为原码符号位不变其余位取反）。

下面讲一下~9这个操作在计算机中实现的步骤：（假设是8位的）
+9 原码：0000 1001
+9 补码：0000 1001 （实际存放的值）
~按位取反后原码：1111 0110
补码：1000 1010 (实际存放值)
也就是~9的输出会是-10。

那么再看一下~(-9)这个操作：
-9 原码：1000 1001
-9 补码：1111 0111
~按位取反后原码：0000 1000
补码：0000 1000
~（-9）的输出是8。

找到规律了，要求a的相反数，就是 (~a) + 1 。

贴代码：

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

    public static int neg(int b){ //求相反数
        return add(~b,1);
    }
1
2
3
4
5
6
7

位运算实现乘法

这个要结合平时做乘法的逻辑，聪慧的你一定知道怎么做，（本人比较懒）这里就不画图了。
若要计算a*b，分以下几步:（先定义一个res变量表示结果）

1. b的最后一位如果为1，res加上a，b的最后一位如果为0，当然就不加啦；（这里加法仍然要用位运算）
2. 将b右移1位，a左移一位，为下次运算做准备；
3. 重复1,2步直到b为0。

贴代码：

	public static int multiply(int a,int b){
        int res = 0;
        while (b != 0){
            if ((b & 1) != 0){
                res = add(res,a);
            }
            a <<= 1;
            b >>>= 1;//无符号右移
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11

位运算实现除法

思路是：为了求 res = a / b，则 a = res * b，为了演说方便，假如 res = 9，其二进制为1001，则
a = (1 * 2³ + 0 * 2² + 0 * 2¹ +1 * 2⁰ ) * b = b * 2³ + b * 2⁰。
问题就转化为如何求2的指数了。
要注意的是：负数全部先转化为正数来做，最后再根据符号转成相应的结果，但是由于Integer的负数最小转化为正数会溢出，所以要特殊处理。
贴代码：

	public static int divide(int a ,int b){
        if (b == 0){
            throw new RuntimeException("num/0");
        }else 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){ //最小值求相反数会溢出
            int res = div(add(a,1),b); //先把最小值+1，再转换成正数做除法
            res = add(res,div(minus(a,multiply(res,b)),b)); //  res + (a - res * b) / b
            return res;
        }else {
            return div(a,b);
        }
    }

    public static int div(int a,int b){ //核心代码
        int x = a < 0 ? neg(a) : a; // 如果为负数，求相反数
        int y = b < 0 ? neg(b) : b;
        int res = 0;
        for(int i = 31;i > -1;i = minus(i,1)){
            if ((x >> i) >= y){ //将res的最高位记录下来，从高位开始记录
                res |= 1 << i;
                x = minus(x,y << i);
            }
        }
        res = ((a < 0 && b <0) || (a > 0 && b < 0)) ? neg(res) : res;
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29