底层的整数

在正式介绍汇编语言之前，我会先用几篇文章讲一些数学基础和硬件基础。如果读者已经具备了一定的知识基础，可以直接跳过这些文章去汇编语言部分。这一篇文章中，我将主要讨论“数”这一概念在底层的体现。

数的表示

在计算机底层的软件层面，我们通常采用二进制，八进制或十六进制来记录数字，其中最常用的是十六进制。所谓\(n\)进制，就是从0开始数，逢\(n\)进1. 比如说二进制，就是从0开始数，到1，然后到2的时候进1变成10. 八进制也是类似，但是到了十六进制就犯了难，我们的数字只有0到9这十个，并不能表示出16个呀，于是，我们默认使用了a到f这六个字母来分别表示10到15这六个数。也就是说，十进制数10对应的十六进制数是a, 十进制数26对应的十六进制数是1a. 在大部分计算机术语中，我们通常用0x开头表示十六进制，用0开头表示八进制，而没有前缀来表示十进制。因此，比如说以下的汇编代码（并不需要理解实际含义）

sub    sp, sp, #0x1a

与

sub    sp, sp, #26

的效果相同。

十进制数与十六进制数的转化可以在搜索引擎上找到，这里不再赘述。而八进制，十六进制数与二进制数的转换则十分简单。一个八进制数的一位代表一个二进制数的三位，比如说八进制数的一位5就代表二进制数的三位101; 同理，一个十六进制数的一位就代表二进制数的四位。因此，十六进制数0x2000001就代表二进制数0010000000000000000000000001.

我们知道，之所以使用二进制数，是因为计算机底层采用高电平/低电平这种方法来表示数。那么，我们为什么要使用八进制、十六进制呢？我们知道，如今的计算机大多采用64位系统，意思是说，任何一个地址都是一个64位二进制数。那么，如果我们只采用二进制来表示一个地址，那么得有64个0或者1, 这不仅让我们看花眼了，而且也极大的浪费了电脑的显示资源。而刚才讲到的十六进制数则帮我们解决了这个问题。我们知道，十六进制数的一位对应二进制数的4位。因此，一个\(n\)位二进制数，只需要\(\lceil\frac{n}{4}\rceil\)位十六进制数即可。也就是说，我们要表示64位的地址，只需要16位十六进制数即可。

整数的记录

进制问题解决了在计算机底层软件中数的表示问题，接下来还需要解决的是记录问题，也就是说，如何把数实际存储在寄存器中（下面以8位寄存器为例）。

一个最直观的想法，就是这个数是多少，就把它的二进制数存进寄存器中。例如，对于十进制数154，我们就在寄存器中存储二进制数10011010。这样，我们寄存器中可以存储的数的范围就是\(0\sim 2^{8}-1\)。

原码

但是，我们在日常的编程中，往往需要用到负数。按我们上面的做法，是没有办法存储这种符号信息的。解决这个问题，我们第一个想到的就是在这寄存器的8个位中，取一个位表示符号。例如，我们可以取最高位表示符号，1表示负数，0表示整数。那么，10011010就表示负的二进制数11010，也就是-26。在这种情况下，我们寄存器中可以存储的数的范围就是\(-2^{7}+1\sim 2^{7}-1\)。这种方式我们称作“原码”存储方式。

那么，所有整数都按上述方法用原码存储可以吗？我们知道，在编程中虽然会用到负数，但也会有许多情况只用到非负数（例如取数组下标的时候）。那么，如果用原码存储，我们只能用到\(0\sim 2^{7}-1\)这么多非负整数，比我们第一种不存储符号的方法少了接近一半可以用的数字，这让我们非常难以忍受。因此，我们需要提出一个共识：有符号整数与无符号整数共存！有符号整数，就是指其存储时包含了符号信息，就我们刚才所提出的方案来看，就是最高位存储符号；无符号整数则相反，其存储不包含符号信息，也就是我们提出的第一个方案，是多少就存多少，只能表示\(0\sim 2^{8}-1\)。

