第2章信息的表示和处理

计算机的表示法是用有限数量的二进制位来对一个数字编码，因此，当结果太大以至于不能表示时，某些运算就会溢出，溢出会导致某些令人吃惊的结果，例如，在今天的大多数计算机上（32位int），计算表达式200*300*400*500会得出结果-884901888.这违背了整数运算的特性，计算一组正数的乘积不应该得到负数。
另一方面，整数的计算机运算满足人们熟知的真正的整数运算的许多性质，如交换律和结合律。
浮点运算有完全不同的数学属性，虽然溢出会产生特殊值 $+\infty$ ，但是一组正数的乘积总是正的，由于表示的精度有限，浮点运算是不可结合的，例如，在大多数机器上，C表达式(3.14+1e20)-1e20求得值是0.0，而3.14+(1e20-1e20)求得值为3.14.
整数运算和浮点数运算会有不同的数学属性是因为它们处理数字表示有限性的方式不同。整数的表示虽然只能编码一个相对较小的数值范围但是这种表示时精确的，而浮点数虽然可以编码一个较大的数值范围，但是这种表示只是近似的。

2.1 信息存储

机器级程序将内存视为一个非常大的字节数组，称为虚拟内存，内存的每个字节都由一个唯一的数字来标识，称为它的地址，所有可能地址的集合就称为虚拟地址空间。顾名思义，这个虚拟地址空间只是一个展现给机器级程序的概念性映像。实际的实现是将动态随机访问储存器、闪存、磁盘存储器、特殊硬件和操作系统软件结合起来，为程序提供一个看上去统一的字节数组。
C语言中一个指针的值都是某个存储块的第一个字节的虚拟地址。C编译器还把每个指针和类型信息联系起来，这样就可以根据指针值的类型，生成不同的机器级代码来访问存储在指针所指向位置处的值。尽管C编译器维护着这个类型信息，但是它生成的实际机器级程序并不包含关于数据类型信息。每个程序对象都可以简单地视为一个字节块，而程序本身就是一个字节序列。

2.1.1 十六进制表示法

当值x是2的非负整数n次幂时，也就是x = xⁿ，我们可以很容易地将x写成十六进制形式。只要记住x的二进制表示就是1后面跟n个0，十六进制数字0表示4个二进制0。所以，当n表示成i+4j的形式，我们可以把x写成开头的十六进制字为1(i=0),2(i=1),4(i=2),8(i=3)，后面跟随者j个十六进制的0。比如x=2048= $2^{11}$ 。n = 11 = 3 + 4 * 2，从而得到十六进制表示0x800

2.1.2 字数据大小

每台计算机都有一个字长，指明指针数据的标称大小，因为虚拟地址是以这样的一个字来编码的，所以字长决定的最重要的系统参数就是虚拟地址空间的最大大小。
大多数64位机器也可以运行32位机器编译的程序，这是一种向后兼容，因此举例来说，当程序prog.c用如下伪指令编译后：linux> gcc -m32 prog.c 。该程序就可以在32位或64位机器上正确运行
因此我们将程序称为32位程序或64位程序，区别于程序如何编译，而不是在哪种机器上运行
为了避免由于依赖典型大小和不同编译器设置带来的奇怪行为，ISO C99引入了一类数据类型，其数据大小是固定的，不随编译器和机器设置而变化，其中就有数据类型int32_t和int64_t。使用确定大小的整数类型是程序员控制数据表示的最佳途径
数据类型char是一个例外，尽管大多数编译器和机器都将它们视为有符号数，但C标准不保证这一点。相反，正如方括号指示的那样，程序员应该用有符号字符的声明来保证其为一个字节的有符号数值，不过，在很多情况下，程序行为对数据类型char有无符号并不敏感
C语言标准对不同数据类型的数字范围设置了下界，但是却没有上界

2.1.3 寻址和字节顺序

