如何通过二进制位运算实现加减乘除

1. 引言

众所周知，计算机是通过 bit 位来存储数字的，因为每个 bit 位只能存储 0 或 1，因此，计算机底层的所有计算都是基于二进制来实现的。 那么，仅仅通过位运算，如何才能计算出数字的加减乘除呢？这是一个非常有意思的问题。 本文我们就来详细介绍一下。

2. 为什么要有原码和补码 — 计算机中数字的表示

对于一个非负数，用二进制来表示他是非常简单的，例如二进制的 0 就是十进制的 0，二进制的 1101 就是十进制的 13。 但是负数要如何表示呢？你一定会想，既然正数可以简单地表示，那么我们直接通过最高位上置 1 表示负数，0 表示正数就可以了。 也就是说，对于一个 byte 来说，0b 0000 0101 表示 5，0b 1000 0101 表示 -5，看上去确实是实现了负数的表示，但是这引入了一个新的问题，我们都知道 5 + (-5) 结果是 0，那么对于二进制加法 0b 0000 0101 + 0b 1000 0101 的结果也必须是 0，此时我们有两种办法来解决这个问题：

1. 实现加法、减法两套算法，在加法运算前先判断两个加数最高位的取值，然后将他们转换为整数的加减法再最终决定结果的最高位取值
2. 重新定义正数或负数的二进制表示方法，让 5 的二进制表示与 -5 的二进制表示只和刚好位 0

方法一的好处是负数的表示十分易于理解，但缺点是算法实现复杂度比方法二高很多。 方法二的好处是完全可以通过加法的算法来直接实现减法，只需要在进行加法前按照规则将减数转换为其相反数即可，但是缺点也很明显，就是负数的表示不再那么直观了。 综合考虑，由于二进制的表示仅仅是计算机在各种计算时使用的，在给用户呈现最终的结果时，用户无需了解其内在的二进制表现形式，因此方法二的缺点也就并不怎么明显了，所以最终计算机的实现都选择了方法二。 那么，我们如何定义一套新的负数表示方法呢？很简单，既然 0b 0000 0101 + (-5) == 0b 0000 0000，所以 -5 == 0b 0000 0000 - 0b 0000 0101 == 0b 1111 1111 + 1 - 0b 0000 0101 == 0b 1111 1011。 从 0b 1111 1111 + 1 - 0b 0000 0101 可以直接看出规律，因为 0xff - x 就是 x 的按位取反，整个过程就是正数的按位取反再加 1，这就是计算机中补码的计算方法。

因此取反操作为：

func neg(num int) int {
    return add(int(^uint(num)), 1)
}

2.1. 特殊情况

需要注意的是，因为 int 型的位数是有限的，因此会出现溢出的情况，例如对于 8 位 int 型来说 0b 1000 0000 表示 -128，将他按照计算补码的方式计算出其相反数即：0b 0111 1111 + 1 = 0b 1000 0000，仍然是 -128。

3. 加法的实现

有了上述的补码，我们计算加法时就非常轻松了，无需关注两个加数的符号问题，直接按位相加即可，那么我们如何来实现按位相加呢？ 我们来看看对于两个只有 1 位的加数其和符合什么规律呢：

上表中只有两个加数均为 1 时才比较特殊，如果我们不考虑进位，你会发现，和的结果刚好是异或的结果，而进位位的值和两个加数相与的结果是一致的，这样只要递归计算进位位与不考虑进位位的和的结果就可以得到最终的求和结果了。 接下来，我们需要考虑这个递归过程的终止条件以及是否会出现无限递归的可能呢？很显然，如果两个加数的任何一个为 0，我们直接返回另一个加数即可，这就是递归的终止条件，而两个二进制位的和可能出现的进位位只有可能是 10 或 00，即使每次递归，进位均不为 0，下一次递归的进位会以低位补 0 向高位移动，最终溢出使进位位最终为 0，最终实现递归的终止，从而不会出现无限递归的可能。 有了这个规律，我们就可以编写代码了：

func add(num1 int, num2 int) int {
    unum1, unum2 := uint(num1), uint(num2)
    if num1 == 0 || num2 == 0 {
        return int(unum1 | unum2)
    }
    return add(int(unum1^unum2), int((unum1&unum2)<<1))
}

4. 减法的实现

我们上面已经介绍了补码的表示与计算方法，根据补码的计算规则，一个数的相反数即按位取反再加 1。 对于减法而言，将减数转换为其相反数，再将他与被减数相加即可实现减法运算。

func sub(num1 int, num2 int) int {
    return add(num1, neg(num2))
}

5. 乘法的实现

乘法看上去非常简单，当两个乘数都是非负数时，用一个乘数循环加自己，加的次数是另一个乘数的值。

