整数的表示

位模式

不同类型的数据,比如数字、文本、图片、视频等都以二进制形式(即一连串的1和0)存储在计算机中,我们称之为位模式。将位模式以不同的解析方式还原出来时,用户便看到了不同类型的数据。例如位模式01000001既可以表示数字65,也可以表示字符A。下面的show_bytes函数用来打印数据的位模式,打印结果以十六进制形式给出:

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>

typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, int len)
{
for (int i = 0; i < len; i++) {
printf(" %.2x", start[i]);
}
printf("\n");
}

将数据转换成位模式的过程称为编码(encoding),整数的编码方式主要有两种,无符号编码(Unsigned Encoding)和补码编码(Two’s Complement Encoding)。

编码类型

无符号编码

把位模式$\vec{x} = [x_{w-1}, x_{w-2}, … , x_0]$看做一个二进制表示的数,用函数$B2U_w$(Binary to Unsigned)来表示从位模式到无符号编码表示的整数数值的转换关系:

$$B2U_w(\vec{x}) \doteq \sum_{i=0}^{w-1} x_i 2^i$$

因此,宽度为$w$的位模式用无符号编码方式表示的无符号整数的范围是$0$到$2^w-1$。C语言中,unsigned类型的数据采用无符号编码。

补码编码

表示有符号数一般采用补码编码方式。用函数$B2T_w$(Binary to Two’s Complement)来表示从位模式到补码编码表示的整数数值的转换关系:

$$B2T_w(\vec{x}) \doteq -x_{w-1} 2^{w-1} + \sum_{i=1}^{w-2} x_i2^i$$

最高位$x_{w-1}$称为符号位,符号位为0时表示为非负数,为1时表示为负数。补码编码方式表示的整数范围是$-2^{w-1}$到$2^{w-1}-1$。

整数类型转换

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

在C语言中,不同数据类型之间可以转换。例如,强制类型转换运算(unsigned)xx转化成一个无符号类型。下面的C代码打印两个变量的数值以及它们的位模式:

1
2
3
4
5
6
7
short int v = -12345;
usigned short uv = (unsigned short) v;
/* 打印数值和位模式 */
printf("v = %d:");
show_bytes((byte_pointer)&v, sizeof(v));
printf("uv = %u:");
show_bytes((byte_pointer)&uv, sizeof(uv));

编译运行之后得到如下结果:

1
2
v = -12345: c7 cf
uv = 53191: c7 cf

即转换前后的位模式没有改变,解析方式的不同造成了不同的结果。类似地,0xff用无符号编码表示正数255,用补码编码表示负数-1。依照转换前后位模式不变的原则,可以得到从有符号数到无符号数的转换函数$T2U_w$(Two’s Complement to Unsigned):

$$T2U_w(x) = B2U_w(T2B_w(x)) = x_{w-1} 2^w + x$$

类似地,从无符号数到有符号数的转换函数$U2T_w$(Unsigned to Two’s Complement)为:

$$U2T_w(u) = B2T_w(U2B_w(u)) = -u_{w-1} 2^w + u$$

C语言中,大多数常数默认为符号数(signed),在末尾加上Uu即声明该数字为无符号常数。C语言允许无符号数和有符号数之间的转换,转换前后位模式保持不变,结果的差异由解析方式的不同造成。从无符号数转换到有符号数时,使用函数$U2T_w$,从符号数转换为无符号数时,使用函数$T2U_w$。

另外,执行运算时,如果一个是有符号数而另一个是无符号数,那么C语言会隐式地将有符号参数强制类型转换为无符号数。例如,考虑比较式-1 < 0U ,因为第二个运算是为无符号的,第一个运算数会被隐式地转换成无符号数,-1变成了一个很大的正数,表达式等价于4294967295U < 0U,得到了和预想中不一样的结果,这一点尤其要注意。

扩展位模式

一种常见的运算是在不同字长的整数之间转换,同时保持数值不变。将一个无符号数转换成一个更大的数据类型,执行零扩展(zero extension),即在开头添加0。将一个补码数字转换为一个更大的数据类型执行符号扩展(sign extension),即在开头添加符号位,如果是负数,则添加1,如果是正数,则添加0。如果转换中不仅有字长的扩展还有符号的改变,则转换的原则如下:首先改变大小,然后完成符号转换。例如下面的C代码:

1
2
3
4
5
short sx = -12345;
unsigned uy = sx;

printf("uy = %u:\t", uy);
show_bytes((byte_pointer)&uy, sizeof(unsigned));

可以得到输出uy = 4294954951: ff ff cf c7,即(unsigned)sx等价于(unsigned)(int)sx

截断数字

有些情况要从长字节转换到短字节,例如从intchar,这种情况称作截断。将一个$w$位的数字$\vec{x} = [x_{w-1}, x_{w-2}, … , x_0]$转换成一个$k$位的数字,把前$w-k$位舍弃即可,得到新的位模式$\vec{x} = [x_k, x_{k-1}, … , x_0]$。还是依照位模式不变的原则,根据前面的公式可以计算得到截断后得到的数值。

类型转换总结

凡是涉及到不同整数类型的转换,都要把握一个原则:以位模式为中心。具有相同字节长度的类型之间的转换,位模式不变,字节长度不同的类型之间的转换,对位模式进行扩展或截断操作。最后采用新的解析方式解析位模式便得到类型转换之后的值。

参考

CS:APP