如果按原码存储有符号整数的方案，我们来考虑以下场景。寄存器A中存储了二进制数11100001，寄存器B中存储了二进制数00000111。按我们目前提到的方案来看，如果要计算加减，会变成这样：

  • 如果A和B存储的是有符号数

    A存储十进制数-97，B存储十进制数7。A与B相加为-90，二进制数为11011010；A与B相减为-104，二进制数为11101000。

  • 如果A和B存储的是无符号数

    A存储十进制数225，B存储十进制数7。A与B相加为232，二进制数为11101000；A与B相减为217，二进制数为11011010。

我们的CPU如果需要同时支持有符号数和无符号数的加减法，我们会发现，有符号数的加法与无符号数的减法得到的存储结果一致，反之亦然。如果按这种设计，我们需要在实现加法的时候首先判断是否有无符号，其次我们得同时实现加法器和减法器。

有没有更好的方法？

补码

我们来看看天才般的先行者是怎么做的。

下面，我们用\(\alpha=f(a)\)表示将整数\(a\)记录到寄存器中，其中寄存器的值直接转化成无符号二进制数为\(\alpha\)。例如，按照我们之前的说法，10011010就表示负的二进制数11010，也就是-26，那么，\(f(-26)=154\)，因为10011010直接转化为无符号二进制数就是154。

那么，我们之前讲的对于无符号整数的记录方法就很直接：

$$ \alpha =f_u(a)=a $$

我们该如何记录有符号整数呢？

首先，我们需要指出，由于寄存器的位数是有限的，因此对于一个\(n\)位寄存器来说，如果

$$ f(a)\equiv f(b)\pmod{2^{n}} $$

那么\(a\)和\(b\)存储到寄存器中时，是没法看出差别的（因为它们在寄存器中的表现是相同的），也就是说，可以认为\(a=b\)。

我们天才般的先行者提出了补码的概念，对于有符号整数的记录：

$$ \alpha =f_s(a)=\begin{cases} a&0\leq a\leq 2^{n-1}-1\\ 2^{n}+a&-2^{n-1}\leq a<0 \end{cases} $$

容易验证，对于两个寄存器中的值\(\alpha=f_u(a_u)=f_s(a_s)\)和\(\beta=f_u(b_u)=f_s(b_s)\)，我们有：

对于无符号加法：

$$ f_u(a_u+b_u)\equiv f_u(a_u)+f_u(b_u)=\alpha+\beta\pmod{2^{n}} $$

对于有符号加法：

$$ f_s(a_s+b_s)\equiv f_s(a_s)+f_u(b_s)=\alpha+\beta\pmod{2^{n}} $$

对于无符号减法：

$$ f_u(a_u-b_u)\equiv f_u(a_u)+f_s(-b_u)\pmod{2^{n}} $$

对于有符号减法：

$$ f_s(a_s-b_s)\equiv f_s(a_s)+f_s(-b_s)\pmod{2^{n}} $$

还是以我们之前的场景为例。寄存器A中存储了二进制数11100001，寄存器B中存储了二进制数00000111。按补码方案来看：

  • 如果A和B存储的是有符号数

    A存储十进制数-31，B存储十进制数7。

    A与B相加为-24，其补码为11101000，正好就是11100001+00000111=11101000。

    A与B相减为-38，其补码为11011010。其计算方法为，先求-7的补码，为11111001，然后再直接相加11100001+11111001=11011010。

  • 如果A和B存储的是无符号数

    A存储十进制数225，B存储十进制数7。

    A与B相加为232，在寄存器中为11101000，正好就是11100001+00000111=11101000。

    A与B相减为218，在寄存器中为11011010。其计算方法为，先求-7的补码，为11111001，然后再直接相加11100001+11111001=11011010。

由此可见，在这种方法下，无论将寄存器中的值看作有符号数还是无符号数，其加法与减法都只需经历相同的运算，并且得到的结果在寄存器中相同。也就是说，我们只需要实现一个加法器（以及一个求补码的器件），就可以实现所有有符号数与无符号数的加减法了。

