[C++知识库][C/C++]数的存储和表示

1 整数的表示

在C/C++中，整数的表示有两种，一种是无符号的（unsigned integer，简写为U），另一种是有符号的（用Two’s-complement encodings表示，简写为T)

1.1 无符号数

这玩意儿应该是C/C++中特有的，java和python等是没有这种数据格式的。我们假设有一个m位的二进制数，如果这些二进制数是无符号数的编码，那么这些二进制数对应的无符号数（10进制）为

$$B2U_w（x）=\sum _{i=0}^{(w?1)}{x}_i{2}^i$$
如x=1011，则B2U（1011）=11。

从上面式子可知，w位的无符号数的最大值和最小值分别是2^w-1，0

1.2 符号数

这是我们通常意义下的整数，它包含正数和负数。他的编码要求是将最高位当做符号位（负数位），其余位为正数。同样假设有一个m为二进制数，这个二进制数是符号数的编码（这个编码方式叫two’s-complement encodings)，则对应的符号数（10进制）为：

$$B2T_w（x）=?x_{w?1}{2}^{w?1}+\sum _{i=0}^{(w?2)}{x}_i{2}^i$$

如x=0011，则B2U(x)=B2T(x)=3；x=1011，则B2U（1011）=11，B2T（1011）=-5。

由上式可以推导，w位的符号数最大值为
$$\sum _{i=0}^{(w?2)}{x}_i{2}^i$$

最小值为
$$?x_{w?1}{2}^{w?1}$$

此外，若想要让任意的正数变为对应的负数，那么可以先取该正数的two’s-complement encodings，设为T，则（~T）+1就为所求，如： 7 = 0111，（~7）+1 = 1000+1 = 1001 = -7。（注意在4bits的情况下，最大值只是7，请不要取11这种数字）。同样的你要让-7变为7也可以用（~-7）+1来获得。实际上这就是我们通常说的补码形式。

符号数需要注意的地方是，在4bits情况下，最大值是7，如果相加两个最大值得到的不是14，而是-2。

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

假设我们有w位二进制数，则两者的转换为：
$$T2U_w(x)=x+x_{w?1}{2}^w$$
$$U2T_w(u)=?u_{w?1}{2}^w+u$$

上式的推导基于
$$B2U?B2T=x_{w?1}{2}^w$$

我们考虑一个4bits的数，T2U(-7) = -7+16 = 9；这就好像把负数进行翻转成正数一样。
U2T(9) = 9-16 = -7

1.4 补全（extension）和截断（truncating numbers）

1.4.1 无符号的补全

假设我们的机子是一个8bits机子（或者说编译器是处理8bits的），那么我之前的例子中的4bits这个数如果仍要放到这个机子里则必须把他转化为8bits的数。对于无符号数而言可将其拆分为：
$$B2U_w（x）=\sum _{i=h}^{(w?1)}{x}_i{2}^i+\sum _{i=0}^{(h?1)}{x}_i{2}^i$$
其中，w是整个的位数，h是我们目前存的数的位数。则我们只要在h为之后全补上0，则上式仍然等于原数。如5 = 0101，拓展后为 0000 0101;

1.4.2 有符号的补全

我们效仿无符号的拆分，则：
$$B2T_w（x）=?x_{w?1}{2}^{w?1}+\sum _{i=h?1}^{(w?2)}{x}_i{2}^i+\sum _{i=0}^{(h?2)}{x}_i{2}^i$$
显然若
$$\sum _{i=h?1}^{(w?2)}{x}_i{2}^i$$
x全为1，则上式=原数。如 -7 = 1001，拓展后为 1111 1001 = -7

1.4.3 截断

截断的发生是因为overflow，溢出。而溢出指的是当前的位数无法存放你想要放的数，比如对于w位的符号数而言，他的最小值是
$$?x_{w?1}{2}^{w?1}$$
用两个最小值相加，得到的是
$$?x_{w?1}{2}^w$$
这意味在二进制下上数左移<<1，如果说目前的“容器”只有w位，那么他就不能存下(w+1)位，因此他只能放弃这个（1）位，而存下w位。比如说4bits下的最小值-8=1000，-8+（-8）=1 0000，但是显然我们存不下第5位，所以-8+（-8） = 0。

另一个例子是“容器”的变更，比如一个int数强转成short数，那么此时也会发生上面说的截断。

假设有一个w位的数，然后放进一个只有k的容器中（w>=k），则无符号数的截断的数学表示如下：

$$B2U_w（x）mod{2}^k=[\sum _{i=0}^{(w?1)}{x}_i{2}^i]mod{2}^k$$

假设w=k+2的情况，则i=k时，(x2^k) mod 2^k = 0，i=k+1时也是如此，这就意味着超过容器k的位数的其他位，无论是什么都将转化为0。而 i = 2时， x2^2 mod 2^k 保留的就是 x2^2 本身。

至于有符号数，同样的我们需要把超过k的位数全部转化为0，因为不要像补全那样补1，所以可以转化成无符号数进行无符号的处理：

$$B2U_w(x)mod{2}^k=U2T_k(B2U_w(x)mod{2}^k)$$

