C语言支持多种整型数据类型来表示有限范围的整数。每种类型都能用关键字来指定大小，这些关键字包括char、short、long，同时还可以指示被表示的数字是非负数(声明为unsigned)、或者可能是负数（默认）。另外，为这些不同的大小分配的字节数根据程序编译为 32 位还是 64 位而有所不同。

long的大小与int一样大，属于历史遗留问题，历史上的int在16位平台时代是2个字节，long是4个字节，所以long要long，等到32位平台将int提升到32位一个字长时，int和long的长度就一样。

不同word size对应的最值的16进制编码（其中的U表示Unsigned，T表示Two's comlement（补码））：

注意上面的16进制与二进制的对应关系：

7：0111

8：1000

F：1111

可以看出有以下数量关系：

1 无符号数编码

假设有一个整数数据类型，有位（word size or width）。将其写成向量，将其视为二进制表示的无符号数，则每一位取值范围为0或1。

用函数（Binary to Unsigned的缩写，长度为)表示为:

函数将一个长度为w 的0、1 串映射到非负整数。

例：

可以用长度为的指向右侧箭头的条表示每个位的位置 i。每个位向量对应的数值就等于所有值为 1 的位对应的条的长度之和。

w位二进制所能表示的无符号整数的范围：

2 有符号整型数据的补码编码

目前，最常见的计算机有符号整型数的计算机表示方式为补码形式。在补码中，将字的最高有效位解释为负权（negative weight）。这里通过函数 B2T_w(Binary to Two's-complement的缩写)来表示：

例：

最高有效位也称为符号位，它的“权重”为，是无符号表示中权重的负数。符号位被设置为1 时，表示值为负，而当设置为0 时，值为非负。

补码 + 它的负数 ＝ 模；

补码和它的负数的二进制位只有最低位是相同的，其它位都是相补：

补码 && 它的负数 = 1;

这也是经常有以下表述的来由：

对于负数，补码等于反码+1。

补码使用最高位表示符号，但与无符号整数编码表示的总体值域的个数是一致的：。

我们用向左指的条表示符号位具有负权重。于是，与一个位向量相关联的数值是由可能的向左指的条和向右指的条加起来决定的。

最高位以外的其它位相对于最高位而言，是一个此涨彼消的状态。

w位二进制所能表示的有符号整数的范围：

负整数的范围比正整数的范围大1，多出来的数就是100…000（二进制序列，最小的负数），该数取反加1等于模，截断后就是0了。

3 有符号整数与无符号整数之间的转换

C 语言允许在各种不同的数字数据类型之间做强制类型转换。遵循底层的位表示不变，而按不同类型的编码规则进行解释的原则。

如果是相关类型的隐式转换，C语言设置了一系列的转换规则。

如果是不相关类型的强制转换，C语言会在位级层面按编码规则做重新解释（解码）。

例如，假设变量x 声明为int，u 声明为unsigned，表达式（unsigned)x 会将x 的值转换成一个无符号数值，而(int)u 将u 的值转换成一个有符号整数。将有符号数强制类型转换成无符号数。另外，一个表达式中，如果同时存在无符号整数与有符号整数，计算时，有符号整数会隐式转换为无符号整数。

对于有符号整数的正整数部分，与无符号整数是一致的。

对于对于有符号整数的负整数部分，与无符号整数只有最高位的解释不同，其它位是一致的。

所以有以下数量关系：

负整数x→U ＝ x+

u→负整数x = U -

由于C 语言对同时包含有符号和无符号整型数表达式的隐式转换，会出现一些奇特的行为。当执行一个运算时，如果它的一个运算数是有符号的而另一个是无符号的，那么C语言会隐式地将有符号整数强制类型转换为无符号数，并假设这两个数都是非负的，来执行这个运算。就像我们将要看到的，这种方法对于标准的算术运算来说并无多大差异，但是对于像<和>这样的关系运算符来说，它会导致非直观的结果。

有符号数到无符号数的隐式强制类型转换导致了某些非直观的行为。而这些非直观的特性经常导致程序错误，并且这种包含隐式强制类型转换的细微差别的错误很难被发现。

4 扩展一个整型数字的位表示

一个常见的运算是在不同字长的整数之间转换，同时又保持数值不变。

对于有符号整数和无符号整数，两者在扩展时，高位的符号扩展有所区别：

short sx = val; unsigned short usx = sx; int x = sx; unsigned ux = usx;

在采用补码表示的32 位大端法机器上的内存布局：

有符号整型使用1来做符号扩展。

无符号整型使用0来做符号扩展。

有符号整数在做右移运算时，也会存在符号扩展的问题。

5 截断数字

假设我们不用额外的位来扩展一个数值，而是减少表示一个数字的位数。例如下面代码中这种情况：

int x = 53191;short sx = (short) x; int y = sx;

当我们把x 强制类型转换为short 时，我们就将 32 位的int 截断为了 16 位的short int。