对于跨越多字节的程序对象，我们必须建立两个规则，这个对象的地址是什么，以及在内存中如何排列这些字节，在几乎所有机器上，多字节对象都被存储为连续的字节序列，对象的地址为所使用字节中最小的地址。
某些机器选择在内存中按照从最低有效字节到最高有效字节的顺序存储对象，而另一些机器则按照从最高字节到最低有效字节的顺序存储。前一种规则——最低有效字节放在最前面的方式称为小端法。后一种规则——最高有效字节放在最前面的方法称为大端法。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yRsbNQTM-1626352423774)(http://qv9agnsrq.hb-bkt.clouddn.com/IMG_0756(20210715-074858)].PNG)
许多比较新的微处理器是双端法，也就是说可以把它们配置成作为大端或小端的机器运行。然而，实际情况是：一旦选择了特定的操作系统，那么字节顺序也就固定了。比如用于许多手机的ARM微处理器，其硬件可以按小端或大端两种模式操作，但是芯片上最常见的两种操作系统——安卓和IOS都是运行小端模式
有时，字节顺序会成为问题。
1. 在不同类型的机器之间通过网络传送二进制数据时，一个常见的问题是当小端法机器产生的数据被发送到大端法机器或者反过来时，接受程序会发现，字里的字节成了反序。为了避免这类问题，网络应用程序的代码编写必须遵守已建立的关于字节顺序的规则，以确保发送方机器将它的内部表示转换成网络标准，而接收方机器则将网络标准转换成它的内部表示。
2. 当阅读表示整数数据的字节序列时，字节顺序也很重要，这通常发生在检查机器级程序时，当阅读小端法机器生成的机器级程序表示时，经常会将字节按照相反的顺序显示。书写字节序列的自然方式是最低位字节在最左边，最高位字节在最右边，正好与习惯相反
3. 编写规避正常的类型系统的程序时，在C语言中可以通过使用强制类型转换或联合来允许以一种数据类型引用一个对象，而这种数据类型与创建这个对象时定义的数据类型不同，大多数应用编程都强烈不推荐这种编码技巧，但是它们对系统级编程来说是非常有用的，甚至是必须的。

/*
 * @Description: 打印程序对象的字节表示
 * @version: 
 * @Author: 
 * @Date: 2021-07-14 10:43:34
 * @LastEditors: Please set LastEditors
 * @LastEditTime: 2021-07-14 11:04:59
 */
#include <stdio.h>
typedef unsigned char *byte_pointer;
void show_bytes(byte_pointer start, size_t len)
{
    size_t i;
    for (i = 0; i < len; i++)
        printf(" %.2x", start[i]);
    printf("\n");
}
void show_int(int x)
{
    show_bytes((byte_pointer)&x, sizeof(int));
}
void show_float(float x)
{
    show_bytes((byte_pointer)&x, sizeof(float));
}
void show_pointer(void *x)
{
    show_bytes((byte_pointer)&x, sizeof(void *));
}
void test_show_bytes(int val)
{
    int ival = val;
    float fval = (float)ival;
    int *pval = &ival;
    show_int(ival);
    show_float(fval);
    show_pointer(pval);
}
int main(void)
{
    test_show_bytes(1);
    int val = 0x87654321;
    byte_pointer valp = (byte_pointer)&val;
    show_bytes(valp, 1);
    show_bytes(valp, 2);
    show_bytes(valp, 3);
    return 0;
}
/* 
01 00 00 00
00 00 80 3f
f4 fe 61 00
 */

2.1.4 表示字符串

2.1.5 表示代码

计算机系统的一个基本概念就是，从机器的角度来看，程序仅仅只是字节序列，机器没有关于原始源程序的任何信息，除了可能有些用来帮助调试的辅助表以外。

2.1.6 布尔代数简介

2.1.7 C语言中的位级运算

2.1.8 C语言中的逻辑运算

2.1.9 C语言中的移位运算

移位运算是从左到右可结合的，所以x<<j<<k等价于(x<<j)<<k
左移就是向左移动k位，丢弃掉最高的k位，低位补0
机器一般支持两种形式的右移：逻辑右移和算术右移，逻辑右移在左端补0，算术右移在左端补最高有效位的值
C语言标准没有明确定义对于有符号数应该使用哪种右移，这就意味着任何假设一种或者另一种右移形式的代码都可能会遇到可移植性问题，然而实际上几乎所有编译器/机器组合都对有符号数使用算数右移，且很多程序员也都假设机器会使用算数右移。对于无符号数右移必须是逻辑的
Java对右移有明确定义，>>表示算数右移，>>>表示逻辑右移
对于一个w位组成的数据类型，若移动位数大于等于w，在许多机器上是位移量是通过计算k mod w得到的。但是C标准没有保证，Java保证了。

2.2 整数表示

2.2.1 整型数据类型

C语言标准定义了每种数据类型必须能够表示的最小的取值范围，图2-11，它们的取值范围比上图的典型实现一样或小一些。特别的，除了固定大小的数据类型是例外，我们看到它们只要求整数和负数的取值范围是对称的。固定大小的数据类型保证数值的范围与2-9给出的典型数值一致，包括不对称性。

2.2.2 无符号数的编码

函数 $B2U_{w}$ 能够被定义为一个映射 $B2U_{w}:\{0,1\}\rightarrow\{0,...,2^{w}-1\}$ 。

2.2.3 补码编码

最常见的有符号数的计算机表示方式就是补码形式，在这个定义中，将字的最高有效位解释为负权。
补码编码的定义，对于向量 $x=[x_{w-1},x_{w-2},...,x_{0}]$ ： $B2T_{w}(x)=-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_{i}2^{i}$ 。
$TMin_{w}=-2^{w-1}$ , $TMax_{w}=2^{w-1}-1$
$B2T_{w}:\{0,1\}\rightarrow\{TMin_{w},...,TMax_{w}\}$
$∣ T M i n ∣ = ∣ T M a x ∣ + 1$
$UMax_{w}=2TMax_{w}+1$
ISO C99标准在文件stdint.h中引入了这个整数类型类。这个文件中定义了一组数据类型，声明形如intN_t和uintN_t，对不同的N值指定N位有符号和无符号整数，N的具体指与实现有关，但是大多数编译器允许的值为8 16 32 64
这些数据类型对应着一组宏，定义了每个N的值对应的最小和最大值，这些宏的名字形如INTN_MIN INTN_MAX UINT_N_MAX
确定宽度类型的带格式打印需要使用宏，以与系统相关的方式扩展为格式串。

#include <stdint.h>
#include <stdio.h>
int main(void)
{
    int32_t x = 1;
    uint64_t y = 2;
    printf("x = %" PRId32 ", y = %" PRIu64 "\n", x, y);
    return 0;
}

关于整数数据类型的取值范围和表示，Java标准是非常明确的，它要求采用补码表示，取值范围与图2-10的情况一样。在Java中，单字节数据类型称为byte，而不是char。
反码：除了最高有效位的权是 $2^{w-1}-1)$ 而不是 $2^{w-1}$ ，它和补码是一样的： $B2O_{w}(x)=-x_{w-1}(2^{w-1}-1)+\sum_{i=0}^{w-2}x_{i}2^{i}$
原码：最高有效位是符号位，用来确定剩下的位应该取负权还是正权： $B2S_{w}(x)=(-1)^{x_{w-1}}.(\sum_{i=0}^{w-2}x_{i}2^{i})$
属于补码来源于这样一种情况，对于非负数x，我们用 $2^{w}-x$ 来计算-x的w位表示，术语反码来源于这样一个属性，我们用[111…111]-x来计算-x的反码表示

