凌云的博客

整数表示

分类：data| 发布时间：2025-01-29 22:11:00

整型数据类型

C 支持多种整型数据类型——表示有限范围的整数。

C 和 C++ 都支持有符号（默认）和无符号数。 Java 只支持有符号数。

无符号和二进制补码编码

假设有一个整数数据类型有 w 位。 我们可以将向量写成 $\overrightarrow{x}$，表示整个向量，或者写成 [x_w-1,x_w-2,...,x₀]，表示向量中的每一位。 把$\overrightarrow{x}$ 看做一个写成二进制表示的数，我们就获得了$\overrightarrow{x}$的无符号表示。

我们用一个函数 B2U_w 来表示这种形式：

$${\mathrm{B2U}}_w(\overrightarrow{x})\doteq \sum _{\mathrm{i=0}}^{\mathrm{w-1}}{x}_i{2}^i$$ $$\mathrm{等式\; 2.1}$$

符号 ≐ 表示左手边被定义为等于右手边。 函数 B2U_w 将一个长度为 w 的 0、1 串映射到非负整数。 它的最小值是用位向量 [0,0,...,0] 表示，也就是整数 0，而它的最大值是用位向量 [1,1,...,1] 表示，也就是整数值 ${\mathrm{UMax}}_w\doteq {\sum }_{\mathrm{i=0}}^{\mathrm{w-1}}{2}^i=2^w\mathrm{-1}$

因此函数 B2U_w 能够被定义为一个映射 B2U_w：{0, 1}_w→{0,...,2^w-1}。

注意 B2U_w 是一个双射——对于每一个长度为 w 的位向量，都有一个唯一的值与之对应；反过来，在 0~2^w-1 之间的每一个整数都有一个唯一的长度为 w 的位向量二进制表示与之对应。

最常见的有符号数的计算机表示方式是二进制补码形式。 它将位的最高有效位解释为负权。 我们用函数 B2T_w（表示 “二进制到二进制补码”，长度为 w）来表示这种解释：

$${\mathrm{B2T}}_w(\overrightarrow{x})\doteq -x_{w-1}{2}^{w-1}+\sum _{\mathrm{i=0}}^{\mathrm{w-2}}{x}_i{2}^i$$ $$\mathrm{等式\; 2.3}$$

最高有效位也称为符号位。当被置为 1 时，表示值为负，而当被设置为 0 时，值为非负。 它能表示的最小值是位向量 [1,0,...,0]，其整数值为 TMin≐-2^w-1。 而最大值是位向量 [0,1,...,1]，其整数值为：${\mathrm{TMax}}_w\doteq {\sum }_{\mathrm{i=0}}^{\mathrm{w-2}}{x}_i{2}^i=2^{\mathrm{w-1}}-1$。

同样地 B2T_w 也是一个双射，B2T_w：{0, 1}_w→{-2^w-1,...,2^w-1-1}，对于可表示范围内的每个位模式都有一个唯一的整数与之对应。

下表展示了一些“有趣的”数字

数	字长 w
	8	16	32	64
UMaxw	0xFF 255	0xFFFF 65 535	0xFFFFFFFF 4 294 967 295	0xFFFFFFFFFFFFFFFF 18 446 744 073 709 551 615
TMaxw	0x7F 127	0x7FFF 32 767	0x7FFFFFFF 2 147 483 647	0x7FFFFFFFFFFFFFFF 9 223 372 036 854 775 807
TMinw	0x80 -128	0x8000 -32 768	0x80000000 -2 147 483 648	0x8000000000000000 -9 223 372 036 854 775 808
-1	0xFF	0xFFFF	0xFFFFFFFF	0xFFFFFFFFFFFFFFFF
0	0x00	0x0000	0x00000000	0x0000000000000000

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

既然 B2U_w 和 B2T_w 都是双射，它们就有明确定义的逆映射。 将 U2B_w 定义为 B2U_w^-1，而将 T2B_w 定义为 B2T_w^-1。

