二进制的计算

Unisky大约 5 分钟

二进制的计算

1.无符号数二进制表示

就是最常见的二进制表示法，对于一个字节的八位数（1B=8bit），可以储存0~255的无符号数。

2.有符号数二进制表示

众所周知，有符号的二进制数的表示法包括原码、反码和补码。其中补码是计算时最为常用的表示类型。在计算机系统中，二进制数全部用补码来表示。若为有符号数，最高位为符号位。

对于正数，原、反、补码均相同，符号位为0

对于负数，原码符号位为1，反码为对原码除符号位全部取反（即进行~运算），补码在反码的基础上+1，若进位到符号位，则溢出，再往上进位需要舍去。

对于一个字节，原码和反码可以储存-127~127，补码可以储存-128~127

以下是常见的原码反码补码类型表示（使用八位表示）

十进制数	原码	反码	补码
+69D	01000101B	01000101B	01000101B
-35D	10100011B	11011100B	11011101B
-128D	/	/	10000000B
+127D	01111111B	01111111B	01111111B
+0D	00000000B	00000000B	00000000B
-0D	10000000B	11111111B	00000000B

TIPS

补码多出的一位的原因是，在补码中的正0和负0的表示形式完全相同。
-128没有原码和反码,有特殊的补码
B=Binary，O=Octal，D=Decimal, H=Hexadecimal，分别表示二、八、十、十六进制数

3.有符号数二进制计算

对于有符号数的加减计算，我们直接使用补码相加的方式进行计算

例如（为了方便，此处使用五位表示，最高位为符号位）：

注：该表示法下表示的数为 -16 ~ 15

3D+5D=8D，直接转换，补码相加，00011B+00101B=01000B
9D+8D=17D?，由于17已经超出了表示上限，所以该计算会导致溢出，实际的运算情况如下：01001B+01000B=10001B，10001B的原码是11111B，所以得到的实际结果是-15
5D-7D=-2D，减法运算转换成加法运算是5D+(-7D)，所以实际运算情况是00101B+11001B=11110B，11110B(补)=10010B(原)

4.不使用四则运算实现二进制计算

现在我们知道了补码计算的流程，现在我们关注计算过程，也就是对二进制这一个相加的过程进行关注。我们可以用小学竖式来直观地展现这个计算过程，以5D-7D=-2D为例，就像这样

\begin{array}{r} 00101B\\ +11001B\\ \hline 11110B \end{array}

假设有两个二进制数 $P,Q$ ,结果为 $R$ ，且 $P[i]$ 表示从低位到高位的第i位，在不考虑进位的情况下，我们可以发现， $R[i]=P[i] \odot Q[i] = \neg (P[i] \oplus Q[i])$ ，而上一位存在进位的情况下，由于只会进一位，所以此时 $R[i]=P[i] \oplus Q[i]$

假设我们再加一个二进制数 $S$ 用于表示进位情况，将需要进位的位标为1，那么我们可以得到进位情况，PQ在最高位时则不考虑进位

S[i+1] = (P[i] \land Q[i]) \lor (P[i] \land S[i]) \lor (Q[i] \land S[i])

这样我们就可以实现通过二进制数的位运算继而实现整体数的运算。

但是这样还不够，我们能不能继续将这个计算更简化一些呢？

对于5D-7D=-2D， $P=00101B, Q=11001B, R=11110B, S=00010B$ 很显然，此时 $R= P \oplus Q \oplus S$ ，说明我们想要完成这个计算，最重要的就是把 $S$ 算出来

直接对两个加数进行位运算可以得到每一位的相加情况是否会对下一位进位，但是此时能够绝对明确进位情况只有最低位，因为其他位还需要考虑上一位的进位情况，并不能直接得到 $S$ 。我们来举一个更合适的例子来探讨这个问题

7D+3D=10D， $P=00111B,Q=00011B$ ,实际的 $R=01010B,S=01110B$ ,进行第一次位与运算，得到 $S_0 = 00011B$ ,因为 $S_0$ 对应的进位情况是偏了一位的，所以对 $S_0$ 进行一次左移得到 $S_0'=00110B$ ，显然第四位应当进位却没有标为1。我们没有办法一次性将正确的 $S$ 加到上面，但是我们可以考虑逐次计算进位。

首先计算 $P \oplus Q$ ,得到 $R_0 = 00100B$ ，那么问题就变成了00100B+00110B,这样思路就很明确了，按照这样的步骤不断加下去，直到不再产生进位为止(即 $S_n=00000B$ )，最后得到的 $R_n$ 就是我们需要的 $R$

我们从头开始来继续完成上面这个例子

$P_0=00111B,Q_0=00011B,R_0=P_0 \oplus Q_0=00100B,S_0=(P_0 \land Q_0)<<1=00110B$
$P_1=R_0=00100B, Q_1=S_0=00110B, R_1 = P_1 \oplus Q_1 = 00010B, S_1=(P_1 \land Q_1)<<1=01000B$
$P_2=R_1=00010B, Q_2=S_1=01000B, R_2 = P_2 \oplus Q_2 = 01010B, S_2=(P_2 \land Q_2)<<1=00000B$
$R=R_2=01010B$

使用java表示则是如下代码块

/**
 * A,B,C分别对应上文的P,Q,S
 */
public int binaryCalculation(int dataA, int dataB){
    while(dataB!=0){
        int dataC = (dataA & dataB) << 1;//位与+左移
        dataA = dataA ^ dataB;//位异或
        dataB = dataC;
    }
    return dataA;
}

5、来试一道算法题看看？

试试这一道题open in new window

题解与上述内容基本完全相同，不再过多阐述。