CSAPP要点总结 第2章 信息的表示和处理 part2 整数

整数表示

整数数据类型和范围

32位机器上C语言的整数典型的取值范围:

64位机器上C语言的整数典型的取值范围:

不同于32位的情况在于long类型不再是32位而是64位。

C语言标准要求的整数最小的取值范围：

可以才看出，32位无符号整数不能超高约 42亿（即4GB），64位整数不能超过约。。。额。。极少情况会超过吧。

对于Java，只支持有符号数

补码（two’s-complement）

补码的一个简单理解是： 除了最高位，其他位按照无符号数规则取值，而最高位表示权重，最高位为0时权重为0，当最高位为1时，解释为负权（negative weight）， 取值为 $-2^{w-1}$ , 其中w是最高位，那么用数学表示即为：

例如 $ B2T_4[1011] = -8 + 3 = -5 $,其中负权为 $-1*2^3 = -8$。

因此，可以进一步推出最小值为0x1000 0000 = -128 和 最大值ox0111 1111 = 127（以8位为例）。

在最大值和最小值之间，补码和数值是一一对应的，用数学来说是一个双射。

C语言并没强制要求用补码形式表示有符号整数，但几乎所有机器都如此表示。 若希望代码具有最大移植性，必须假设该数的取值范围按照如上表格C语言标准要求的整数最小的取值范围 当然，按照如上表的32/64位典型取值范围在绝大多数情况下都适用。

然而，由于标准并没有强制规定，当数据大小非常重要是，采用确定大小的整型类型。 ISO C99标准在stdint.h中引入intN_t以及uintN_t，N取值通常为8、16、32、64。

关于整型取值范围和表示，Java则非常明确，它要求用补码， 取值范围参见上表64位机器上C语言的整数典型的取值范围。 命名有所不同，Java中byte对应C中的char，且没有long long数据类型。 因此，Java在任何机器上行为都一样。

反码和原码

反码（Ones’ Complement）与原码（Two’s Complement）不同之处在于 反码的负权是 $ -(2^{w-1}-1) $,补码中负权是 $ -2^{w-1} $ 相当于负数的补码+1， 或者按照更好的理解就是如果最高位为1，那么其他位0变成1,1变成0就对了。 或者更准确的理解是： 对于反码 $ -x = [111…11] - x $,很多个1，所以是Ones’ Complement； 对于补码 $ -x = 2^w - x $,有一个2，所以是Two’s Complement

原码（Sign-Magnitude）则是最高位符号位，其他按照无符号表示。

反码和原码的问题在于存在+0和-0两种表示0的方法。几乎所有现代机器都用补码，反码逐渐淘汰。 在浮点数中使用了原码编码。

补码的快速计算方法

补码在汇编中经常出现，刚通计算练习，总结出一点计算补码的心得，举例说明：

mov 0xfffffec8(%ebp), %eax

如上的补码0xfffffec8共84 = 32位，看上去很复杂，实际上很多个f，即很多个零， 这样，先计算其对应正数值，即计算机课上常常提到的“反码+1”， 用数学表示就是： $ -x = [111…11] - x + 1$ 那么: f - e = 1 f - c = 3 f - 8 = 7 那么对应正数是0x137 + 0x1 = 0x138 = 1256 + 3*16 + 8 = 256 + 48 + 8 = 312 因此，0xfffffec8 = -312

有符号数和无符号数的转换

位值不变，只是不同解释方式的数值不同。 对于u_i = (unsigned int)i:

• $if (i >= 0) u_i = i;$
• $if (i < 0) u_i = i + 2^w$ ,w为位个数，例如32位

转换除了显示还有隐式，例如：

int tx,ty
unsigned int ux, uy

//explicit
tx = (int) ux;
uy = (unsigned int) ty;
//implicit
tx = ux; /*Cast to signed*/
uy = ty; /*Cast to unsigned*/

特别要注意隐式转换

尤其是关系运算符 例如：if( -1 < 0U ),实际上是false， 因为关系运算符中存在unsigned则将其中的signed转换为unsigned，因此实际是if(4294967295U < 0U)

signed vs. unsigned in C

C语言并没规定有符号数采用什么表示， 但几乎所有机器都采用补码，并默认通常的书为有符号， 如果要特别声明为无符号，则加后缀U或者u，例如12345U、0x1A2Bu

扩展一个数字的位表示

即为了表示更大数，扩展位数。 对于unsigned，用零扩展，高位全补0； 对于signed补码，用符号扩展，负数补1，其他补0。

当遇到同时进行数位扩展和有符号/无符号转换时， C语言要求，先进行数位扩展，例如：

