使用 位编码整数有两种不同的方式：

1. 只能表示非负数（零、正数），即无符号数的编码。
2. 既能表示非负数，也能表示负数，即有符号数的编码、补码编码。

下表是一些数学术语，用于精确定义和描述计算机如何编码和操作整数。

符号	类型	含义
$B2T_w$	函数	二进制转补码
$B2U_w$	函数	二进制转无符号数
$U2B_w$	函数	无符号数转二进制
$U2T_w$	函数	无符号数转补码
$T2B_w$	函数	补码转二进制
$T2U_w$	函数	补码转无符号数
$TMi{n}_w$	常数	最小补码值
$TMa{x}_w$	常数	最大补码值
$UMa{x}_w$	常数	最大无符号数
${+}_w^t$	操作	补码加法
${+}_w^u$	操作	无符号数加法
${\ast }_w^t$	操作	补码乘法
${\ast }_w^u$	操作	无符号数乘法
${-}_w^t$	操作	补码取反
${-}_w^u$	操作	无符号数取反

下标w表示整数的位数。

整型数据类型

C语言支持多种整型数据类型——表示有限范围的整数。每种类型都可以用关键字指定大小，如char、short、long，同时还可以用unsigned表示是无符号的。
无符号数永远是>=0的。有符号数既能表示负数，又能表示非负数，在“典型”实现中，负数的表示范围比非负数大1（不对称）。

C语言标准定义了每种数据类型必须能够表示的最小取值范围。对有些数据类型则要求正数和负数的取值范围是对称的。
C/C++支持无符号数和有符号数，Java只支持有符号数。

无符号数的编码

假设一个整数有w位，其编码为$[x_{w-1},x_{w-2},...,x_0]$，写作位向量$\vec{x}$。在这个编码中，每个位$x_i$取值为0或1。

原理：无符号数的编码定义。
对向量$\vec{x}=[x_{w-1},x_{w-2},...,x_0]$，有
$$\begin{array}{r}B2U_w(\vec{x})\dot{=}\sum _{i=0}^{w-1}{x}_i{2}^i\end{array}$$

$\dot{=}$表示左边被定义为等于右边。

函数 $B2U_w(\vec{x})$将一个长度为w的0、1串映射为非负整数，函数的返回值就是该编码的无符号数值。

$\vec{x}$所能表示的最小值为[0, 0, ..., 0]，w个0，该编码对应的无符号数值为0；最大值是[1, 1, ..., 1]，w个1，该编码对应的无符号数值为 $UMa{x}_w\dot{=}B2U_w([1,1,...,1])=\sum _{i=0}^{i=w-1}{2}^i=2^w-1$。
因此，函数$B2U_w$能够被定义为一个映射：{0,1}w→{0,1,2,...,2w−1}\{0, 1\}^w \to \{0, 1, 2, ..., 2^{w}-1\}{0,1}w→{0,1,2,...,2w−1}。

原理：无符号数编码是唯一的。
函数$B2U_w$是一个双射。
对函数 $B2U_w(\vec{x})$而言，给定一个位向量$\vec{x}$，有唯一对应的无符号数值。
对函数 $U2B_w(y)$而言，给定一个无符号数值$y$，有唯一对应的位向量$\vec{x}$。

补码编码

最常见的有符号数的计算机表示方法是补码编码。在这个定义中，将最高有效位解释为负权。
原理：补码编码定义。
对向量$\vec{x}=[x_{w-1},x_{w-2},...,x_0]$，有
$$\begin{array}{r}B2T_w(\vec{x})\dot{=}-x_{w-1}{2}^{w-1}+\sum _{i=0}^{w-2}{x}_i{2}^i\end{array}$$
最高有效位$x_{w-1}$也称为符号位，它的权重为$-2^{w-1}$。$x_{w-1}$为1时，该值是负数；为0时，该值是非负数。

$\vec{x}$所能表示的最小值为[1, 0, ..., 0]，值为$TMi{n}_w\dot{=}-2^{w-1}$；最大值为[0, 1, ..., 1]，值为$TMa{x}_w=2^{w-1}-1$。
因此，函数$B2T_w$能够被定义为一个映射：{0,1}w→{−2w−1,−2w−1+1,...,2w−1−2,2w−1−1}\{0, 1\}^w \to \{-2^{w-1}, -2^{w-1} + 1, ..., 2^{w-1}-2, 2^{w-1}-1\}{0,1}w→{−2w−1,−2w−1+1,...,2w−1−2,2w−1−1}。

