位运算——使用位运算实现整数的四则运算

1、加法

  使用按位运算实现加法，首先了解加法的二进制运算。

例子：

  以 6+3 为例：

    110     # 6的二进制
+    11     # 3的二进制
--------  
   1001     # 9的二进制

解法：

  将 3 和 6 进行按位异或运算，得到按位运算不进位加法的值。

110^11=101

  将 3 和 6 进行按位与运算，得到 3 和 6 相加后哪一位需要向前进位。

110&11=10

  将 3 和 6 按位与运算的结果向左移动一位，则得到当前位进位的值。

(110&11)<<1=100

  如果增量不为 0，则一直执行。

Java 代码实现：

  源码：

    public static void main(String[] args) {
        // 以6+3为例子
        System.out.println("6的二进制"+Integer.toBinaryString(6));
        System.out.println("3的二进制"+Integer.toBinaryString(3));
        System.out.println("6+3的二进制"+Integer.toBinaryString(add(6,3)));
        System.out.println(add(6,3));
    }

    public static int add(int a,int b){
        // 得到a和b不进位加法的值
        int noCarry=a^b;
        // 得到a和b哪一位需要增值
        int increase=(a&b)<<1;
        // 如果增量不为0则继续执行
        if(increase!=0){
            // 将不进位加法的结果值和增量继续相加
            return add(noCarry,increase);
        }
        return noCarry;
    }

  运行结果：

6的二进制110
3的二进制11
6+3的二进制1001
9

2、减法

  使用按位运算实现减法，首先了解减法的二进制运算。

例子：

  以 5-3 为例：

    101     # 5的二进制
-    11     # 3的二进制
--------  
     10     # 2的二进制

解法：

  一个正数原码取反加一得到该正数的负数的补码。

# 3的二进制
00000000000000000000000000000011
# -3的二进制（3取反+1）
11111111111111111111111111111101

  因为 5-3=5+(-3)，所以通过按位运算实现减法运算，先将得到减数的负数然后相加。
  使用按位运算得到一个正数的负数

-a=~a+1

Java 代码实现：

  源码：

    public static void main(String[] args) {
        // 以5-3为例子
        System.out.println("5的二进制"+Integer.toBinaryString(5));
        System.out.println("3的二进制"+Integer.toBinaryString(3));
        System.out.println("5-3的二进制"+Integer.toBinaryString(minus(5,3)));
        System.out.println(minus(5,3));
    }

    public static int add(int a,int b){
        // 得到a和b不进位加法的值
        int noCarry=a^b;
        // 得到a和b哪一位需要增值
        int increase=(a&b)<<1;
        // 如果增量不为0则继续执行
        if(increase!=0){
            // 将不进位加法的结果值和增量继续相加
            return add(noCarry,increase);
        }
        return noCarry;
    }

    public static int minus(int a,int b){
        // 将减数转成负数(~b+1)
        b=add(~b,1);
        // 再将a+(-b)
        return add(a,b);
    }

  运行结果：

5的二进制101
3的二进制11
5-3的二进制10
2

3、正数乘法

  使用按位运算实现乘法，首先了解乘法的二进制运算。

例子：

  以 5*9 为例：

    1001     # 9的二进制
*    101     # 5的二进制
--------  
    1001
      0
+ 1001
--------  
  101101     # 45的二进制

原理：

  将乘数按位从右往左开始遍历，当下标为 x 为 1 则将被乘数向左移动 x 位，为 0 则舍去，最后求和得到结果。

Java 代码实现：

  源码：

    public static void main(String[] args) {
        // 以5*9为例子
        System.out.println("9的二进制"+Integer.toBinaryString(9));
        System.out.println("5的二进制"+Integer.toBinaryString(5));
        System.out.println("5*9的二进制"+Integer.toBinaryString(ride(5,9)));
        System.out.println(ride(5,9));
    }

    public static int ride(int a,int b){
        // 统计被乘数被移动后的和
        int sum=0;
        // 当乘数为0时结束循环
        while (b!=0){
            // 判断乘数的当前为是否为1
            if((b&1)==1){
                sum+=a;
            }
            // 每次循环，将b向右移动一位，a向左移动一位
            b=b>>1;
            a=a<<1;
        }
        return sum;
    }

  运行结果：

9的二进制1001
5的二进制101
5*9的二进制101101
45

4、正数除法

  使用按位运算实现除法，首先了解除法的二进制运算。

例子：

  以 15/6 为例：

    1111     # 15的二进制
-    110     # 6的二进制
--------  
    1001
-    110     # 再减6
--------  
      11     # 结果比6小
--------  
       2     # 减了两次所以结果为2

原理：

  除法本意是求被除数可以由多少个除数组成，那么求出被除数能减去多少个除数即可，做减法的次数就是除法的商。

Java 代码实现：

  源码：

    public static void main(String[] args) {
        // 以15/6为例子
        System.out.println("15的二进制"+Integer.toBinaryString(15));
        System.out.println("6的二进制"+Integer.toBinaryString(6));
        System.out.println("15/6的商"+except(15,6));
    }

    public static int except(int a,int b){
        // 记录商（减的次数）
        int merchant=0;
        // 如果被乘数（被减数）比乘数（减数）小则结束循环
        while (a>=b){
            a=minus(a,b);
            // 执行一次循环商加一
            merchant++;
        }
        return merchant;
    }

    public static int minus(int a,int b){
        // 将减数转成负数(~b+1)
        b=add(~b,1);
        // 再将a+(-b)
        return add(a,b);
    }

    public static int add(int a,int b){
        // 得到a和b不进位加法的值
        int noCarry=a^b;
        // 得到a和b哪一位需要增值
        int increase=(a&b)<<1;
        // 如果增量不为0则继续执行
        if(increase!=0){
            // 将不进位加法的结果值和增量继续相加
            return add(noCarry,increase);
        }
        return noCarry;
    }

  运行结果：

15的二进制1111
6的二进制110
15/6的商2