虽然看起来式子很复杂，但实际上他做的事就是截断一下，比如w=4,k=3,则符号数2截断后是 010 = 2; -7 = 1001, 截断后是 001 = 1

1.5 运算

• 由于运算实际上仍然是涉及补全和截断的内容，所以这里不再写具体的操作和公式了，但仍然需要说明的是，因为截断的缘故，无论是无符号的书还是有符号的数，他们的相加永远只能在某个范围内，从而实现一种循环。此外，符号数中，两个正数的相加未必是正数，两个负数的相加未必是负数，因为他们二进制编码的关系以及截断的关系。

• 一个有用的点是乘法，因为历史缘故，以前的机器对于乘法处理不太行，所以很多时候乘法的处理都变成左移右移的操作，比如说：
  $$x\times 14=x(2^3+2^2+2^1)=(x<<3)+(x<<2)+(x<<1)$$
  $$x\times 14=x(2^4?2^1)=(x<<4)?(x<<1)$$

• 除法的操作与乘法类似，但是因为他会存在小数问题，此时在用正数表示时就会有rounding问题，如果是正数则rounding down，如果是负数则rounding up。但是C好像在这方面的处理是只能处理rounding down，他内部的rounding up的操作是用（x+y-1）/y的roungding down实现的。

2 浮点数，IEEE 754标准

2.1 表示

早些时候浮点型数字的表示是五花八门的直到IEEE 754标准，对于一个可能的小数（注意不是任意），他的表示是：

$$V_{进制}=(?1{)}^s\times M_{进制}\times 2^E$$
因此保存一个浮点数我们只需要存储s,M,E这三个数据。对于这3个数的存贮，他们有一个统一的样式

对于C语言的单精度而言，存e的地方又8bits，存f的地方有23bits。

在上面的统一样式下s,M,E的具体存储又有三种类型（他是根据e的情况来分的），但在具体说类型前，需要说一个数字bias，他等于2^(k-1)-1。
（以下全以正数为例）

• 第一种，若e全为0，则：E=1-bias，M=f。这种通常表示接近0的浮点数。
• 第二种，若e不全为0 && 也不全为1，则：E=e-bias, M=f+1。这种表示一般意义下的浮点数。
• 第三种，若e全为1，则：1.若 f全为0，则该数V是无穷数；2. 若f不全为0，则V=NaN，不是数。

假设我们是一个8bits的系统，设k=4，n=3，则考虑以下例子：

这个表有两个地方值得说的：

• 如果我们希望转换240这个数变成240.0这种浮点数，那么240=1111 0000=1.111*2^7，而这个就正是0 1110 111的表示。
• 在确定了e是哪种模式后，在确定E后，我们可以直接写出V的二进制形式，而无需像十进制那样进行转换。

十进制下1/3=0.333333…，我们无法用有限位的小数去表示这样的数，所以我们可能用0.333≈1/3来处理他，所以我们会有精度损失的问题。所以同样的，我们在2进制下也有这种问题，特别是电脑的位数都是固定的情况下。比如说1/10=0.00011001100110011(0011)…，因为电脑只能存有限位，假设只能存23bits，x=0.00011001100110011001100，则会产生误差0.1-x=0.00000000000000000000001100(1100)…。这种误差如果是通过某种方法累计的则会产生由精度带来的问题。

2.2 rounding

对于rounding，我们通常说4舍5入，但是这可能会带来一些统计上的问题，因为1-4是4个数，而5到9是5个数。而这个统计问题在计算机中是一定会有的，因为计算机的位数是有限的，所以必须要rounding。为了在统计意义上消除这个问题，因此定义10进制下的rounding规则如下：

• 1-4，round down
• 5，round to even
• 6-9，round up

round to even是一个“复合”的操作，他的操作步骤为，先确定这个数的round down, round up，如果你要round的位数小于中间数（5），则取round down，大于5则取round up。如果等于5，则判断round up是even的还是round down是even的。

实际上，我们更关心的是二进制的情况，对于任意二进制浮点数数而言，我们都可以写成xxxxxx.yyyyyyz，这种形式（我为了简便，xxxx可以是任意0，1的组合，不一定全是1或0，y同理），此时也分3种情况：

• z=1000…，even
• z>1000…，up
• z<1000…，down

比如说我需要round 1bit处，则对于10.010来说，我们写成10.0|10，后面的10显然=100…，所以使用even，则去掉10为round down，10.0；去掉10+1，10.1为round up，因为0是even所以用round down=10.0。

rounding同样会带来类似精度损失的问题，由于分析相同，此处不再赘述。

2.3 运算

对于他们的运算都可以直接转化为
$$V_{二进制}=(?1{)}^s\times M_{二进制}\times 2^E$$
然后相加或相乘之类的再表示为10进制数，但需要注意的是，浮点数的运算只能支持“可交换律”，x+y=y+x，但是对于“结合律”是有问题的，如x+y+z！=x+(y + z)，而在乘法中，分配律也是有问题的。因此如下面的计算b+c+a+d

t = b+c;
x = a+t;
y = t+d;

这种方法运用了结合律，是有问题的。但是在实际上面来看，虽然带来了问题，但是这种问题通常是小的（？），所以得到的数据还算能用（？）。