信息的表示和处理
(0 & 1) + interpretation = everything.
现代计算机存储和处理的信息以二值信号表示。二值信号能够很容易地被表示、存储和传输。当把位（bit）组合在一起，再加上某种解释（interpretation），即赋予不同的可能位模式以含义，我们就能够表示任何有限集合的元素。
“很容易地被表示、存储和传输” => 高低电压。
通过研究数字的实际表示，我们能够了解可以表示的值的范围和不同算术运算的属性。为了使编写的程序能在全部数值范围内正确工作，而且具有跨越不同机器、操作系统和编译器组合的可移植性，了解这种属性是非常重要的。大量计算机的安全漏洞都是由于计算机算术运算的微妙细节引发的。在早期，当人们碰巧触发了程序漏洞，只会给人们带来一些不便，但是现在，有众多的黑客企图利用他们能找到的任何漏洞，不经过授权就进入他人的系统。这就要求程序员有更多的责任和义务，去了解他们的程序如何工作，以及如何被迫产生不良的行为。
研究的目的。
不仅仅需要正向地去了解如何让程序正确地工作，也要反向地去了解如何迫使程序产生不良的行为，这可以更好地帮助理解底层的工作原理。
从编码的基本定义开始，然后得出一些属性，例如可表示的数字的范围、它们的位级表示以及算术运算的属性。从这样一个抽象的观点来分析是很重要的，因为程序员需要对计算机运算与更为人熟悉的整数和实数运算之间的关系有清晰的理解。
不仅仅需要了解当前的设计是怎么样的，还要了解为什么这样设计，分开看待具体和抽象。
信息存储
大多数计算机使用8位的块，或者称为字节（byte），作为最小的可寻址的内存单位，而不是访问内存中单独的位。机器级程序将内存视为一个非常大的字节数组，称为虚拟内存（virtual memory）。内存的每个字节都由一个唯一的数字来标识，称为它的地址（address），所有可能地址的集合就称为虚拟地址空间（virtual address space）。
编译器和运行时系统将存储器空间划分为更可管理的单元，来存放不同的程序对象（program object），即程序数据、指令和控制信息。每个程序对象可以简单地视为一个字节块，而程序本身就是一个字节序列。
也许是因为无处不在的局部性原理，在计算机中，很多时候“最小”指向的是一个“连续的块”而非“不可分割的点”。
“非常大的字节数组” => 非常重要的一种视角。
十六进制表示法
一个字节由8位组成。二进制表示法太冗长，而十进制表示法与位模式的互相转化很麻烦，替代的方法是，以16为基数，或者叫做十六进制（hexadecimal，简写为 hex）数，来表示位模式。
| 十进制 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 十六进制 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
| 二进制 | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
十六进制 => 优秀的替代品。
字数据大小
每台计算机都有一个字长（word size），指明指针数据的标称大小（nominal size）。因为虚拟地址是以这样的一个字来编码的，所以字长决定的最重要的系统参数就是虚拟地址空间的最大大小。对于一个字长为w位的机器而言，虚拟地址的范围为0~2^w-1，程序最多访问2^w个字节。32位字长限制虚拟地址空间为4GB，64位字长限制虚拟地址空间为16EB。
大多数64位机器也可以运行为32位机器编译的程序，这是一种向后兼容。“32位机器”和“64位机器”区别在于该程序是如何编译的，而不是其运行的机器类型。
字长和虚拟地址空间的最大大小不能完全一概而论。字长是指处理器一次能够处理的二进制数据位数，通常地址总线的位数与之保持一致，以保证一次性读取完整的数据并充分发挥寻址能力。但是现代计算机可能采用不同的位数以实现更高的性能和灵活性。
基本C语言数据类型的典型大小（以字节为单位），分配的字节数受程序是如何编译的影响而变化。
字长也会影响数据类型的典型大小。数据总线的位数通常也与字长保持一致，即使读取char类型的数据，CPU也是一次性读取64位的数据再提取8位（这时候小端法似乎更自然）。
| 有符号 | 无符号 | 32位 | 64位 |
|---|---|---|---|
| [signed] char | unsigned char | 1 | 1 |
| short | unsigned short | 2 | 2 |
| int | unsigned int | 4 | 4 |
| long | unsigned long | 4 | 8 |
| int32_t | uint32_t | 4 | 4 |
| int64_t | uint64_t | 8 | 8 |
| char * | 4 | 8 | |
| float | 4 | 4 | |
| double | 8 | 8 |
程序员应该力图使他们的程序在不同的机器和编译器上可移植。可移植性的一个方面就是使程序对不同数据类型的确切大小不敏感。
字长、地址总线、数据总线 => 处理器一次能够处理的二进制位数、虚拟地址空间的最大大小、数据的最大大小。
寻址和字节顺序
对于跨越多字节的程序对象，我们必须建立两个规则：这个对象的地址是什么，以及在内存中如何排列这些字节。
- 在几乎所有的机器上，多字节对象都被存储为连续的字节序列，对象的地址为所使用的字节中最小的地址。
- 排列表示一个对象的字节有两个通用的规则。最低有效字节在最前面的方式，称为小端法（little endian）；最高有效字节在最前面的方式，称为大端法（big endian）。大多数 Intel 兼容机都只用小端模式；IBM 和 Oracle 的大多数机器按大端模式操作，个人计算机使用小端法；许多比较新的微处理器使用双端法（bi-endian），比如移动电话上的 ARM 微处理器，但是最常见的 Android 和 iOS 只能运行于小端模式。
选择何种字节顺序没有技术上的理由。只要选择了一种规则并且始终如一地坚持，对于哪种字节排序的选择都是任意的。
和《格列佛游记》中的情节类似，争论仍然存在。
对于大多数应用程序员来说，其机器所使用的字节顺序是完全不可见（透明）的。不过有时候，字节顺序会成为问题。
- 在不同类型的机器之间通过网络传送二进制数据时，网络应用程序的代码编写必须遵守已建立的关于字节顺序的规则。
- 当检查机器级程序，阅读表示整数数据的字节序列时字节顺序也很重要。
- 当编写规避正常的类型系统的程序时，比如使用强制类型转换来访问和打印不同程序对象的字节表示。
表示字符串
C语言中字符串被编码为一个以null（其值为 0）字符结尾的字符数组。每个字符都由某个标准编码来表示，最常见的是 ASCII 字符码。字符串在使用 ASCII 码作为字符码的任何系统上都将得到相同的结果，与字节顺序和字大小规则无关。因而，文本数据比二进制数据具有更强的平台独立性。
可以通过执行命令 man ascii 来得到一张 ASCII 字符码的表。
文字编码的 Unicode 标准：
ASCII 字符集适合于编码英语文档，但是在表达一些特殊字符方面并没有太多办法，它完全不适合编码希腊语、俄语和中文等语言的文档。基本编码，称为 Unicode 的“统一字符集”，使用32位来表示字符，每个字符要占用4个字节。不过有一些替代编码，常见的字符只需要1个或2个字节，而不太常用的字符需要多一些的字节数。特别地，UTF-8 表示将每个字符编码为一个字节序列，兼容标准 ASCII。
数字和符号，一一对应。
表示代码
不同的机器类型使用不同的且不兼容的指令和编码方式。即使是完全一样的进程，运行在不同的操作系统上也会有不同的编码规则，因此二进制代码是不兼容的。二进制代码很少能在不同机器和操作系统组合之间移植。
计算机系统的一个基本概念就是，从机器的角度来看，程序仅仅只是字节序列。机器没有关于原始源程序的任何信息，除了可能有些用来帮助调试的辅助表以外。
布尔代数简介
二进制值是计算机编码、存储和操作信息的核心，所以围绕数值 0 和 1 的研究已经演化出了丰富的数学知识体系，称为布尔代数（Boolean algebra）。
最简单的布尔代数是在二元集合 {0, 1} 基础上的定义。二进制值 1 和 0 表示逻辑值 TRUE 或者 FALSE，而运算符~、&、|和^分别表示逻辑运算 NOT、AND、OR 和 EXCLUSIVE-OR。
布尔运算可以扩展到位向量的运算。
布尔运算&对|具有分配律；|对&具有分配律。
布尔环：a^a=0，(a^b)^a=b。
位向量一个很有用的应用就是表示有限集合。
C语言中的布尔运算
C语言的一个很有用的特性就是它支持按位布尔运算。
确定一个位级表达式的结果最好的方法，就是将十六进制的参数扩展成二进制表示并执行二进制运算，然后再转换回十六进制。
C语言中的移位运算
C语言还提供了一组移位运算，向左（<<）或者向右（>>）移动位模式。移位量应该是一个0~w-1之间的值。移位运算是从左至右可结合的。
右移运算 x>>k 的行为有点微妙。一般而言，机器支持两种形式的右移：逻辑右移和算术右移。逻辑右移在左端补k个0，算术右移是在左端补k个最高有效位的值。这种做法看上去可能有点奇特，但是它对有符号整数数据的运算非常有用。
C语言标准并没有明确定义对于有符号数应该使用哪种类型的位移，这意味着可能会遇到可移植性问题。实际上，几乎所有的编译器/机器都对有符号数使用算术位移，对于无符号数使用逻辑右移。
与C相比，Java对于如何右移有明确的定义。>> 表示算术右移，>>> 表示逻辑右移。
对于一个由w位组成的数据类型，C语言标准很小心地规避了说明当移动k≥w位时应该如何做。在许多机器上，实际上位移量是通过k mod w得到的。
加减法的优先级比位移运算高。
应该通过使用括号避免容易引起困扰的代码。
整数表示
整型数据类型
C语言支持多种整型数据类型——表示有限范围的整数。
| C数据类型 | 32位 | 64位 |
|---|---|---|
| [signed] char | -128~127 | |
| unsigned char | 0~255 | |
| short | -32 768~32 767 | |
| unsigned short | 0~65 535 | |
| int | -2 147 483 648~2 147 483 647 | |
| unsigned int | 0~4 294 967 295 | |
| long | -2 147 483 648~2 147 483 647 | -9 223 372 036 854 775 808~9 223 372 036 854 775 807 |
| unsigned long | 0~4 294 967 295 | 0~18 446 744 073 709 551 615 |
| int32_t | -2 147 483 648~2 147 483 647 | |
| uint32_t | 0~4 294 967 295 | |
| int64_t | -9 223 372 036 854 775 808~9 223 372 036 854 775 807 | |
| uint64_t | 0~18 446 744 073 709 551 615 |
取值范围并不对称，负数的范围比正数的范围大1。
C语言标准定义了每种数据类型必须能够表示的最小的取值范围，且char、short、int、long等类型的正数和负数的取值范围是对称的。
将标准和具体实现以及字长分开看待（32位机器也可以支持64位表示的整数数据类型）。
无符号数的编码
假设有一个整数数据类型有 w 位。将位向量写成
原理：无符号数编码的定义
映射的范围
原理：无符号数编码的唯一性
函数
补码编码
原理：补码编码的定义
最高有效位
映射的范围，其中，
原理：补码编码的唯一性
函数
观察特殊值
| 数 | w=8 |
|---|---|
| 11111111 | |
| 10000000 | |
| 01111111 | |
| -1 | 11111111 |
| 0 | 00000000 |
- 补码的范围不对称
- 最大的无符号数值比补码的最大值的两倍大1
C语言标准并没有要求要用补码形式来表示有符号整数，但是几乎所有的机器都是这么做的。关于整数数据类型的取值范围和表示，Java标准是非常明确的。
数学角度解释和推导
有符号数的其他表示方法
- 反码（Ones’s Complement）：除了最高有效位的权重是
而不是 ，它和补码是一样的： - 原码（Sign-Magnitude）：最高有效位是符号位，用来确定剩下的位应该取负权还是正权：
这两种表示方法都有一个奇怪的属性，就是对于数字 0 有两种不同的编码方式，把 [00…0] 都是解释为 +0，而值 -0 在原码中表示为 [10…0]，在反码中表示为 [11…1]。虽然过去生产过基于反码表示的机器，但是几乎所有的现代机器都使用补码。在浮点数中仍有使用原码编码。
尽管在实际应用中已经存在胜出者，但是了解其他有符号数的表示方式仍有助于理解编码本身。
补码（Two’s Complement）：对于非负数 x，我们用
反码（Ones’ Complement）用
了解术语来源比单纯的记忆术语有意思多了！
有符号数和无符号数之间的转化
C语言允许在各种不同的数字数据类型之间做强制类型转换。
- 从数学的角度来说：
- 对于两种形式都能表示的值，保持不变
- 负数转换为无符号数，0
- 无符号数超过补码范围，TMax
- 从C语言的实现角度来说：保持位模式不变，改变解释的方式
原理：补码转换为无符号数
对满足
这是通过比较等式(2.1)和等式(2.3)推导而来
原理：无符号数转换为补码
对满足
这是通过比较等式(2.1)和等式(2.3)推导而来
C语言中的有符号数与无符号数
尽管C语言标准没有指定有符号数要采用某种表示，但是几乎所有的机器都使用补码。
通常，大多数数字都默认是有符号的，如果要创建一个无符号常量，必须加上后缀 U 或者 u。
尽管C语言标准没有精确规定应如何进行无符号数和有符号数之间的转换，但大多数系统遵循的原则是底层的位表示保持不变。
转换的结果依赖于如何进行转换的规则，要理解胜出的规则的底层逻辑。它避免了计算和修改位模式，只改变了 interpretation。
- 显示的强制类型转换
- 隐式的类型转换（比如赋值，另外当心发生在表达式中的非直观情况）
扩展一个数字的位表示
将一个无符号数转换为一个更大的数据类型，只要简单地在表示的开头添加0。这种运算被称为零扩展（zero extension）
原理：无符号数的零扩展
定义宽度为
按照等式(2.1)，该原理直接遵循无符号数编码的定义。
将一个补码数字转换为一个更大的数据类型，可移植性符号扩展（sign extension），在表示的开头添加最高有效位的值。
原理：补码数的符号扩展
定义宽度为
根据归纳法，结合等式(2.3)
本质上，权重总和的变化量为 0。
截断数字
当把int类型的x强制类型转换为short时，就将32位的int截断为16位的short。截断一个数字可能会改变它的值——溢出的一种形式。
原理：截断无符号数
令
通过对等式(2.1)应用取模运算可以得到
原理：截断补码数值
令
到这一步有一点感觉，自己主动用数学工具描述原理的能力似乎退化了，尽管不难理解。
很微妙的一点是，“截取”并不是开辟了一个更小的空间，虽然也涉及修改“被截取”掉的部分，但本质上是在使用时提取了有用的一部分，忽略了剩余部分，这有点像缓冲区的使用方式。
关于有符号数与无符号数的建议
有符号数到无符号数的隐式强制类型转换导致了某些非直观的行为。这些非直观的特性经常导致程序错误，并且这种包含隐式强制类型转换的细微差别的错误很难被发现，因为它们是在没有明确指示的情况下发生的。
避免这类错误的一种方法是绝不使用无符号数。实际上，除了C语言很少有语言支持无符号整数。
使用场景：
- 往一个字中放入描述各种布尔条件的标记（flag）时
- 作为地址使用
- 当实现模运算和多精度运算的数学包时，数字是由字的数组来表示的
第3种不太理解。
整数运算
理解计算机运算的细微之处，从而理解计算机运算的有限性形成的一些属性，能够帮助程序员编写更可靠的代码。
无符号加法
考虑两个非负整数
计算它们的和，范围为
以此类推，持续的“字长膨胀” 意味着，要想完整地表示算术运算的结果，不能对字长做任何限制。
- Lisp，支持无限精度的运算
- 常见语言，支持固定精度的运算
似乎“字长”确实具有表示整数所需的位数的含义。
原理：无符号数加法
对满足
运算
被定义为把整数和 截断 位得到的结果，再视为一个无符号数。这也可以视为一种形式的模运算，模 。
原理：检测无符号数加法中的溢出（易证）
对在范围
原理：无符号数求反
对满足
第一眼看上去好奇怪。
另外，模数加法，阿贝尔群，单位元，加法逆元，涉及这么多概念吗。。。
补码加法
对满足
运算
被定义为把整数和 截断 位得到的结果，再视为一个补码数。
两个数的
设计是巧妙。可是为什么在这里直接认为两者的加法具有位级等价性呢？明明两者的乘法具有位级等价性还需要证明。
推导如下：
结合等式(2.6)
结合等式(2.7)
- 如果
，则 - 如果
，则 - 如果
，则 ，则 - 如果
，则 ，则
虽然结论符合直觉，但是严谨的推导过程并不简单。补码加法的定义是“截断和解释”，溢出是衍生出的概念，在不溢出的情况下，还是可能出现需要截断的情况。
原理：检测补码加法中的溢出
对满足
原理：补码求反
“补码的非”这个说法好奇怪啊，negation 翻译成这个好吗，在无符号数部分还翻译成求反呢。
对满足
求反的两种方法：
- 按位取反（求补）后，再对结果加 1，即
。 - 保留最右侧的 1，对其左侧按位取反（求补）
无符号乘法
都是先将运算定义为截取低
位，或者说被迫抛弃不能存储的部分高位。
原理：无符号数乘法
对满足
补码乘法
原理：补码乘法
对满足
原理：无符号和补码乘法的位级等价性
给定长度为
推导如下
上面的
*需要转义，是因为默认 markdown 渲染插件冲突吗
对等式两边应用
乘以常数
在大多数机器上，整数乘法指令相当慢，需要 10 个或者更多的时钟周期，然而其他整数运算（例如加法、减法、位级运算和移位）只需要 1 个时钟周期。
原理：乘以 2 的幂
对固定字长左移
原理：与 2 的幂相乘的无符号乘法
对于无符号整数
原理：与 2 的幂相乘的补码乘法
对于补码整数
溢出不影响移位结果
由于整数乘法比移位和加法的代价要大得多，许多C语言编译器试图以移位、加法和减法的组合来消除很多整数乘以常数的情况。
乘以非 2 的幂的常数，如果没有优化，底层通过循环加法实现，也有特定硬件可以实现乘法。
除以 2 的幂
在大多数机器上，整数除法比整数乘法更慢——需要 30 个或者更多的时钟周期。
无符号和补码数分别使用逻辑移位和算术移位来达到目的。
除以 2 的幂可以通过逻辑或者算术右移来实现。可惜，这个方法不能像乘法，推广到除以任意常数。
关于整数运算的最后思考
- 计算机执行的“整数”运算实际上是一种模运算形式。
- 表示数字的有限字长限制了可能的值的取值范围，运算结果可能溢出。
- 补码既能表示负数也能表示正数，同时使用与执行无符号算术相同的位级实现。
参考文章
- 《深入理解计算机系统》