考虑函数 U2T_w(x)≐B2T_w(U2B_w(x))，其输入是一个 0~2^w-1 之间的值，得到一个 -2^w-1~2^w-1-1之间的值，这两个数由相同的位模式。

比较等式 2.1 和 2.2，我们可以发现对于位模式 $\overrightarrow{x}$，计算 ${\mathrm{B2U}}_w\left(\overrightarrow{x}\right)-{\mathrm{B2T}}_w\left(\overrightarrow{x}\right)=x_{w-1}(2^{w-1}-{-2}^{w-1})=x_{w-1}{2}^w$。 得到 ${\mathrm{B2U}}_w\left(\overrightarrow{x}\right)=x_{w-1}{2}^w+{\mathrm{B2T}}_w\left(\overrightarrow{x}\right)$，令 $x={\mathrm{B2T}}_w\left(\overrightarrow{x}\right)$，有：

$${\mathrm{B2U}}_w\left({\mathrm{T2B}}_w\right(x\left)\right)={\mathrm{T2U}}_w\left(x\right)=x_{w-1}{2}^w+x$$ $$\mathrm{等式\; 2.5}$$

在 x 的二进制补码表示中，位 x_w-1 决定了 x 是否为负，得到：

$${\mathrm{T2U}}_w\left(x\right)=\{\genfrac{}{}{0ex}{}{x+2^w,x<0}{x,x\ge 0}$$ $$\mathrm{等式\; 2.6}$$

当将一个有符号数映射为它相应的无符号数是，负数就被转换成了大的正数，而非负数保持不变。

我们推导一个无符号数 x 和与之对应的有符号数 U2T_w(x) 之间的关系。 令$x={\mathrm{B2U}}_w\left(\overrightarrow{x}\right)$ ，我们有

$${\mathrm{B2T}}_w\left({\mathrm{U2B}}_w\right(u\left)\right)={\mathrm{U2T}}_w\left(u\right)=-u_{w-1}{2}^w+u$$ $$\mathrm{等式\; 2.7}$$

在 x 的无符号表示中，位 x_w-1 决定了 x 是否大于或者等于 2^w-1，得到：

$${\mathrm{U2T}}_w\left(u\right)=\{\genfrac{}{}{0ex}{}{u,u<2^{w-1}}{u-2^w,u\ge 2^{w-1}}$$ $$\mathrm{等式\; 2.8}$$

函数 U2T 把大于 2^w-1-1 的数字转换为负值。

C 中的有符号与无符号数

C 标准没有指定有符号数的表示，但是几乎所有的机器都使用二进制补码。

C 允许无符号数和有符号数之间转换。原则是基本的位表示保持不变。 因此在一台二进制补码机器上，当从无符号数转换为有符号数时，效果就是应用函数 U2T_w，而从有符号数转换为无符号数时，就是应用函数 T2U_w，其中 w 表示数据类型的位数。

C 执行一个运算时，如果它的一个运算数是有符号的而另一个是无符号的，那么 C 会隐含地将有符号参数强制转换为无符号数，并假设这两个数都是非负的。

下表展示了 32 位机器上 C 的升级规则（promotion rule）的效果：

表达式	类型	求值
0==0U	无符号	1
-1<0	有符号	1
-1<0U	无符号	0*
2147483647>-2147483647-1	有符号	1
2147483647U>-2147483647-1	无符号	0*
2147483647>(int)2147483648U	有符号	1*
-1>-2	有符号	1
(unsigned) -1 > -2	无符号	1

扩展一个数字的表示

要将一个无符号整数转换为一个更大的数据类型，我们只要简单地在表示开头添加 0。 这种运算被称为零扩展。 要将一个补码数字转换为一个更大的数字类型，规则是执行一个符号扩展，在表示中添加最高有效位的值。 如果原始值为 [x_w-1,x_w-2,...,x₀]，那么扩展后的表示就为 [x_w-1,...,x_w-1,x_w-1,x_w-2,...,x₀]。

如何证明符号扩展工作正确呢？ 我们需要证明 B2T_w+k([x_w-1,...,x_w-1,x_w-1,x_w-2,...,x₀])=B2T_w([x_w-1,x_w-2,...,x₀])，为了证明这个表达式，我们只需要证明：B2T_w+1([x_w-1,x_w-1,x_w-2,...,x₀])=B2T_w([x_w-1,x_w-2,...,x₀])，然后通过归纳法即可证明原式。

用等式 2.4 展开左手边的表达式：

$${\mathrm{B2T}}_{\mathrm{w+1}}([x_{\mathrm{w-1}},x_{\mathrm{w-1}},x_{\mathrm{w-2}}\mathrm{,...,}{x}_0])={\mathrm{-x}}_{\mathrm{w-1}}{2}^w+\sum _{\mathrm{i=0}}^{\mathrm{w-1}}{x}_i{2}^i$$ $$={\mathrm{-x}}_{\mathrm{w-1}}{2}^w+x_{\mathrm{w-1}}{2}^{\mathrm{w-1}}+\sum _{\mathrm{i=0}}^{\mathrm{w-1}}{x}_i{2}^i$$ $$={\mathrm{-x}}_{\mathrm{w-1}}(2^w-2^{\mathrm{w-1}})+\sum _{\mathrm{i=0}}^{\mathrm{w-2}}{x}_i{2}^i$$ $$={\mathrm{-x}}_{\mathrm{w-1}}{2}^{\mathrm{w-1}}+\sum _{\mathrm{i=0}}^{\mathrm{w-2}}{x}_i{2}^i$$ $$={\mathrm{B2T}}_w\left(\right[x_{\mathrm{w-1}},x_{\mathrm{w-2}},\mathrm{...},x_0\left]\right)$$

截断数字

将一个 w 位的数$\overrightarrow{x}=[x_{\mathrm{w-1}},x_{\mathrm{w-2}},\mathrm{...},x_0]$ 截断为 k 位时，我们会丢弃高 w-k 位，得到一个位向量： $\overrightarrow{x}=[x_{\mathrm{k-1}},x_{\mathrm{k-2}},\mathrm{...},x_0]$。 截断一个数字可能会改变它的值——溢出的一种形式。 对于一个无符号数字 x，截断它到 k 位的结果就相当于计算 x mod 2^k。 通过应用模运算到等式 2.1 就可以得到：

$${\mathrm{B2U}}_w\left(\right[x_{\mathrm{w-1}},x_{\mathrm{w-2}},\mathrm{...},x_0\left]\right)mod{2}^k=\left[\sum _{\mathrm{i=0}}^{\mathrm{w-1}}{x}_i{2}^i\right]mod{2}^k$$ $$=\left[\sum _{\mathrm{i=0}}^{\mathrm{k-1}}{x}_i{2}^i\right]mod{2}^k$$ $$=\sum _{\mathrm{i=0}}^{\mathrm{k-1}}{x}_i{2}^i$$ $$={\mathrm{B2U}}_k\left(\right[x_{\mathrm{k-1}},x_{\mathrm{k-2}},\mathrm{...},x_0\left]\right)$$

对于一个二进制补码数字 x，相似的推理表明 ${\mathrm{B2T}}_w\left(\right[x_{\mathrm{w-1}},x_{\mathrm{w-2}},\mathrm{...},x_0\left]\right)mod{2}^k={\mathrm{B2T}}_k\left(\right[x_{\mathrm{k-1}},x_{\mathrm{k-2}},\mathrm{...},x_0\left]\right)$。

截断的结果有如下等式：

$${\mathrm{B2U}}_k[x_{k-1},x_{k-2},\mathrm{...},x_0]={\mathrm{B2U}}_w[x_{w-1},x_{w-2},\mathrm{...},x_0]mod{2}^k$$

$$\mathrm{等式\; 2.9}$$

$${\mathrm{B2T}}_k[x_{k-1},x_{k-2},\mathrm{...},x_0]={\mathrm{U2T}}_k\left({\mathrm{B2T}}_w\right[x_{w-1},x_{w-2},\mathrm{...},x_0]mod{2}^k)$$

$$\mathrm{等式\; 2.10}$$