c的基础 1. 无符号数和补码

计算机中储存和处理的信息是以二进制信号表示的。单个的位不是是非常有用，而将这些位 组合在一起，加上某种解释，即给不同的可能位模式赋予含义，我们就能够表示如何有限集合的元素，即实现各种数据结构。计算机中使用8位的块称之为字节作为最小的可寻址的存储器单位，机器级程序将存储器视为一个非常大的字节数组，称为虚拟存储器。存储器的每个字节都有一个唯一的数字来标识，称为地址，所有可能地址的集合称为虚拟地址空间。

c语言中的指针，指针的值为某个存储块的第一个字节的虚拟地址。C编译器将每个指针和类型信息结合起来，根据指针值的类型也就是声明的指针类型，来生成不同的机器级代码来访问储存在指针所指向位置出的值每个程序对象可以简单的视为一个字节块，而程序本身就是一个字节序列。

字长，32位系统为4个字节，64位系统为8个字节，对于32位字长时，其能表示的虚拟地址范围为0 - 2^32-1 ，即虚拟地址空间最大为4GB。

大端法：最高有效字节在低地址位。

小端法：最高有效字节在高地址位。

高低地址位， 0， 1241251，显然，前者为低，后者为高。

一般系统都使用的是大端法。

C中基本的位运算：

^异或， 1 ^ 0 = 1 , 0 ^ 1 = 1, 0 ^ 0 = 0, 1 ^ 1 = 1 .

& 且 |或 ~取反

<< n 左移 n 位 >> n 右移n位

c中的右移有两种，逻辑右移和算术右移，逻辑右移即在左端补0，而算术右移在左端不最高有效位的值。一般对于有符号数进行的是算术右移，

java中使用>>表示算术右移，而使用>>>表示逻辑右移。

位运算操作符的优先级都低于 加减 号， 所以 在算式中 一般都要用括号 括起来。

对位运算的一个常见用法是实现掩码运算。掩码就是指从字节中选出一定位的集合。

