二进制乘除法的实现

深碍√TFBOYSˉ_ 2022-06-08 12:10 102阅读 0赞

转自：http://www.cnblogs.com/zuoxiaolong/p/computer10.html

### 引言 ###

运算一直是程序运行当中一个重要的环节，而在二进制的运算过程当中，加法运算又是重中之重，它基本上奠定了二进制运算的基础。因为无论是减法还是乘法，都可以由加法运算来替代，唯有除法不能由加法替代。

了解计算机运算的规律，可以有助于我们理解很多程序代码上无法理解的内容。比如上章提到的溢出问题，在了解了加法运算的原理之后，相信猿友们都可以轻松的知道为何有些运算会得到意想不到的结果。

这里还需要提一点的是，不同的处理器所采取的运算方式可能是有细微的差别的，因此也不能一概而论。因此我们大多时候会尽量讨论运算的抽象数学特性，抽象的东西大部分时候总是可靠的，这种特性为跨平台提供了基础，不过也并非总是如此，毕竟LZ只听说过浮点数运算标准，还没听说过整数运算标准，不知道究竟是LZ孤陋寡闻了，还是确无此物。

正因如此，我们了解一下这些运算的抽象性，会有助于我们理解程序代码级无法理解的东西。

### 无符号乘法 ###

无符号的乘法与加法类似，它的运算方式是比较简单的，只是也可能产生溢出。对于两个w位的无符号数来说，它们的乘积范围在0到(2w\-1)2之间，因此可能需要2w位二进制才能表示。因此由于位数的限制，假设两个w位的无符号数的真实乘积为pro，根据截断的规则，则实际得到的乘积为 pro mod 2w。

### 补码乘法 ###

与加法运算类似，补码乘法也是建立在无符号的基础之上的，因此我们可以很容易的得到，对于两个w位的补码数来说，假设它们的真实乘积为pro，则实际得到的乘积为 U2Tw(pro mod 2w)。

上面的式子我们有一个假设，就是假设对于w位的两个补码数来说，它们的乘积的低w位与无符号数乘积的低w位是一样的。这意味着计算机可以使用一个指令执行无符号和补码的乘法运算。

在书中给出了这一过程的证明，我们来大概看一下，这里主要应用了无符号编码和补码编码的关系，其中x’和y’分别代表x和y的补码编码。

![29005027-4600ad9c78624c31acee38cf299b35d5.jpg][]

这里运用的主要技巧就是2w mod 2w = 0。

### 乘法运算的优化 ###

根据我们小学所学的乘法运算，我们知道，假设两个w位的二进制数相乘，则需要进行w次与运算，然后进行w - 1次加法运算才能得到结果。从此不难看出，乘法运算的时间周期是很长的。因此计算机界的高手们想出了一种方式可以优化乘法运算的效率，就是使用移位和加法来替代乘法。

上述优化的前提是对于一个w位的二进制数来说，它与2k的乘积，等同于这个二进制数左移k位，在低位补k个0。在书中对这一等式进行了证明，过程如下。

![30000132-d89e0bf436a249869b5509233c7e22fd.jpg][]

这个过程主要应用了无符号编码的公式，各位猿友应该不难看懂。

有了上面的基础，我们就可以使用移位和加法对乘法优化了。对于任意一个整数y，它总能使用二进制序列表示（假设不超过二进制的表示范围），因此我们可以将x和y乘积的二进制序列表示为如下形式（此公式在书中没有展现）。

x \* y = x \* (yw-12w-1 + ... + y020) =  (x << w-1) \* yw-1 \+....+ (x << 0 ) \* y0

我们举个例子，对于x \* 17，我们可以计算x \* 16 + x = (x << 4) + x ，这样算下来的话，我们只需要一次移位一次加法就可以搞定这个乘法运算。而对于x \* 14，则可以计算 x \* 8 + x \* 4 + x \* 2 = (x << 3) + (x << 2) + (x << 1) ，更快的方式我们可以这么计算，x \* 16 - x \* 2 = (x << 4) - (x << 1) 。

这里最后需要提一下的是，加法、减法和移位的速度并不会总快于乘法运算，因此是否要进行上面的优化就取决于二者的速度了。

### 无符号除法 ###

除法与乘法不同，它不满足加法的分配律，也就是设y = m + n ， x/y != x/m + x/n。而且不幸的是，它有时候会比乘法运算更慢，但是我们只能针对除数可表示为2k的除法运算进行优化，转换为算数右移或者逻辑右移k位的运算（无符号数为逻辑右移，为正数时，逻辑右移与算术右移效果一样）。

由于是除法，因此我们会涉及到舍入的问题。这里定义└x/y┘的值为a'，x/y为a，则对于a'，它是唯一一个整数，满足 a' =< a < a'+1。

比如└2.1┘的值就为2，而对于└-2.1┘则为-3，如果本身就是整数，则等于自身。

书中给出了无符号数除以2k等价于右移k位（w > k >= 0）的证明，这一证明过程相对比较复杂一点，LZ这里给出一个相对简单的证明方式，不采用书上的证明。如果各位看LZ的证明看不懂的话，也可以参照一下书上的方式。

我们假设对于一个w位的无符号数来说，假设它的位表示为\[xw-1....x0\]，则x = xw-12w-1 + .... + x020 。因此就有以下结果。

x/2k = xw-12w-1-k +... + xk20 + xk-12\-1 +...+ x02\-k = B2Uw-k(\[xw-1....xk\]) + xk-12\-1 +...+ x02\-k

由于xk-12\-1 +...+ x02\-k <= 2\-1 + .... 2\-k = (1-(1/2)k) < 1 （这里是证明的关键一步，先假设所有位为1，则利用等比数列求和公式即可得到），因此有└xk-12\-1 +...+ x02\-k┘ = 0。