当将一个w位的整型数截断为一个k位整型数字时，我们会丢弃高w-k位。

无符号整数取模：

有符号整数的补码取模后要做转换 ：

6 整数运算与溢出

C语言的整型数字是一个有限字长的表示，当在计算时存在溢出时，会做模运算处理。

当两个w位的无符号整型相加时，其结果可能是一个w+1位的无符号数。

当两个w位的无符号整型相加时其和等于或超过时，就会发生溢出，其结果为和与的模运算：

补码加法存在正溢出与负溢出：

首先要明白，一个正数和一个负数相加，结果一定不会溢出（因为结果的绝对值一定小于两个加数的绝对值，两个加数都表达出来了，结果一定能表达出来。）

所以，发生溢出的情况一定是符号相同的两个数相加。

分情况讨论：

① 正整数pa + 正整数pb = r

符号位0，数位相加，如果结果的符号位变成1了，那一定是两个加数的最高位相加进上来的。

假设将一个长度 w=4 的0、1 串映射到有符号整数，其最大的正数只能是0111，也就是7。

0111+0001 = 1000 // 7 + 1 ＝ 8-2^4 = -8，向下溢出

0111+0011 = 1010 // 7+ 3 = 10-2^4 = -6，向下溢出

发生向下溢出，判断的方式之一是：r

② 负整数na + 负整数nb = r

符号位都是1，所以符号位一定会进位。数位相加，如果最后符号位是0，说明结果变成正的了，那一定是发生溢出了（负+负！=正）。

假设将一个长度 w=4 的0、1 串映射到有符号整数，其最小的负数只能是1000，也就是-8。

1000+1111 = 11000 ->0110 // -8+(-1) = -9+2^4 = 7，向上溢出

1011+1011 = 10110 ->0110 // -5+(-5) = -10+2^4 = 6，向上溢出

另外一种情况，没有改变符号位的溢出，属正常溢出，正如有符号位扩展、算术移位一样：

1100+1100 = 10000 ->0000 // -4+(-4)= -8， 正常溢出

1111+1111 = 11110 ->1110 // -1+(-1)=-2， 正常溢出

发生向上溢出，判断的方式之一是：r

CPU的标志寄存器有一个溢出标志位，反映有符号数加减运算是否溢出。如果运算结果超过了8位或者16位有符号数的表示范围，则OF置1，否则置0。

7 整数的乘除

① 两整数乘除的结果还是一个整数类型（类型一致），如果是除法，可能存在舍入（舍入到零，向上舍入，向下舍入）的情况；

② 两整数乘法要考虑溢出的情况。

③ 位运算也是一种特殊的整数乘除，乘数与除数是2的不同的整数幂（当一个整数乘除一个常数时，这个常数如果不是某个整数次幂，可以拆解成不同的幂次的加减）。

8 代码示例

8.1 带符号数产生意外结果的例子。这个例子会造成无限循环，因为sizeof会返回unsigned int 类型，由此带来的结果是，i - sizeof(char)这个表达式的求值结果将会是 unsigned int (隐式转换 !!)，i 会隐式转换为unsigned，i从 0 减 1 后变成-1，其二进制编码是 0xFFFFFFFF，转换成无符号数是2^32-1，从而产生无限循环，有时候你需要特别留心这种不经意的错误 !

int n = 10, i; for (i = n - 1 ; i - sizeof(char) >= 0; i--) printf("i: 0x%xn",i);if (-1 > 0U) // -1的二进制编码是0xFFFFFFFF，转变成无符号数是2^32-1 printf("You Surprised me!n");

8.2 以下是2002年的freeBSD内核的部分代码，其中包含了漏洞，假设恶意人员将负值作为maxlen传入这个函数，有发生什么情况？

以下size_t的类型是typedef unsigned int size_t的类型定义：

#define KSIZE 1024char kbuf[KSIZE];int copy_from_kernel(void *user_dest, int maxlen) { int len = KSIZE < maxlen ? KSIZE : maxlen; memcpy(user_dest, kbuf, len); return len;}void *memcpy(void *dest, void *src, size_t n);void getstuff() { char mybuf[MSIZE]; copy_from_kernel(mybuf, -512); // -512转变成无符号数后是2^31+512}

8.3 给定一个有序的整型数组，请编程实现二分查找算法。

高德纳在《计算机程序设计的艺术》指出，虽然早在1946年就有人将二分查找的方法公诸于世，但直到1962年才有人写出没有bug的二分查找程序，可见，写一个安全的代码并不容易，你是不是一不小心就写出像下面这样的二分查找代码了？

int binary_search(int a[], int len, int key){ int low = 0; int high = len - 1; while ( low <= high ) { int mid = (low + high)/2; // 提示：这里有溢出Bug！ if (a[mid] == key) { return mid; } if (key < a[mid]) { high = mid - 1; }else{ low = mid + 1; } } return -1;}

ref

Randal E. Bryant, David R. O’Hallaron《Computer Systems：A Programmers Perspective》

－End－