【算法100天 | 2】位运算实现加减乘除（含：LeetCode 29题 两数相除）

一、位运算基础

0、打印整数的二进制数据

public static void printBinary(int num) {
    // 32位二进制
    for (int i = 31; i >= 0; i--) {
        System.out.print((num & (1 << i)) == 0 ? "0" : "1");
    }
}

1、原码-补码-反码

对正整数而言：原码 = 补码= 反码

对负整数而言：

• 反码 = 原码符号位不变，其他按位取反；
• 补码=反码+1（同样符号位不变）

2、带符号右移 和 不带符号右移

不带符号右移：>>

• 高位均补0

带符号右移：>>>

• 高位补符号位

3、相反数

n的相反数 == ~n + 1（n取反+1），注意：-2^32的相反数 还是它自己；

验证

public class BitCalculate {
    public static void main(String[] args) {
        int num = 5;
        printBinary(num);
        System.out.println();

        // 位运算：取反
        int num2 = ~ num + 1;
        printBinary(num2);

        System.out.println();
        printBinary(-5);
    }

    /**
     * 打印数字的二进制数据
     */
    public static void printBinary(int num) {
        // 32位二进制
        for (int i = 31; i >= 0; i--) {
            System.out.print((num & (1 << i)) == 0 ? "0" : "1");
        }
    }
}

结果：

二、位运算实现加减乘除（LeetCode 29题 两数相除）

假如不允许使用+、-、*、/符号，如果使用位运算实现加减乘除运算？

我们先看+、-、*，/对应于LeetCode的29题，放在最后来看；

1、位运算实现加法

首先要知道：

• 异或（两位不同为1，相同为0）运算（^） 的结果 == 两数不进位的相加

• 与（两位同为1，则为1，否则为0）运算（&）再左移一位（<< 1） 的结果 == 两数相加的进位

思路：

根据异或运算和与运算的特性，可以知道整数 a、b异或的结果为不进位的相加，a、b与运算 再 左移一位的结果为两数相加的进位；所以只需死循环进位信息，重复做异或、与运算操作，直到进位为0为止。

代码：

public static int add(int a, int b) {
    int sum = a;
    while (b != 0) {
        // 无进位的相加
        sum = a ^ b;
        // 进位信息
        b = (a & b) << 1;
        a = sum;
    }
    return sum;
}

验证：

public static void main(String[] args) {
    int a = 4;
    int b = 2;
    int num = add(a, b);
    System.out.println(a + " + " + b + " = " + num);
}

2、位运算实现减法

思路：

a - b 等于 a + b的相反数（b取反 + 1），因此可以基于上述的add(int, int)函数扩展；

代码：

/**
 * a - b 等于 a + b的相反数（b取反 + 1）
 */
public static int minus(int a, int b) {
    return add(a, negNum(b));
}

/**
 * 获取n的相反数
 */
public static int negNum(int n) {
    // n取反 再 + 1
    return add(~n, 1);
}

验证：

public static void main(String[] args) {
    int a = 4;
    int b = 2;
    int num = minus(a, b);
    System.out.println(a + " - " + b + " = " + num);
}

3、位运算实现乘法

思路：

上小学我们学乘法的时候，老师教过我们一个方法：把乘法拆成加法，比如：12 * 34 = 13 * 4 + （12 * 3） * 10；

在位运算中其实也是一样的，可以通过加法和移位运算实现乘法；比如：1001 * 1010，可以拆分为：1001 * 1000 + 1001 * 0010；

在二进制运算中，1001 * 1000 等价于 1001 左移 3位，1001 * 0010 等价于 1001 左移 1位。

代码：

/**
 * 乘法
 */
public static int multi(int a, int b) {
    int res = 0;
    while (b != 0) {
        // b的二进制的最低位为1时
        if ((b & 1) != 0) {
            res = add(res, a);
        }
        // a 左移1位
        a <<= 1;
        // b 无符号右移1位
        b >>>= 1;
    }
    return res;
}

验证：

public static void main(String[] args) {
    int a = 9;
    int b = 10;
    int num = multi(a, b);
    System.out.println(a + " * " + b + " = " + num);
}

4、位运算实现乘除法（LeetCode 29题 两数相除）

1）题干

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

2）解题思路

1> 首先处理边界问题：