因此我们可以得到└x/2k┘ = └B2Uw-k(\[xw-1....xk\])┘ + └xk-12\-1 +...+ x02\-k┘ = └B2Uw-k(\[xw-1....xk\])┘ = B2Uw-k(\[xw-1....xk\]) = x >> k。

更直观的，我们可以使用程序验证这一结果，看下面的Java代码。

![复制代码][copycode.gif]

public class Main { public static void main(String[] args) { int a = 17; int b = 8; int c = a/b; System.out.println("a:" + Integer.toBinaryString(a)); System.out.println("b:" + Integer.toBinaryString(b)); System.out.println("c:" + Integer.toBinaryString(c)); System.out.println("a >> 3:" + Integer.toBinaryString(a >> 3)); } }

![复制代码][copycode.gif]

这段程序的结果如下，可以看出a/b的结果就是a右移3位的结果，也就是结果等于a >> 3。

![30013544-d1ef5c73010240e8a792d1e536710a1a.jpg][]

### 补码除法 ###

由于刚才我们的程序使用的都是正数，因此虽然Java中没有无符号数，不过我们可以模拟出无符号数的效果。也可以认为，补码除法在被除数为正数的情况下，与无符号编码是一样的效果（我们不考虑除数为负的情况，因为被除数与除数的符号位可以相互抵消，以下也一样），不过当被除数为负数时就不同了。这里在介绍补码除法之前，我们先来看一下，当a为负数时的结果，也就是此时会采用补码编码。

我们将刚才的程序稍微修改一下，如下。

![复制代码][copycode.gif]

public class Main { public static void main(String[] args) { int a = -17; int b = 8; int c = a/b; System.out.println("a:" + Integer.toBinaryString(a)); System.out.println("b:" + Integer.toBinaryString(b)); System.out.println("c:" + Integer.toBinaryString(c)); System.out.println("a >> 3:" + Integer.toBinaryString(a >> 3)); System.out.println("c:" + c); System.out.println("a >> 3:" + (a >> 3)); } }

![复制代码][copycode.gif]

它得到的结果如下，有点出乎意料。

![30015001-7cfaa326a9884795a9249b3eb87ffc24.jpg][]

这次为了便于观看，我们将c和a >> 3的整数值打印了出来，发现移位运算的结果是-3，而a/b的结果为-2。可以看出我们a/b的结果是我们所期望的，可是移位的运算结果似乎在舍入的时候出现了问题。

其实这个问题出现的原因很简单，补码编码与无符号编码类似，对于位表示都有└x/2k┘= B2Tw-k(\[xw-1....xk\]) = x >> k。不过此时由于是负数，所以采取了向下舍入。上面已经提到过└-2.1┘的值为-3。

因此，我们得到这样一个结论，当有舍入发生时，将一个负数右移k位不等价于把它除以2k。

### 除法的补救 ###

既然在舍入时，一个负数右移k位不等价于把它除以2k。那么为了使用这种优化，计算机界的大神们自然要想办法解决这个问题。于是他们想出了一个办法，即“偏置”这个值（不得不佩服这些大神们）。

首先我们定义┌x/y┐的值为a'，x/y为a，则对于a'，它是唯一一个整数，满足 a'-1 < a <= a'。

在上面的定义基础上，“偏置”的含义就是，我们有┌x/y┐ = └(x+y-1)/y┘。这一过程的证明不难理解，我们假设x = ky + r（我们考虑r > 0 ，此时会有舍入发生），则有。

└(x+y-1)/y┘ = └(ky+r+y-1)/y┘ = k + └(r+y-1)/y┘ = k + 1

可以看出在做了这个处理之后，也就是将x加上y-1的偏移量，此时在舍入时，结果会在原来的基础上加1。这也正是“偏置”的含义所在，它会将舍入“偏置”到向上舍入。

下面我们将补码除法当中的程序按照这种方式修复一下，看是不是这个结果，如下。

![复制代码][copycode.gif]

public class Main { public static void main(String[] args) { int a = -17; int b = 8; int c = a/b; System.out.println("a:" + Integer.toBinaryString(a)); System.out.println("b:" + Integer.toBinaryString(b)); System.out.println("c:" + Integer.toBinaryString(c)); System.out.println("(a+b-1) >> 3:" + Integer.toBinaryString((a+b-1) >> 3)); System.out.println("c:" + c); System.out.println("(a+b-1) >> 3:" + ((a+b-1) >> 3)); } }

![复制代码][copycode.gif]

此处我们将a“偏置”，也就是加上b-1的偏移量，我们来看结果。

![30023652-58d900482e0440dc8b5f0f78e6f48658.jpg][]

可以看出，在偏置之后，在负结果舍入时，移位运算的结果将会是我们期望得到的，这样我们便可以使用这一技巧进行优化了。

[29005027-4600ad9c78624c31acee38cf299b35d5.jpg]: /images/20220608/31aa85bf8a3f440899a1bea06a7e786e.png
[30000132-d89e0bf436a249869b5509233c7e22fd.jpg]: /images/20220608/0826cd3410194ff0a52cf70c13daaaa8.png
[copycode.gif]: /images/20220608/7c0f65f7991643d293ed66f44500892f.png
[30013544-d1ef5c73010240e8a792d1e536710a1a.jpg]: /images/20220608/040a553c763d406bacdebf58357c391d.png
[30015001-7cfaa326a9884795a9249b3eb87ffc24.jpg]: /images/20220608/7ae4c052c46f470fa76a34579a6e5994.png
[30023652-58d900482e0440dc8b5f0f78e6f48658.jpg]: /images/20220608/a9991665095f48ec904c3add42ad6e01.png