short sx = -12345;
unsigned uy = sx;
// 首先扩展位数，即 (int)sx;
// 然后再符号转换，即 (unsigned) (int)sx;

截断数字

与扩展数值位数相反，直接阶段高位，有可能数值变化。

总结

总之，当遇到隐式类型转换等非直观的错误时要非常小心，例如：

/* bug code, CSAPP 2.25*/
float sum_elements(float a[], unsigned length) {
    int i;
    float result = 0;

    for(i = 0; i < length - 1; i++) //length -1 溢出，结果为Umax
        result += a[i];

    return result;
}

上述代码中，当length = 0,本意应该返回0.0， 实际上因为i < length -1因为 0U - 1 溢出，结果为 Umax，所以该条件总为真，且指针指向了错误的地址。

错误代码2：

// CSAPP Q-2.26
size_t strlen(const char *s);

int strlonger(char *s, char *t) {
    //return strlen(s) - strlen(t) > 0;//错误
    return strlen(s) > strlen(t);
}

看上去没啥问题，但是，size_t原来是unsigned int类型的。

总结1：最好不要出现隐式转换，例如int到size_t的转换 总结2：最好不用无符号，当然无符号有其非常适合的应用场景，例如位的集合，并不需要符号。

整型运算

两数相加可能会是负数（溢出），x < y和x - y < 0可能结果不一样，这是计算机运算的有限性造成的。

无符号加法

对于C语言这样的有限精度的计算而言（Lisp除外），计算可能会出现溢出。无符号加法的溢出可以理解为加法取模， 即 z = x + y 等价于 z = (x + y) mod 2^w，如果溢出，则cut掉2^w。 为了判断是否溢出，如果 (z < x)&&(z < y) 则溢出。

用数学表示就是：

模数加法形成了一种数学结构，称为阿贝尔群（Abelian group）。 它是可交换，可结合的，有一个单位元0，且每个元素都有一个加法逆元。

补码加法

实际上，大多数计算机使用同样的机器指令执行无符号和有符号（对于补码）的加法。

当负数+负数得到正数时（加上了2^w），发生负溢出。 当正数+正数得到负数时（减少了2^w），发生正溢出。 （正数 + 负数 显然不会溢出）

补码的负值（补码非）

数学意义上来说即若 x + y = 0， 则y是x的负值，或者写作-x。 对于补码而言，唯一要考虑的是 $2^{w-1}$这一个数的情况，因为没有对应的整数， 实际上根据对应加法规则，负值的值为：

// CSAPP Q-2.32

// 用于判断补码 x + y是否溢出，较简单，略
int tadd_ok(int x, int y);

// bug code
int tsub_os(int x, int y) {
    return tadd_ok(x, -y); //很自然的想法的通过加法判断来判断减法
} // 然而当 y = 2 ^ {w-1} 时，-y = y, 因此需要考虑此特殊情况，改进代码略

补码负值的位级运算

就是课上常常提到的每一位都取反 + 1，即 -x = ~x + 1

无符号乘法

补码的乘法

对于补码的乘法，其位级运算和无符号乘法相同，加法也是同样的规则。 因此对于机器而言，它不用考虑到底是补码还是无符号。

乘以常数

对大多数机器，整数乘法相当慢，约10个或更多时钟周期， 而其他比如 加法、减法、位级运算、移位只需要1个时钟周期， 因而考虑用移位运算优化乘法，例如下式都是求x*14： 当然，这里的常数是整数

    x * 14
    (x << 3) + (x << 2) + (x << 1) // 14 = 2^3 + 2^2 + 2
    (x << 4) - (x << 1) // 14 = 2^4 - 2

除以2的幂

对于大多数机器，整数除法比乘法还要慢，需要30或更多个时钟周期。 可采用右移加速，无符号用逻辑右移，补码用算术右移 此时，只有除以2^k，才能用右移优化， 由于整数除法也会有舍入的误差，例如 $\lceil -30/4 \rceil = -7 = \lfloor -27/4 \rfloor$，$\lceil -32/4 \rceil = -8 = \lfloor -29/4 \rfloor$， 为了得到正确的舍入（即避免负数除法与右移结果差1），可通过偏置（biasing）的方式做除法， 即如果 $x<0$ 首先 $x+=2^k - 1$ ,再做除法，除以 $2^k$ ,写出程序即为：

(x < 0 ? (x + (1<<k)) - 1) : x) >> k;

关于整数运算最后的思考

整数运算实际上是一种模运算，补码和无符号的加减乘除实际上从机器的角度是一样的。 C的某些规定可能会产生意想不到的结果，特别注意unsigned数据类型以及溢出。