写在前面
本人理解可能有所偏差，为了避免被误导，建议配合原书理解
由于原书中内容存在大量预定义公式及向量运算，本文中会尽可能避免出现原文表达方式，以便理解，但如果需要理性理解的话建议去记原书的公式。本文也可能出现大量本文作者抽象的理解
本篇文章没有任何一名幸运玩家惨遭封号
上一回我们说到，一切数据在计算机眼里都是二进制，整型也不例外。由于这部分涉及到大量的二进制运算，所以，有关计算的部分，就拜托小娜……
还在摸鱼啊……不是？你开挂一般的脑子都打不过的吗……
娜：上一个账号因为我物像锁定参数没调整好，被VAC制裁了，这是新账号，分段很低，队友一个比一个不给力，唉（叹气）。
以后操作的像人一点不就行了吗……等等，你上一个账号用的不是我的吗……
（气氛一度降到了冰点）
算了，反正那个号的库存只有个位数，我们继续正题吧……
整数在计算机的表示
不论是什么机器，什么语言的编程，都脱不开一个很重要的数据类型——整型。在python中，整形的定义其实非常宽泛，但在C中，整形被加以了严格的区分。除了区分长度的关键字short和long，在32位和64位编程中的整形大小int32_t和int64_t（两者的大小差别本质上取决于对象占用的字节大小，32位机器整数占4字节，而64位占8字节）以及某种达到C语言单个对象最大长度不知名物体size_t，还有定义是否产生正负号的无符号关键字unsigned（在int32_t/int64_t中简化为前缀u）。至于其具体大小，各位可以自行百度或者查看原书，本文不再赘述。
如果要谈整数怎么表示的，我们可以先从简单一点的部分谈起：
无符号整型
相信各位已经在大学甚至高中的微机课上学过原码、反码、补码的概念了。对于一个整数在计算机中的二进制表示来讲，无符号相当于正整数的原码，但是把符号位扬了。二进制每一位对应十进制大小都是2的((位数-1)次方)。相应的，十进制整数就相当于对应二进制为1的每一位的次方和。比方说，13=8+4+1=2^3+2^2+2^0，那么其对应二进制就是1101。
而对应每一个正整数，都有一个与之唯一对应的无符号整形。故此，无符号整形在内存空间之内的正整数区间是满足双射（即变量与函数值之间互相仅存在唯一的映射）的。
可是我们不止要表示正整数，还要表示负整数。那么，就该搬出我们经常用到的——
补码编码
等下，这……这不对吧？不是应该讲正常整形了吗？怎么还开始复习了呢？
好吧……欸等下你一直拿手柄打fps的吗？！
大家应该都还记得，所谓补码，正数与原码相同，负数则除了符号位全部按位取反。
好了，理论上来讲，我们已经明白“补码编码”是什么了。但是由于其作为编码的特性，还是要注意一下：
1、补码的范围并不对称。细心的同学应该已经发现了，理论上来讲，补码的符号位在其为负值的时候为1，也会使其被“错误”地被看待为一个最高的数值位。这使得补码的实际下限要比实际上线多1个整数。
2、在占用字节范围内，最大的无符号数约等于最大的补码的两倍。
为了防止在各个系统中调用的混乱，往往需要一个规范化的定义。C中的库<limits.h>就规定了有、无符号整型的相关区限，这部分内容在书中也提及了。
有无符号数之间的那些事
理解了补码，我们也就明白了有符号数怎么来的。所以，在C中，当我们进行强制类型转换，数值的解释方式会发生变化，无符号转有符号，原先的最高位会被当作符号位看待，而其余二进制位会在最高位为1的前提下当成被反转过的进制位看待；有符号转无符号，原先的符号位会被看成最高二进制位，如果符号位正好表示负数，那么你会得到一个very big的整数。理性理解建议看书，这里跳过公式与其解释、推导部分。
那原书写的肯定比我这里讲的详细多了QAQ，笔记一般都是导读和概括嘛awa
娜：ᗜ ‸ ᗜ 盯~~~~~
好吧我摊牌了，我真的不想用md写公式。
不管怎么说，不论有无符号如何变换，所表示的数据的二进制位都必须是保证不变的。这是大多数系统进行类型转换时遵循的底层逻辑。
在C语言中，定义无符号常量需要添加大写或小写的”u”作为后缀，而python因为没有严格意义上的常量，自然不用太在意这个问题……应该。
此外，C的运算式但凡和无符号沾上边，那么整个运算式中的变量都会被当作无符号数看待，这点在位运算时尤其小心。
但是要在长短整型之间变换怎么办
我们在使用C的实际编程中绝对会遇到变量类型转换的问题，不单是上述的有无符号转换，还有变量占用字节长的转换。往往，对于一个公用变量，一些函数为了各种理由需要用到短整型（short int），而一些函数为了运算方便又要用长整形（long int）之类的。这种时候……
我们就要来介绍一下我们的压缩变量，遇到数据变答辩糕，鲁棒性很强的，打开以后，是一个加大加厚的变量，你看他怎么塞都塞不坏，好不掉速不乱码，使用114514次都没问题……
好好好，玩梗呢，姑奶奶您消停消停……
不过嘛，跟压缩毛巾一个道理，我们如果将大变量转换为小变量，广义上讲，那需要经历一些复杂的过程，毕竟，这不是C语言的底层逻辑能够实现的，典型的例子就是高精度运算，将大整数封装到变量类型占字节较小的数组中去。
但是，狭义上讲，也就是从位运算的角度上讲，这件事根本不可能。除了可能会碰到的符号位问题外，最根本的问题就是前缀位丢失，即超出短变量型的部分被当场截断，这是不可避免的。截断的具体定义可以查阅原书，念师傅不想拿md写公式，先不提了。
但是，从小变大，那的确很好做。在位运算上，我们只要往开头补0补到相应大小即可……对于无符号数是这样的。有符号数，也就是补码数字可能有点小麻烦，我们需要往前补的是符号位。
很简单，抛开公式谈，因为对于一个有符号数的位向量表示，其因为是补码，符号位为1的时候代表负数，其余位反转，所以，如果向大的变量型转变，理论上其原码的补充前缀除了符号位全部为0，在符号位为0的时候自然不用变动，但在为1的时候需要将这些0全部反转，这种特性又巧合地使得填充的位与符号位保持一致。
额……这比喻也不能说不对吧……等下，你不是计算姬嘛，怎么我们俩的解释方式还反过来了？
你别……算了你继续欸嘿吧
整数的运算
我们现在知道如何表示各式各样的整数了，那么，开算吧！
加法
无符号就是正常的位运算加，略过。
带符号的话在二进制上就非常麻烦了。既然是在计算机中，我们不可能真正像正常位运算减那样理解计算机是怎么算的。书上给出的内容是这样的：
将其参数转换为无符号数，执行无符号数加法，再将结果转换成补码
什么意思呢？首先两个带符号数，也就是补码形式表示的整数，先将其转换为原码进行数值位相加，然后再随原码数值位表示的数值大者安排符号位，接下来转换成原码。整个过程的结果看上去经历了“数值位不经转换直接相加，符号位随绝对值大者决定”的过程，其实这么想，计算机也不是不能实现，但是，现行标准经不起自定义的折腾，这会让你的程序兼容性大打折扣，而且，这种精心安排的运算规则还与接下来要讲的事情息息相关：
加法溢出
当然，如果加法都像看上去那么简单就好了，但这里是《深入理解计算机系统》，计算机的整数是有上限的，突破了就会溢出。很惨的是，C的溢出并不会报错，所以我们应当尽可能理解，然后避免。
所谓溢出，就是数值在运算时突破了其既定的位长上限，对于二进制位上限为w的数，这种突破在无符号数上表现为数值因大于2的w次方而无法被正常存储，故而溢出到设定的内存空间之外。带符号的就更麻烦了，不论正负都会溢出，并且由于符号位的存在，上下限被压缩到了2的w-1次方。
所幸加法的溢出判定还算好做，书中提供了一些公式和手法，这里简单说明一下，由于两个无符号二进制位上限为w的数的和不可能超过2的w+1次方，我们只需要预估计算结果是否会存在于[2^w,2^w+1)的区间内部。至于有符号数同理，只不过，注意符号位和上下限同时判断（其实取绝对值对人会省事很多，但对计算机来讲不一定省事）
当然，变量的溢出和pwn常见的数组的溢出是两码事，这点在后面会提到。
补码的非
大于整型区间下边界的数x，其加法逆元等于其非，即-x，若位于下边界，则加法逆元就等于下边界。为了防止下边界溢出导致数据错乱，而加法逆元在符号上表示为负，故而在处理下边界相加的时候会直接令下边界减去其加法逆元，令其和其它数的逆元相加一样直接=0。
乘法
自然，乘法本质上作为数个相同数的相加也被纳入整数计算大军，只不过还是要考虑溢出问题。
无符号很简单，乘法，算溢出的时候模个2的w次方，然后判断的时候甭用区间直接看上界，完事。
有符号有了之前的经验也轻松很多，不就是累加吗，补码和原码在二进制上不是有很强的一致性，补转原，数值乘，模去边界，然后补上双方符号位的或，完事。
但是，实际上并没有这么轻松。原理上，对于两个任意整数，其无符号表示下的乘法在固定表示位上限的情况下与带符号乘法在二进制表示上相同。这点在书中有推导，简单来说就是将二者分解为数值位和符号位，相乘后对上界取模，简化的结果相等，这点可以自行翻书。
而除此之外，乘以常数有着一套独立的操作机制，就是乘以常数对二的幂次方的分解。还记得我们上回提到过的东西吗？
此外，对于位运算，C还提供了移位操作：左移（<<n）和右移（>>n），效果上对应整形十进制运算的乘2的幂次方和除以2的幂次方，实际上则分别对应着所有二进制位增n位并末尾补0，和所有二进制位降n位并取整。
对于一个已知的整数，我们不需要太麻烦的操作，或者说，不需要太麻烦计算机的操作。
我们只需要把整数拆分成若干互不相等的2的n次幂的和，然后进行一个乘法分配律，完事，计算机算二进制反而是最快的。
当然，乘法也是有溢出上界的，有符号就是2的2(w-1)次方，无符号就是2的2w次方。
除法，但是只能除2的幂
但是整数除法比较好实现的就只有二进制算数右移了，不然就扯到下一节的浮点数了。
对于一个整数除以2的幂，在整数部分一般是无符号前缀补0，有符号前缀补符号位，正如前面提到的一样。但是，处理余数是个很头疼的东西。下取整还好说，毕竟C的移位默认就是下取整，省的操作余数。但是上取整呢？
我们引入偏置的概念，即对于一个数的向右位移k位，我们首先对该数二进制的k位后缀，加上一个二进制1拉满的数，即对于1位位移，原数+1；4位位移，原数+15(1111)，8位位移，原数+255(11111111)，etc。如此一来，就算产生余数，我们也能绝对保证上取整了。至于详细原理可以看原书推导，这里不细讲。
所以，很难说计算机的整型运算导致了什么。它确实让计算机更快了，但也让程序员更痛苦了，不止是理解上，还在于堆屎山的问题上。“特性”的叠加会让程序产生意料之外的状况，而这种状况的冲突往往就体现在整型的特性上，比方说那个让B站程序员痛苦了彻夜的GCD。
下一篇，我们将提到浮点数相关的内容。所以，还是那句话：
