信息的表示和处理

2019-04-01 本文已影响0人 Teech

信息的存储

字数据大小

计算机中，字长指的是指针数据标称大小，虚拟地址以字来进行编码的，所以字长w位的机器，可以表示的虚拟内存的范围是0~2^w-1。32位字长的机器可以表示的范围是4GB。一个指针占用的大小，编译的阶段确定。当用gcc -m32的时候，即表明只能在32位字长的机器上运行，生成的可执行文件中，表示了指针的大小被分配了32位，反之用gcc -m64则64位。区别在于代码如何被编译。

寻址和字节顺序

对象的地址是指的对象中连续字节序列中的最小地址。字节如何被排列有两种做法，即大段和小端。

大端：最高有效字节在最前面的方式（内存低地址存储最高的8位），和书写顺序相同。
小端：最低有效字节在最前面的方式（内存高地址存储最高的8位）。低地址存储最低8位，最高地址存储最高8位的形式排序。

表示字符串

c语言中，字符串可以被认为是以null（0）结尾的字符序列，每个字符都是由ASCII 编码。内存中分布的顺序和与字节顺序无关。

移位运算

c语言中提供的位移运算，c语言标准中没有提出到底是右移是逻辑位移还是算术位移，但基本所有的编译器和机器组合都是实现的是算术右移（个人理解因为大部分机器都是基于补码实现的机器）。算术右移n位，最左边补充的n位，都是和原来最高位的bit值相同。在序列位向量[x_w-1,....x₀]中，如果算术右移动n位，即得出的新的位向量位[x_w-1,x_w-1,...,x_w-1,x_w-2,...,x₀],其中[x_w-1的个数位n+1个。位运算左移操作都是在最右边填充0.
移位操作优先级比+,-,*,/都是要低。

整数表示

无符号数的编码

针对向量 $\vec{x}$ = [x_w-1,....x₀] ,
B2U_w( $\vec{x}$ ) = $\sum_{i=1}^{w-1}x_i2^{i}$ .
B2U_w表示把长度w的位向量映射位无符号整数。UMax_w = $\sum_{i=1}^{w-1}x_i2^{i}$ = $2^w-1$ .B2U_w为一个双射，每一个无符号整数都有一个w位的位向量，每一个位向量都可映射为一个唯一的无符号整数。

补码编码

补码的定义：B2T_w( $\vec{x}$ ) = $-x_{w-1}2^{w-1} + \sum_{i=1}^{w-2}x_i2^{i}$ .最高位w-1为符号位。符号位为1时，即为负数。Tmin_w = $-2^{w-1}$ .Tmax_w = $\sum_{i=1}^{w-2}x_i2^{i}$ = $2^{w-1}-1$ .B2T_w同样是一个双射。补码的范围是不对称的。|Tmin_w| = |Tmax_w + 1|.Tmin_w没有对应的正数。最大符号数Umax_w = 2Tmax_w + 1.-1和Umax_w具有相同的表示，即所有位均为1.

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

有符号和无符号数的转换，会保持位不变，只是改变解释这些位的方式。数值可能会改变，但是位不变。如果 0≤x≤Umax_w，函数U2B_w都会给出唯一的w位无符号表示。当Tmin_w≤x≤Tmax_w，函数T2B_w都会给出唯一的w位补码形式表示。当输入一个Tmin_w~Tmax_w之间的数都会对应唯一一个0 ~ Umax_w的值。这两个数具有相同的位模式。反之，则一样。

c语言中无符号数与有符号数。

声明一个常量是。比如0xABCD或者12345 默认是有符号的。如果要申明一个符号整数 $12345_u$ .c语言标准没有说明无符号和有符号之间如何转换，大部分是保持位不变，改变解释位的形式转换。当一些表达式同时出现有符号和符号的时候，c语言会隐似的把有符号转换成无符号的形式。< 和 >这样的关系运算符往往会产生非直观的结果。比如-1 < 0u 表达式结果为1。 2147483647 > (int)2147483648u表达式结果为1。

拓展一个数字的位表示

无符号数的拓展，将无符号数据拓展为一个更大的数据类型，将开头的部分填充0.
补码的拓展，将宽度为w的位向量 $\vec{x}$ = [x_w-1,....x₀] 拓展成为 $w^{'}$ 的位向量 [x_w-1,x_w-1,x_w-1,....x₀] .这个可以算算术填充。可以证明B2T_w+k[x_w-1,x_w-1,x_w-1,....x₀] = B2T_w[x_w-1,....x₀] .

截断数字

截断无符号数，令向量 $\vec{x}$ 为 [x_w-1,....x₀] 截断为k位数字时，会丢弃高w-k位。得到一个新向量 $\vec{x^{'}}$ 位 [x_k-1,....x₀],截取一个无符号数可能会改变数字结果（溢出的一种方式）。数学上采用mod $2^{k}$ 次方的形式表示。
截断补码，令向量 $\vec{x}$ 为 [x_w-1,....x₀] 截断为k位数字时，得到一个新向量 $\vec{x^{'}}$ 位 [x_k-1,....x₀]。有符号数32位53191（十六进制CFC7），截取成16位整数时，-65536 + 53191 = -12345。
当一个有符号负数转变位无符号数时（往往隐式转换），会产生一个很大的符号数，往往就会产生出乎意料的bug，所以尽量不使用无符号数。往往在使用bit位表示不同布尔含义的时候才使用无符号数。

整数运算

无符号数的加法

当 $x,y \in [0,2^w),==> x+y \in [0,2^{w+1})$ .所以当 $x+y \in [2^w,2^{w+1})$ 时，发生溢出。溢出结果是减去 $2^w$ 的结果。 $x+_{w}^{u}y$ 表示，x + y的结果截断位w位在把这个结果看做一个无符号数，这个也是一个形式的模运算。比如x=9，y=12的位表示位[1001]以及[1100].他们的和是21[10101].简单丢弃高位得到[0101]（十进制5）。这个结果和21 mod 16结果一致。

//如果溢出，返回0，不会溢出返回1
int uadd_ok(unsigned x,unsigned y){
     unsigned s = x + y;
     if(s < x) return 0; //等价于 if(s < y) return 0;当且仅当这个情况发生溢出
     return 1;
}

补码加法

给定范围 $-2^{w-1} \leq x,y \leq 2^{w-1}-1$ .
$x+_{w}^{t}y =\left\{ \begin{aligned} & x+y - 2^w , x+y \geq 2^{w-1} （正溢出）\\ & x+y , -2^{w-1} < x+y \leq 2^{w-1} （正常）\\ & x+y + 2^w , x+y < -2^{w-1} （负溢出）\\ \end{aligned} \right.$
对于 $Tmin_w \leq x,y \leq Tmax_w，令s = x + _{w}^{t}y,当且仅当x > 0,y > 0时，s \leq 0时发生正溢出，x<0,y<0时，s\geq0时发生负溢出$

//如果溢出，返回0，不会溢出返回1
//版本1 根据定义
int tadd_ok1(int x,int y){
  int s =  x + y;
  int ret = 1;
  if (x > 0 && y > 0 && s<= 0 ) ret = 0;
  if (x < 0 && y < 0 && s>= 0) ret = 0;
  return ret;
}
//版本2
int tadd_ok2(int x,int y){
  int s = x+ y;
  return (s - x) == y; //等价于(s-y) ==  x,所以只需要判定一个条件即可。
}

补码的非

在 $Tmin_w \leq x \leq Tmax_w$ 中，都有一个逆 $-_{w}^{t}x$ 使得 $-_{w}^{t}x + x = 0$ 。所以
$-_{w}^{t}x =\left\{ \begin{aligned} & Tmin_w , x = Tmin_w \\ & -x \\ \end{aligned} \right.$
在这个也和无符号的逆运算的位结果相同。 $|Tmin_w| = |Tmax_w + 1|$ 时，在 $x = Tmin_w$ 时没有对应的正整数，负数表示范围比正数表示范围大1.即[1000...000]表示 $Tmin_w$ ,而[0000...000]则表示0.
从补码位级的值有两种技巧。

表达式-x 和 ~x +1得到的结果一样。所以在求取的值时0xfffffffa。~x+1 = 0x05 + 1 = 0x06 = -x。所以x的值是-0x06.
x的位表示位 $[x_{w-1},x_{w-2},...1,0...,0]$ ，这个值的非的表示可以写为 $[~x_{w-1},~x_{w-2},...1,0...,0]$ 。继续看上面的例子0xfffffffa位级表示是[1,...1010]，-x = [0...0110] = 6.所以x = -6.

无符号数的乘法

在 $0 \leq x ,y \leq 2^w-1$ 中， $x*_{w}^{u}y = (x \times y) mod 2^{w}$ 。直接进行位截断处理。

补码的乘法

在 $-2^{w-1} \leq x ,y \leq 2^{w-1}-1$ 中， $x \times y$ 的取值范围在 $[-2^{2w-2}+2^{w-1} ,2^{2w-2}]$ .如果想表示全需要2w-1位来表示。c语言中，直接采用截断位w位的方式来实现。 $x*_{w}^{t}y = U2T_{w}((x \times y) mod 2^w)$ 。所以无符号乘法和补码乘法具有相同的位级等价性。
如果[101] 和[011]相乘。

如果解释成无符号乘法等价于 $5 \times 3 = 15 ,15 mod 2^3 = 7$ .位级结果为[1111]丢弃最高位为[111]即为7.
如果解释成补码乘法等价于 $-3 \times 3 = -9 ,-9 mod 2^3 = -1$ . 位级别结果为[1111]丢弃最高位为[111]即为-1.
可能针对完整的最终位计算结果可能不同，但是截取后的结果是相同的。参考[100] * [111].

乘以常数

因为乘法需要的cpu周期往往是10个甚至更多。所以编译器优化的时候，会考虑用移位计算和加法运算替代乘法运算。

乘以2的幂的无符号乘法等价于左移一个数值。表达式 $0 \leq k \leq w$ ，x<<k 等价于 $x*_{w}^{u}y$ ，补码乘法和无符号乘法也一样。注意无论补码运算还是无符号运算，乘以2的幂都会导致溢出，但是不论移位还是乘法导致的溢出的结果都是一致的。
由于乘法比移位和加法的组合代价要大的多。所以很多编译器会尝试着用加法和移位的组合来代替乘法。比如x*14 可以用(x<<3) + (x<<2) + (x<<1)这样的组合来替代乘法。甚至可以用(x<<4) - (x<<1)来替换，这样只需要2个移位和1个减法就可以了。

除以2的幂

在大多数机器中整数除法比整数乘法更慢，往往需要30甚至以上的时钟周期。除以2的幂，也可以用右移来实现。无符号和补码分别使用逻辑右移和算术右移来达到目的。
整数除法总是舍入到0，对于x>=0,采用向下舍入的方式，对于x<0采用向上舍入的方式。即总是向0舍入。

除以2的幂的无符号除法。采用逻辑右移的方式。移位总是舍入到0.
除以2的幂的补码除法，采用算术右移的方式。当x<0的时候要先加上一个“偏置量”1<<k -1在>>k的形式来保证向0舍入。

浮点数

二进制小数

$b_{w}b_{w-1}...b_1b_0.b_{-1}b_{-2}...b_{-n}$ 的表示法可以表示二进制小数。b = $\sum_{i=-n}^{m}b_i2^{i}$ ，十进制无法能精确表示1/3.同样有限位数的二进制小数也无法精确表示0.1,0.2之类，只能近似的表示。

IEEE浮点数

IEEE浮点数标准用 $V =(-1)^s \times M \times 2^E$ ,

s为符号位（sign），负数s = 1，正数s = 0
M为二进制小数（significand），可以表示 $2- \varepsilon$ ,也可以是 $1- \varepsilon$ ,后面会讲到前者是规范模式下，后者是非规范模式下表示趋近0的小数。
E位阶码（exponent），加权作用。偏置量 bias = $2^{k-1}-1$ .规范化下，阶码E = e- bias.其中e 为无符号整数 $e_{k-1}e_{k-2}...e{1}$
最常见的浮点类型，单精度浮点数和双精度浮点数，就单精度（c语言中float）s的位数为1，exp的位数为8位，frac位23位。在双精度浮点数（c语言的double）中s的位数为1，exp位数为11，frac位数为52位。根据exp的值的不同，可以分为3种情况。
1.规范化表示，当exp的位模式既不是全0，也不是全1。阶码的字段被解释成偏置（biased）的形式表示的有符号整数。阶码E = e - bias。其中e为无符号整数，其位表示为 $e_{k-1}e_{k-2}...e_0$ ，bias为 $2^{k-1} -1$ 。在float类型中，规范化下 $e\in[1,254],bias = 127 可以推导出E\in[-126,127]$ ，同理在double类型下 $E \in [-1022,1023]$
小数字段frac被描述成f, $0\leq f < 1$ ,其二进制表示为 $0.f_{n-1}...f_1f_0$ ,尾数M定义为1+f。这个是以隐含1开头的表示方法，通过这种方法我们可以额外的获得1位精度。
2.非规格化的表示，当exp的位全部为0时，阶码的字段被解释成E= 1- bias.尾数M = f.小数的部分不包含1开头的小数。所以可以表示+0.0和-0.0，exp位全部为0，以及frac的位全部为0，符号位s为0时表示+0.0，符号位1时表示-0.0。之所以用1-bias 而不是用0-bias的原因是规范化下exp段最小值也是1-bias，而frac被解释成不带1的小数。所以用1-bias可以平滑过渡小数的表示。在float类型中，E = -126。同理在double类型中E = -1022.
非规格化的数表示那些非常接近0的数，提供一种属性称为“逐渐溢出”，分布的数值均匀的分布地接近0.0.
3.特殊值，当exp的位全部为1时，如果frac的位全部为0，那么被解释成 $\infty$ ,符号位s=0时，解释成 $+\infty$ ，符号位s=1时，解释成 $-\infty$ ，比如两个很大的数相乘或者除以0，无穷表示溢出的结果。当frac的位不全为0时，表示NaN，比如 $\sqrt{-1}$ ，或者 $\infty - \infty$ 时。

//输出的结果符合数学定义
unsigned int u1 = 0x7F800000;
unsigned int u2 = 0x7F800000;
float p1 = *(float*)(&u1); //p1表示+无穷
float p2 = *(float*)(&u2);//p2表示-无穷
printf("%f\n",p1+p2); //输出nan
printf("%f\n",p1+p1); //输出inf +无穷
printf("%f\n",p2+p2); //输出-inf -无穷
printf("%f\n",p1+0.5f);//输出inf +无穷
printf("%f\n",p2+0.5f);//输出-inf -无穷

unsigned int maxu1 = 0x7F7FFFFF;
float maxf1  = *(float*)(&maxu1 );
float maxf2 = maxf1 + 1024.0f; //有符号整数溢出，由于精度问题会舍去1024。
unsigned maxe = 0x7F000000;//指数位相同，尾数M=1.0。
float maxf3 = maxf1 + maxe; //输出无穷 上溢
printf("f max=%f,max2=%f,maxf3=%f\n",maxf1,maxf2,maxf3); //输出f max=340282346638528859811704183484516925440.000000,max2=340282346638528859811704183484516925440.000000
printf("hex max=%x,max2=%x\n",*(unsigned*)(&maxf1),*(unsigned*)(&maxf2));//输出hex max=7f7fffff,max2=7f7fffff 加法会溢出掉最小的数字不会溢出到无穷大。
printf("f max=%f",maxf1*1.1f); //输出inf.乘法会溢出到无穷大

例子中和最大浮点数加上1024，由于浮点加法的运算法则的关系，先保证指数位一致，来缩放尾数，在由于精度只有23位，故丢去了1024.

舍入

浮点运算的结果，针对中间值的情况采用偶数舍入的方式。举个例子要求舍入到二进制小数点后1位。
Round（0.0011） = 0.0
Round（0.0101） = 0.1
Round（0.1100） = 1.0
Round（0.0100）= 0.0

浮点数的运算

浮点数的加法，只具有交换性，不具备结合性。比如(3.14+1e10)-1e10，结果为0，3.14+(1e10-1e10)结果为3.14.前者3.14+1e10,由于浮点加法特性，3.14被舍入了。因为浮点加法不具备结合性。
浮点数的乘法，乘法可能会溢出到无穷，也不具备结合性。举个反例(1e201e20)1e-20，1e201e20溢出到无穷，所以结果是无穷，而1e20(1e20*1e-20)结果为1e20.

c语言的浮点数

c语言没有强制要求使用IEEE浮点数，所以没有标准的方法获取+0，-0，+∞，-∞，NaN之类的特殊值，GNU编译器GCC通过包含头文件比如#include<math.h>来获取定义的一些特殊值的常数，INFINITY表示+∞，NAN表示NaN。

浮点数的比较，当出现==来比较两个浮点数是否相等时，对应的是数学意义上的相等。

    unsigned int mm1 = 0x7FF00000;
    unsigned int mm2 = 0xFFF00000;
    unsigned int zz1 = 0x00000000;
    unsigned int zz2 = 0x80000000;
    unsigned int nn1 = 0x7FF00000;
    unsigned int nn2 = 0xFFF00000;
    if(*(float*)(&mm1) == *(float*)(&mm2))
        printf("正无穷==负无穷\n");
    else
        printf("正无穷!=负无穷\n");

    if(*(float*)(&mm1) == *(float*)(&mm1))
        printf("正无穷==正无穷\n");
    else
        printf("正无穷!=正无穷\n");
            
    if(*(float*)(&zz1) == *(float*)(&zz2))
        printf("正0==负0\n");
    else
        printf("正0!=负0\n");
            
    if(*(float*)(&nn1) == *(float*)(&nn2))
        printf("NaN1==NaN2\n");
    else
        printf("NaN1!=NaN2\n");

    if(*(float*)(&nn1) == *(float*)(&nn1))
        printf("NaN1==NaN1\n");
    else
        printf("NaN1!=NaN1\n");

输出结果:
正无穷!=负无穷
正无穷!=正无穷
正0==负0
NaN1!=NaN2
NaN1!=NaN1
可以得出结论，无穷/NaN不等于任何值，+0等于-0。

c语言数据类型转换
当从int转换成float时，数字不会溢出，可能会被舍入。
当从int/float转换成double时，因为double有更大精度和范围，所以能准确保留精度。
当从double转换成float时，值可能溢出到 $\infty$ ，也可能被舍入。因为float表示范围更小，且有效位数更小。
当从float/double 转换成int时，值会向0舍入。值也可能会溢出。c语言标准没有指出这种情况的固定结果，但是intel兼容的微处理器制定位模式为[100..000]字长为w时的 $Tmin_w$ 。即不能为浮点数产生一个合理的近似的整数值。因此表达式(int)1e10会得到-21483648。从正值变成一个负值。