提到有符号整数与无符号整数，我们有一点需要知道。在寄存器中存储的数本身，讨论其是有符号整数还是无符号整数是没有意义的。举个例子，我们有一个8位的寄存器，其内容为二进制数10001111。这个寄存器内的数有符号吗？答案是它不含符号信息。它既可以是有符号整数-0x71，也可以是无符号整数+0x8f。按我们上面所讲的补码的优势可以看出，CPU在进行两个数相加减的时候，是不需要知道处理的数究竟是有符号数还是无符号数的（事实上，CPU是将处理的数同时看作无符号整数与有符号整数来处理的，不过在这里不影响我们的讨论）。也就是说，在某种意义上，CPU是完全不知道存储在寄存器里的值是有符号的还是无符号的。

溢出

在讨论补码的时候我们提到，由于寄存器的宽度是有限的，因此一个寄存器能表示的数是有限的。这就带来了溢出的问题。

什么是溢出呢？具传言（内容引自萌娘百科）：

在初代《文明》中，印度的基准好战度为1，是整个游戏最低的；然而，当玩家在游戏中选择市政“民主政治”(Democracy，效果为所有AI好战度-2)时，会导致数据溢出，从而使甘地的好战度涨为255，使得印度一跃成为全游戏最好战的文明；再加上该作科技树上解锁该市政的科技与解锁核武器的科技位置十分接近，导致游戏中后期印度十分喜欢造核弹扔核弹，自此初代印度领袖莫罕达斯·甘地得名“甘核平/核平使者”。

下面，我们假设在这款游戏中，好战度的值被存储在一个8位的寄存器中。那么，基准好战度为1时，寄存器中的值为00000001。当对其减2时，按照我们上述求减法时的算法，可以得出在寄存器中的值为11111111。如果这个寄存器的值在程序中被视为无符号整数，那么它的值就是255，也就是最大的无符号整数的值了。

这就是溢出的问题。由于寄存器能表示的数是有限的，因此如果不对进位进行判断，那么加减法产生的溢出会造成一定的安全隐患。

在《文明》的例子中，实际上是由减法借位产生的下溢出。那么，有没有相应的上溢出的例子呢？

在初学ASCII码的时候，我想看一看所有的ASCII码对应的字符长什么样。因此，我写了如下的C语言代码：

for (unsigned char ch = 0; ch <= 255; ch++) {
   printf("Char with ASCII %d is %c\n", ch, ch);
}

上面这个代码存在问题吗？把上述代码编译运行一遍会发现，它 停 不 下 来！

为什么会产生这种情况呢？当ch为255时，循环结束会进行ch++的操作，而unsigned char类型的ch值255在寄存器中存储的形式为11111111，对其加1，按照我们之前加减法的法则，会得到00000000，会被程序看作0，仍然不满足循环终止的条件，因此这个循环会停不下来。这就是由上溢出产生的问题。

整数的逻辑运算

除了加减乘除以外，二进制整数还有独特的运算——逻辑运算，分别是与(and), 或(or), 非(not)和异或(xor)。其运算规则相信大家都已经很了解了。

这里要特别指出，如果把一个寄存器与自身异或，效果会是怎样的呢？例如：

eor    w0, w1, w1

上述汇编代码的含义是，将w1寄存器的值与自身异或，将结果存储于w0中。

在这条汇编指令执行之后，w0的值会是多少呢？按照异或的规则，两个相同的值异或结果为0。因此，无论w1的值是多少，在这条指令执行之后，w0的值始终为0。

在某些CPU指令集架构下，编译器会倾向于使用这种指令来将寄存器的值清零。

在污点分析中，我们想探索某个寄存器的值最终被传播到了哪些内存地址上。但如果遇到这种指令时，目标寄存器的值被清空，我们就不需要继续跟踪这个寄存器了。因此，这种指令也是特殊的“漂白指令”。