func mul1(num1 int, num2 int) int {
    result := 0
    isneg := num1 > 0 && num2 < 0 || num1 < 0 && num2 > 0
    if num1 < 0 {
        num1 = neg(num1)
    }
    if num2 < 0 {
        num2 = neg(num2)
    }
    for i:=0; i<num2; i=add(i, 1) {
        result = add(result, num1)
    }
    if isneg {
        return neg(result)
    }
    return result
}

这个算法的时间复杂度是 O(num2)，我们能不能在 O(1) 时间复杂度下计算出两个数的积呢？

5.1. 改进算法

我们知道，在我们计算十进制的乘法时，我们并不是通过反复增加被加数来实现的，而是通过列竖式的方法来实现的，那么二进制的乘法可以通过列竖式来解决吗？当然是可以的：

通过列竖式的方法，我们看到，通过每次将被加数左移一位，将加数右移一位，如果加数最低位为 1，那么就将移位后的被加数加到最终的结果中。

func mul2(num1 int, num2 int) int {
    isneg := num1 > 0 && num2 < 0 || num1 < 0 && num2 > 0
    if num1 < 0 {
        num1 = neg(num1)
    }
    if num2 < 0 {
        num2 = neg(num2)
    }
    unum1, unum2 := uint(num1), uint(num2)
    result := 0
    for unum1 != 0 && unum2 != 0 {
        if unum2 & 1 != 0 {
            result = add(result, int(unum1))
        }
        unum2 >>= 1
        unum1 <<= 1
    }
    if isneg {
        return neg(result)
    }
    return result
}

因为 int 型的 bit 位数是一个常数，所以上述算法时间复杂度是 O(1)

6. 除法的实现

当被除数和除数都是非负数时，除法的原理是用被除数反复减去除数，一旦结果小于被除数，那么减的次数就是最终的商，而这个结果就是余数。 最终，商的符号取决于被除数和除数的符号，而余数的符号总数与除数的符号相同的。

func div1(num1 int, num2 int) (int, int) {
    if num2 == 0 {
        return 0, 0
    }
    isneg, quotneg := num1 > 0 && num2 < 0 || num1 < 0 && num2 > 0, false
    if num1 < 0 {
        num1 = neg(num1)
    }
    if num2 < 0 {
        quotneg = true
        num2 = neg(num2)
    }

    result := 0
    for num1 >= num2 {
        result = add(result, 1)
        num1 = sub(num1, num2)
    }
    if isneg {
        result = neg(result)
    }
    if quotneg {
        num1 = neg(num1)
    }
    return result, num1
}

这个算法的时间复杂度是 O(num1) 的。

6.1. 改进算法

上述算法循环中，每次都用被除数减去除数，那么如果我们可以用被除数减去 n 倍的除数，商在原有基础上就可以直接加 n，算法时间复杂度就会大为缩减，那么，我们如何来确定 n 呢？ n 作为一个自然数，同样可以表示成 2 进制，例如 0b 1011 0101 = 2^7 + 2^5 + 2^3 + 2^2 + 2^0，也就是说，任何一个自然数，都可以表示成若干个 2^m 之和，而 m 的取值均不相同。 因此，根据乘法结合律，我们可以尝试用被除数依次减去 2^i，i 从大到小递减，一旦结果大于 0，那么就将 2^i 累加到商中，被除数再减去这个结果，直到这个结果小于除数，他就是余数，这样，对于有限位数的 int 型来说，算法时间复杂度就是 O(1) 根据乘法的结合律 0b 1011 0101 2 = (2^7 + 2^5 + 2^3 + 2^2 + 2^0) 2 = 2^8 + 2^6 + 2^4 + 2^3 + 2^1 = 0b 0110 1010，也就是说，乘以 2 的操作相当于左移一位。

func div2(num1 int, num2 int) (int, int) {
    if num2 == 0 {
        return 0, 0
    }
    isneg, quotneg := num1 > 0 && num2 < 0 || num1 < 0 && num2 > 0, false
    if num1 < 0 {
        num1 = neg(num1)
    }
    if num2 < 0 {
        quotneg = true
        num2 = neg(num2)
    }

    result := 0
    unum1, unum2 := uint(num1), uint(num2)
    for i:=31; i>=0; i = sub(i, 1) {
        j := unum1 >> uint(i)
        if j >= unum2 {
            result += 1 << uint(i)
            unum1 = uint(sub(int(unum1), int(unum2<<uint(i))))
            if unum1 < unum2 {
                break
            }
        }
    }
    num1 = int(unum1)
    if isneg {
        result = neg(result)
    }
    if quotneg {
        num1 = neg(num1)
    }
    return result, num1
}

上面的代码中，没有通过将除数左移再比较来实现，而是通过被除数右移再比较来实现的，原因在于将除数左移可能造成除数溢出，也就是移动后反而小于移动前，造成算法的错误。