Integer.MIN_VALUE是没有绝对值的，因为其绝对值超过了INT整型的最大范围2 ^ 31 - 1，所以针对除数 和 被除数 是 Integer.MIN_VALUE时，需要做特殊处理；

1. 当 除数 为 32 位有符号整数的最小值 -2^31 时：
   • 如果 被除数 也是 32 位有符号整数的最小值 -2^31 ，返回结果：1
   • 其余情况，返回结果：0
2. 当 被除数 为 32 位有符号整数的最小值 -2^31 时：
   • 如果除数为 −1，则理论上答案应该为 2^31，但是产生了溢出，所以结果为 INT整型的最大值2^31 − 1
   • 其余情况，首先给 被除数 + 1，然后再做后续操作；
3. 当 除数 和 被除数 都不是 32 位有符号整数的最小值 -2^31 时：
   • 正常进行除法运算。

2> 处理 被除数 为 32 位有符号整数的最小值 -2^31 ，除数不为 -1的特殊场景：

在做除法时，我们一般选择先将负数都转换为正数 做除法，最后再加上符号位；

但是-2^31 转换为 正数 就溢出了，所以先对其进行 加一操作（-2^31 + 1 ），然后再完整的进行如下逻辑运算：

假设 被除数是 a（a = -2^31）， 除数 是b；

• 首先计算 (a + 1) / b，得到结果c，c表示a转换为正数最大值后 除 除数b的结果；
• 接着计算a - b * c，得到结果d，d表示a（-2^31）减去 除数b 乘以 （a转换为正数最大值后 除 除数b的结果）的结果；约等于再把最前面舍弃掉的1再加回来；
• 然后计算d / b，得到结果e，e约等于 1 / b；
• 最后的结果为c + e

3> 正常除法场景：

上小学我们学除法的时候，老师教过我们一个方法：把除法看做 减法 和 乘法的混合运算，先看取余运算：135 % 12 = （12 * 10 + 12 + 3）% 12 = 135 - 12 * 10 - 12 = 3；再看除法运算：135 / 12 = 10 + 1 + 3 / 12；

在位运算中其实也是一样的，区别在与我们平时的计算规则是10进制，位运算使用二进制；

采用加权累减实现除法；

假设现在要计算A ÷ B，A为a的二进制数，B为b的二进制数：

• 首先，如果我们选择将B左移，可能B左移时其中的1会超过符号位（导致B’ 变成负数），即溢出；所以此处选择右移A。

• 将A右移30位 --> 右移0位，假设过程中移动了k位，如果A右移了k位后开始 大于等于 B，则商累加（1 << k，即2^ (k-1)次方）；A = A - (B << k)，即A 减去 B 乘以 2^ (k-1)次方。

• 继续A右移过程，右移了k+1位、k+2位…重复上面的运算规则，直到右移0位为止。

• 最终的A则是余数。

3）代码

/**
 * 正常除法
 */
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;
    // x / y，因为y 左移可能其中的 1 会移超过符号位（变成负数），所以选择移动右移 x（右移不存在改符号位的情况、不会溢出）
    for (int i = 30; i >= 0; i = minus(i, 1)) {
        if ((x >> i) >= y) {
            res |= (1 << i);
            x = minus(x, y << i);
        }
    }
    return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
}

/**
 * 处理Integer的最小值（特殊情况）
 */
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 {
            // (a + 1) / b = c
            // a - (b * c) = d
            // d / b = e
            // res = c + e;

            // a + 1 除以 b
            int c = div(add(a, 1), b);
            // 答案为 ((a + 1) / b) + ((a - b * c) / b)
            return add(c, div(minus(a, multi(c, b)), b));
        }
    } else {
        return div(a, b);
    }
}

验证：

PS：加减乘除的效率问题

位运算实现的加减乘除效率大于高级编程语言层面的加减乘除；因为高级编程语言最终也要转换为汇编的位运算指令。

但是如果我们用Java自己写了一套基于位运算实现的加减乘除函数，其并不如JAVA自己的加减乘除（+、-、*、/）快；

• 因为JVM层面对JAVA自己的加减乘除符号做了汇编语言的转换；

• 如果我们自己用JAVA写的位运算 聚合函数（比如：加减乘除），又要经过几层的转换，反而更慢；

当然，单独的位运算符号肯定是更快的；