原理：补码编码是唯一的。
函数$B2T_w$是一个双射。
对函数 $B2T_w(\vec{x})$而言，给定一个位向量$\vec{x}$，有唯一对应的有符号数值。
对函数 $T2B_w(y)$而言，给定一个有符号数值$y$，有唯一对应的位向量$\vec{x}$。

相同的位向量 $\vec{x}$ 在不同的语境下有不同的含义。
如果 $\vec{x}$ 是[1, 1, ..., 1]的串，无符号数值语境下表示UMax，有符号数值语境下表示-1。
如果 $\vec{x}$ 是[1, 0, ..., 0]的串，无符号数值下表示正数 $2^{w-1}$，有符号数值下表示负数 $-2^{w-1}$
最高位为0的情况下，无符号数值和有符号数值相等。

C语言标准并没有要求采用补码形式表示有符号数，但几乎所有的机器都是这么做的。如果程序员希望代码具有最大的可移植性，那么就该假定有符号数是采用补码编码的。

补码：对于非负数x，用$2^w-x$的值表示-x。
反码：对于非负数x，用$2^w-1-x$的值表示-x。

确定大小的整数类型

ISO C99标准定义了确定大小的整数类型。如int32_t和uint64_t。无论在哪台机器上，它们都分别表示32位的有符号数和64位的无符号数。标准也定义了诸如INT32_MAX、INT32_MIN、UINT64_MAX这样的宏，表示对应整数类型值的范围。标准也定义了诸如PRId32、PRIu64这样的宏，表示格式化打印相应的整型变量时的宽度。

相比于C/C++，Java标准定义更明确一些：仅支持有符号数、整型的表示范围确定、采用补码编码。

练习1

位向量 $\vec{x}$ 的长度w = 4，填写下表。

位向量 x		B2U	B2T
十六进制	二进制
0xE	[1110]	14	-2
0x0	[0000]	0	0
0x5	[0101]	5	5
0x8	[1000]	8	-8
0xD	[1101]	13	-3
0xF	[1111]	15	-1

练习2

将下列使用32位补码表示的16进制数转换成等价的10进制数。

1. 0x2e0
   736
2. -0x58
   -88
3. 0x28
   40
4. -0x30
   -48
5. 0x78
   120
6. 0x88
   136
7. 0x1f8
   504
8. 0xc0
   192
9. -0x48
   -72

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

相同位宽的有符号数和无符号数之间强制类型转换的结果是底层位值不变，但改变了解释这些位的方式。比如把short类型的-12345转换成unsigned short会得到53191，事实上这两个数的底层位值是一模一样的。再比如把UINT_MAX强转为有符号数会得到-1，UINT_MAX和-1的底层位值都是[1, 1, ..., 1]。
因此，我们可以通过分析二进制表示，完成有符号数和无符号数之间的转换。