2.2.4 有符号数和无符号数之间的转换

我们看到，强制类型转换的结果保持位值不变，只是改变了解释这些位的方式
补码转换为无符号数：对满足 $TMin_{w}\leq x\leq TMax_{w}$ 的x有： $T2U_w(x)=\begin{cases}x+2^w,&x\ngeq0\\x,&x\ge0\end{cases}$
无符号数转换为补码：对于满足 $0\le u \le UMax_w$ 的u有： $U2T_w(u)=\begin{cases}u,&u\le TMax_w\\u-2^w,&u\nleq TMax_w\end{cases}$
总结一下，我们考虑无符号和补码之间互相转换的结果，对于在范围 $0\le x \le TMax_w$ 之内的值x而言，我们得到的转换结果与原数是一样的。对于这个范围之外的数值，转换需要加上或减去2^w
最靠近0的负数映射为最大的无符号数，最小的负数映射为一个刚好在补码的正数范围之外的无符号数。

2.2.5 C语言中有符号数与无符号数

由于C语言对同时包含有符号和无符号数表达式的这种处理方式，出现一些奇特的行为，放执行一个运算时，如果它的一个运算数是由符号，一个是无符号的，那么C语言将会隐式的将有符号参数强制转换为无符号数，并假设这两个数都是非负的。这种方法对标准的算数运算来说没有多大差异，但是对于想大小于运算来说，会导致非直观的结果。
我们将TMin写成-2147483647-1。因为C头文件limits.h也是这样定义的，#define INT_MIN (-INT_MAX - 1)，补码表示的不对称性和C语言的转换规则之间奇怪的交互，迫使我们用这种不寻常的方式来写TMin

2.2.6 扩展一个数字的位表示

无符号的零扩展：定义宽度为w的位向量u=[ $u_{w-1},u_{w-2},\dots,u_0$ ]，和宽度为w’的位向量u’=[ $0,\dots,0,u_{w-1},\dots,u_0$ ]，其中w’>w，则B2Uw(u)=B2Uw’(u’)
补码数的符号扩展：定义宽度为w的位向量x=[xw-1,…,x0]和宽度为w’的位向量x’=[xw-1,…,xw-1,xw-1.xw-2….,x0]，其中w’>w，则B2Tw(x)=B2Tw’(x’)。

/*
 * @Description: 位扩展和有无符号的转换的相对顺序
 * @version: 
 * @Author: 
 * @Date: 2021-07-14 17:00:41
 * @LastEditors: Please set LastEditors
 * @LastEditTime: 2021-07-14 17:04:44
 */
#include <stdio.h>
typedef unsigned char *byte_pointer;
void show_bytes(byte_pointer start, size_t len)
{
    size_t i;
    for (i = 0; i < len; i++)
        printf(" %.2x", start[i]);
    printf("\n");
}
int main(void)
{
    short sx = -12345;
    unsigned uy = sx;
    printf("uy = %u:\t", uy);
    show_bytes((byte_pointer)&uy, sizeof(unsigned));
    return 0;
}
// uy = 4294954951:         c7 cf ff ff
// (unsigned)(int)sx
// 先进行位扩展
// 这是C语言标准要求的