计算机系统中有三种重要的数字表示，无符号（unsigned)编码,只能表示非负的数，补码(two's-complement)编码，用来表示有符号整数，浮点数(float-point)编码，表示实数的科学计数发的二进制版本。只有C系语言有无符号数这个概念，但我认为无符号数的存在是一种优点。

这里讨论两种编码，无符号和补码。

无符号数的编码即直接将二进制数据转换为10进制，就可以得到结果。其最大值为 2 ^ w - 1，w为其位数，最小值为0.

补码：最高有效位解释或为负权，即 - 2 ^w ，然后将所有位乘以权值得到结果。最高有效位即为符号位。最大值为 2 ^(w-1)-1，最小值为 - 2^w.补码的范围是不对称的。

由于不同机器上的数据类型可能有不同的取值范围，如long，在32位系统中为4个字节，但在64位系统中为8个字节。所以一般使用在stdint.h中定义的数据类型intN_t和unintN_t，来声明N位的有符号数和无符号数，则会使程序在不同系统中都可以正确运行。N一般去8，16，32，64。

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

程序读取不同类型时，只是对存储器上的信息以不同的方式进行解释，而C语言进行强制转换时，也只是改变了其解释存储器上位信息的方式，并没有改变存储器上的信息本身。

所以同样位长的无符号数和有符号数直接的转换，不改变底层的位信息，只是换了一种解释的方法来解释这些位。如对无符号的int 4 294 967 295转换为有符号的int就是 -1，而有符号的int 的-1转换为无符号的int 就是4 294 967 295。

当一个运算中 一个运算数为有符号，一个运算数为无符号数，C语言会隐式地将有符号数强制类型转换为无符号数，，然后执行两个无符号数之间的运算。对于标准的运算来说，这样做不会出错。如 c = a + b, 其中c和a为有符号int，a为-1，b为无符号int为1，则运算时，将a转换为无符号数，也就是4 294 967 295，然后加b，应得到的是4 294 967 296，但在位级上，由于最高位的1超过范围而溢出，只剩下32个0，则最后c的结果为0。可以看出，这里对普通的运算没有影响。

但在一些关系表达式中，则会出错。如 -1 < 0u。u表示无符号数，这里将-1转换为无符号的int后，值为4 294 967 295，肯定是比0要大的，然后就出错了。

在不同字长的整数之间进行转换，需要进行为的扩展和截断。

扩展：

无符号数扩展使用，零扩展：在表示的开头添加0。

有符号数扩展使用，符号扩展：在表示中添加最高有效位的值的副本。即符号位为1时，添加若干个1。

有符号的负数扩展时，前面添加1不会对最后的数值有影响，假定扩展前为w位，扩展后为v位，扩展前的值为-i，则有扩展前除去最高位，剩下为表示的整数为j = 2^w - i，则扩展后，从符号位到原来符号位，即除去j表示数据的部分的剩余部分表示的值为： - 2 ^(v-1) + 2^(v-2)+...+2^w ，则扩展后表示的值为- 2 ^(v-1) + 2^(v-2)+...+2^w + 2 ^w-- i.则前面的数都可以消去，即得到最后结果为-i。

.C中同时进行有无符号转换和不同字长的数据转换时，想转换不同字长的数据类型，即先进行扩展或者截取，然后在使用有符号或者符号的方式来解释数据。

截断：

截取时即舍去高n位即可。

整数运算：

无符号数的加法，会导致结果大于数据类型的范围，则无符号的运算其实是一种模运算，利用溢出机制，实现计算和模2^w。

算术运算溢出，指完整的整数结果不能放到数据类型的字长限制中去。判断两个数相加,如 c = a + b,是否发生溢出，只要判断 c是否 小于a或者b即可，因为a或者b肯定是小于2^w。

补码的加法：

两个有符号数的w位补码之和与无符号数之和有完全相同的位级表示，计算机使用同样的机器指令来执行无符号或有符号的加法。如之前进行的分析：c = a + b, 其中c和a为有符号int，a为-1，b为无符号int为1，则运算时，将a转换为无符号数，也就是4 294 967 295，然后加b，应得到的是4 294 967 296，但在位级上，由于最高位的1超过范围而溢出，只剩下32个0，则最后c的结果为0。

如果将这里的b也看作是有符号数，其结果依然如此且正确。

所以，我们可以理解为，补码的加法是 先将其转换为无符号数，然后相加，得到的结果在转换为有符号数。

这里有溢出，正溢出和负溢出。

正溢出：得到的结果应该位于2^(w-1) —— 2 ^w - 1，但使用补码转换为有符号数后是在 0 —— - 2 ^ (w-1)这个范围内。

负溢出：得到的结果应该在-2^w —— -2^(w-1),但是由于溢出，结果在 0 —— 2^(w-1) -1上。

其他情况为正常。

补码的非：

即取负。对于 -2 ^(w-1)取非为 其本身。对于其他的值可以得到正确结果。

无符号的乘法：

即计算乘积后模 2^w。

补码的乘法：

补码乘积的范围在 -2^(2w-2) + 2^(w-1) 和 -2^(2w-2)之间。这里，对于无符号和补码的乘法运算，其位级表示依然是一样的，所以对于补码的乘法是将其转换为无符号数，然后相乘，结果模2^w。这里对于运算的分析：

令x，y的无符号值为 a，b，其符号位值为 c,d。则 a = x + c * 2^w , b = y + d * 2 ^ w;

a * b % 2^w

= ((x + c * 2^w )*( y + d * 2 ^ w) )%2^w

= (x * y + (y *c + x*d + c*d * 2^w)* 2^w)% 2^w

= (x*y)% 2^w

计算机上的乘法指令相当慢，一般需要10个以上的时钟周期。编译器会使用一项重要的优化，用移位和加法运算和减法运算来代替乘以常数的乘法。如使用(x<<4)-(x<<1)来代替x*14。

计算机上的除法的速度就更加慢了，一般需要30个以上的时钟周期。除以2的幂可以通过右移操作进行，对于无符号是逻辑移位，对于补码进行算术移位。