原理：从有符号数转无符号数。
对于位宽为w的有符号数$x$，二进制表示为位向量 $\vec{x}$，满足$TMi{n}_w<=x<=TMa{x}_w$，有：
$$\begin{array}{r}T2U_w(x)\dot{=}B2U_w(T2B_w(x))=x+x_{w-1}{2}^w=\{\begin{array}{ll}x+2^w,& x<0\\ x,& x>=0\end{array}\end{array}$$

有符号数的最高位权值是$-2^{w-1}$，无符号数的最高位权值是$2^{w-1}$，两者相差$2^w$。所以当最高位为1（$x<0$）时，无符号数值比有符号数值大$2^w$。

原理：从无符号数转有符号数。
对于位宽为w的无符号数$x$，二进制表示为位向量 $\vec{x}$，满足$0<=x<=UMa{x}_w$，有：
$$\begin{array}{r}U2T_w(x)\dot{=}B2T_w(U2B_w(x))=x-x_{w-1}{2}^w=\{\begin{array}{ll}x,& x<=TMa{x}_w\\ x-2^w,& x>TMa{x}_w\end{array}\end{array}$$

当最高位为1（$x>TMa{x}_w$）时，有符号数比无符号数小$2^w$。

练习

补充下面的表格。

$x$	$T2U_4(x)$
-8	8
-3	13
-2	14
-1	15
0	0
5	5

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

在C语言中，声明一个常量时，默认是有符号的，如123、0xAB。要创建无符号常量，需要加上后缀字符u或U，如123u、0xABu。

可以显示转换，如：

int i;
unsigned int u;i = (int)u;
u = (unsigned int)i;

可以隐式转换，如：

int i;
unsigned int u;i = u;
u = i;

或

int i;
unsigned int u;printf("%u\n", i);
printf("%d\n", u);

当执行一个运算时，如果它的一个运算数是有符号的，另一个运算数是无符号的，那么C语言会隐式地将有符号参数转换为无符号数，再进行无符号数之间的运算。

练习

假设在采取补码运算的32位机器上执行以下运算，填写运算的类型和结果。

表达式	类型	求值
-2147483647-1 == 2147483648U	无符号	1
-2147483647-1 < 2147483647	有符号	1
-2147483647-1U < 2147483647	无符号	0
-2147483647-1 < -2147483647	有符号	1
-2147483647-1U < -2147483647	无符号	1

扩展一个数字的位表示

要将一个无符号整数转换为一个更大的数据类型，只需要简单地在高位加0，这种运算被称为无符号数的零扩展。
要将一个有符号整数转换为一个更大地数据类型，需要在高位加符号位，这种运算被称为补码的符号扩展。

当数据扩展和有无符号转换同时出现时，C标准要求先扩展、后进行有无符号转换。

short sx = -12345;
unsigned int uy = sx;  // 等价于unsigned int uy = (unsigned int)(int)sx;
// uy的十六进制表示为0xFFFFCFC7

如果先做符号转换、再扩展，那uy的十六进制表示为0x0000CFC7，就无法正确表示原值sx的符号位。

练习1

下面各个补码对应的有符号数值是多少？

1. [1011]
   $-2^3+2^1+2^0=-5$
2. [11011]
   $-2^4+2^3+2^1+2^0=-5$
3. [111011]
   $-2^5+2^4+2^3+2^1+2^0=-5$

后两个有符号数分别是第一个有符号数符号扩展1位和2位的结果。符号扩展不会改变补码表示的数值大小。

练习2

考虑下面的C函数：

int fun1(unsigned word)
{return (int)((word << 24) >> 24);
}int fun2(unsigned word)
{return ((int)word << 24) >> 24;
}

填写下表。

$w$	$fun1(w)$	$fun2(w)$
0x00000076	0x00000076	0x00000076
0x87654321	0x00000021	0x00000021
0x000000C9	0x000000C9	0xFFFFFFC9
0xEDCBA987	0x00000087	0xFFFFFF87

截断数字

当将一个w位的数截断为一个k位的数时，会丢弃高w-k位，并对低k位做新的解释。截断一个数可能会改变它的值（即溢出）。

练习

将一个4位数值截断为一个3位数值，填写下表。

十六进制		无符号（十进制）		补码（十进制）
原始值	截断值	原始值	截断值	原始值	截断值
0x0	0x0	0	0	0	0
0x2	0x2	2	2	2	2
0x9	0x1	9	1	-7	1
0xB	0x3	11	3	-5	3
0xF	0x7	15	7	-1	-1

关于有符号数与无符号数的建议

整数的扩展和截断、有符号数和无符号数之间的隐式转换，会导致程序错误或漏洞。而这些不符合预期的行为有时很难被程序员发现。避免这些错误的方法有：

1. 整数运算时，统一符号。
2. 如果涉及到整数类型的变化，使用强制转换代替隐式转换，方便程序员发现问题。

练习1

考虑下面的代码，当length等于0时，预期结果是0.0。但实际上，运行时会造成一个内存错误。为什么？该如何修改代码？

float sum_elements(float a[], unsigned length)
{float result = 0;for (int i = 0; i <= length - 1; ++i) {result += a[i];}return result;
}

length是无符号数，i是有符号数，程序执行i <= length - 1时，程序会按无符号数执行该运算。
当length = 0时，在无符号数的语境下，length - 1等于UINT_MAX，i的值永远小于UINT_MAX，所以程序会访问未知内存，导致运行时错误。

解决办法是：

1. 把length的类型改为int。当length = 0时，在有符号数的语境下，length - 1等于-1，i的值是0，程序立即返回0.0。
2. 把i <= length - 1改为i < length。

练习2

下面的代码用来判断一个字符串是否比另一个更长。在头文件stdio.h中，size_t是无符号整型。

// 库函数
size_t strlen(const char *s);// 用户代码
int strlonger(char *s, char *t)
{return strlen(s) - strlen(t) > 0;
}

1. 在什么情况下，这个函数会产生不正确的结果？为什么？
   如果strlen(s)小于strlen(t)，strlen(s) - strlen(t)的预期结果应该是个负数， strlen(s) - strlen(t) > 0的预期结果应该是0。
   但strlen(s)和strlen(t)的返回值都是无符号数，strlen(s) - strlen(t)的结果也是无符号数，无符号数一定是>=0的。因此程序会返回1，而不是0，和预期不符。
2. 如何修改代码，使其正确。
   把return strlen(s) - strlen(t) > 0;改为return strlen(s) > strlen(t);