信息的表示和处理

发表于 | 分类于 | |

三种最重要的数字表示：

  1. 无符号（unsigned）编码基于传统的二进制表示法，表示大于或者等于0的数字。

  2. 补码（two’s-complement）编码是表示有符号整数的最常见的方式，有符号整数就是可以为正或者为负的数字。

  3. 浮点数（floating-point）编码是表示实数的科学记数法的以二为基数的版本。

计算机的表示法是用有限数量的位来对一个数字编码，因此，当结果太大以致不能表示时，某些运算就会溢出（overflow）。

在C语言中，以0x或者0X开头的数字常量被认为是十六进制的值。

十进制和十六进制表示之间的转换需要使用乘法或者除法来处理一般情况。将一个十进制数x转换为十六进制，可以反复地用16除x，得到一个商q和一个余数r，也就是x=qx16+r。然后，我们用十六进制数字表示的r作为最低位数字，并且通过对q反复进行这个过程得到剩下的数字。

反过来，将一个十六进制数字转换为十进制数字，我们用相应的16的幂乘以每个十六进制数字。

d2h.pl
1
2
3
4
5
6
#!/usr/bin/env perl
#Convert list of decimal numbers into hex

for($i = 0; $i < @ARGV; $i++){
	printf("%d\t=0x%x\n", $ARGV[$i], $ARGV[$i]);
}
h2d.pl
1
2
3
4
5
6
7
#!/usr/bin/env perl
# Convert list of hex numbers into decimal

for($i = 0; $i < @ARGV; $i++){
	$val = hex($ARGV[$i]);
	printf("0x%x=%d\n", $val. $val);
}

小端法（little endian）和大端法（big endian）

某些机器选择在存储器中按照从最低有效字节到最高有效字节的顺序存储对象，而另一些机器则按照从最高有效字节到最低有效字节的顺序存储。前一种规则——最低有效字节在最前面的方式，称为小端法。后一种规则——最高有效字节在最前面的方式，称为大端法。

C语言中的运算符sizeof来确定对象使用的字节数。

C语言中字符串被编码为一个以null（其值为0）自负结尾的字符数组。

BIT MANIPULATION

  1. AND
  2. OR
  3. NOT
  4. EXCLUSIVE-OR

对于任一位向量a，有a^a = 0 应用这一属性，考虑下面的程序：

inplace_swap.c
1
2
3
4
5
void inplace_swap(int *x, int *y){
	*y = *x ^ *y;
	*x = *x ^ *y;
	*y = *x ^ *y;
}

掩码

掩码是一个位模式，表示从一个字中选出的位的集合。

例子：掩码0xFF表示一个字的低位字节。位级运算x&0xFF生成一个由x的最低有效字节组成的值，而其他的字节就被置为0。

移位运算

一般而言，机器支持两种形式的右移：逻辑右移和算术右移。

逻辑右移在左端补k个0。算术右移是在左端补k个最高有效位的值。
C语言比标准并没有明确定义应该使用哪种类型的右移。对于无符号数据，右移必须是逻辑的。而对于有符号数据，算术或者逻辑右移都可以。实际上，几乎所有的编译器或者机器组合都对有符号数据使用算术右移。

另一方面，Java对于如何进行右移有明确的定义。表达式x>>k会将算术右移k个位置，而x>>>k会对x做逻辑右移。

Notice：加减法的优先级比移位运算要高。

整数表示

根据字节分配，不同的大小所能表示的值的范围是不同的，唯一一个与机器相关的取值范围是大小指示符long的。大多数64位机器使用8个字节表示，比32位机器上使用的4个字节表示的取值范围大很多。

无符号数的编码

无符号的二进制表示一个很重要的属性，就是每个介于0～2^w-1之间的数都是唯一一个w位的值编码。这个属性用数学语言来描述就是函数B2Uw（Binary to Unsigned）是一个双射——对于每一个长度为w的位向量，都有一个唯一的值与之对应；反过来，在0～2^w-1之间的每个整数都有一个唯一的长度位w的位向量二进制表示与之对应。

补码编码

最常见的有符号数的计算机表示方式就是补码（two’s-complement）形式。在这个定义中，将字的最高有效位解释位负权（negative weight）。我们用函数B2Tw（Binary to Two’s-complement的缩写，长度为w）来表示：
negative最高位＊2^(w-1) + 余下位的和
B2Tw:{0:1}^w -> {-2^(w-1),…, 2^(w-1)-1}
|TMin| = |TMax| + 1

C库中的文件<limits.h>定义了一组常量，来限定编译器运行的这台机器的不同整型数据类型的取值范围。比如，它定义了常量INT_MAX、INT_MIN和UINT_MAX，他们描述了有符号和无符号数的范围。
ISO C99标准在文件stdint.h中引入了另一类整数类型。这个文件定义了一组数据类型，它们的声明形如intN_t和uintN_t，指定的是N位有符号和无符号整数。

关于整数数据类型的取值范围和表示，Java标准是非常明确的。它要求采用补码表示。在Java中，单字节数据类型成为byte，而不是char，而且没有long long数据类型。

有符号数的其他表示方法

  • 反码（Ones’ complement）除了最高有效位的权是-(2^(w-1)-1)而不是-2^(w-1)，它和补码是一样的。
  • 原码（Sign-Magnitude）最高有效位是富豪为，用来确定剩下的位应该取负权还是正权。

这两种表示方法都有一个奇怪的属性，那就是对于数字0有两种不同的编码方式。这两表示方法，把［00…0］都解释位+0。而值-0在原码中表示为[10…0]，在反码中表示为[11…1]。

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

T2Uw(x) = x + 2^w if x < 0 else x

U2Tw(u) = u if u<2^(w-1) else u-2^w

strlonger function
1
2
3
int strlonger(char *s, char *t) {
     return strlen(s) - strlen(t) > 0;
}

由于strlen被定义为产生一个无符号的结果，差和比较都采用无符号运算来计算。当s比t短的时候，差strlen(s)-strlen(t)会为负，但是变成了一个很大的无符号数，且大于0。

相关的问题：

函数getpeername的安全漏洞。

整数运算

无符号加法

无符号运算可以被视为一种模运算形式。无符号加法等价于计算和模上2^w。

算术运算溢出，是指完整的整数结果不能放到数据类型的字长限制中去。

当执行C程序时，不会将溢出作为错误而发信号。不过有的时候，我们可能希望判定是否发生了溢出。比如，假设计算s=x+y，并且我们想要判定s是否等于x＋y。我们声称当且仅当s<x（或者等价地s<y）时，发生了溢出。要明白这一点，请注意x+y>=x，因此如果s没有溢出，我们能够肯定s>=x。另一方面，如果s确实溢出了，我们就有s=x+y-2^w。假设y<2^w，我们就有y-2^w<0，因此s = x + (y-w^2) < x。

Q:写出一个具有如下原型的函数：
/ Determine whether arguments can be added without overflow /
int uadd_ok(unsigned x, unsigned y);

如果参数x和y相加不会产生溢出，这个函数会返回1。

uadd_ok function
1
2
3
4
5
6
int uadd_ok(unsigned x, unsigned y)
{
     unsigned sum = x + y;
     return sum >=x;
}
​`

补码加法

  • 我们将两个负数x和y相加，得到一个非负的结果（x+y=x+y-2^w）。这种情况称为负溢出（negative overflow）。
  • 我们将两个正数x和y相加，得到一个负数的结果（x+y=x+y+2^w）。我种情况称为正溢出（positive overflow）。

Q:写出一个具有如下原型的函数：
/ Determine whether arguments can be added without overflow /
int uadd_ok(int x, int y);
如果参数x和y相加不会产生溢出，这个函数会返回1。

​

uadd_ok function
1
2
3
4
5
6
7
int uadd_ok(int x, int y)
{
     int sum = x + y;
     int neg_over = x < 0 && y < 0 && sum >=0;
     int pos_over = x > 0 && y > 0 && sum < 0;
     return !neg_over && !pos_over;
}

补码的非（negation operation）

在C语言中，我们可以确定，对于任意整数值x，计算表达式-x和~x+1得到的结果完全一样。

以下内容未完成……
无符号乘法
补码乘法
乘以常数
除以2的幂

浮点数

101.11(binary) = 1x2^2+0x2^1+1x2^0+1x2^(-1)+1x2^(-2) = 23/4

IEEE（Eye triple Eee）浮点标准用V = (-1)^s x M x 2^E的形式来表示一个数：

  • 符号（sign）s决定这个数时负数（s=1）还是正数（s=0），而对于数值0的符号位解释作为特殊情况处理。
  • 尾数（significant）M是一个二进制小数，它的范围是1～2-e，或者是0～1-e。
  • 阶码（exponent) E的作用是对浮点数加权，这个权重时2的E次幂（可能是负数）。

将浮点数的位表示划分为三个字段，分别对这些值进行编码：

  • 一个单独的符号位s直接编码符号s
  • k位的阶码字段exp编码阶码E
  • n位小数字段frac编码尾数M，但是编码出来的值也依赖于阶码字段的值是否等于0。
  1. 在单精度浮点格式中，s、exp和frac字段分别为1位、k＝8位和n＝23位，得到一个32位的表示。
  2. 在双精度浮点格式中，s、exp和frac字段分别为1位、k＝11位和n＝52位，得到一个64位的表示。

给定了位表示，根据exp的值，被编码的值可以分为三种不同的情况。

  • 情况1:规格化的值
    这是最普遍的情况。当exp的位模式既不全位0也不全为1时，都属于这类情况。在这种情况中，阶码字段被解释为以偏值（biased）形式表示的有符号整数。也就是说，阶码的值时E=e-Bias，其中e是无符号数，而Bias是一个等于2^(k-1)-1的偏置值。由此产生指数的取值范围，对于单精度时-126~+127，而对于双精度是-1022~+1023。

对小数字段frac的解释为描述小数值f，其中0<=f<1，也就是二进制小数点在最高有效位的左边。尾数定义为M＝1+f。有时，这种方式也叫做隐含的以1开头的（implied leading 1）表示，因为我们可以把M看成一个二进制表达式位1.fn-1…f0的数字。既然我们总是能够调整阶码E ,使得尾数M在范围1<=M<2之中，那么这种表示方法是一种轻松获得一个额外精度位的技巧。由于第一位总是等于1，因此我们就不需要显示地表示它。

  • 情况2：非规格化的值
    当阶码域全0时，所表示的数就是非规格化形式。在这种情况下，阶码值时E＝1-Bias，而尾数的值时M=f,也就是小数字段的值，不包含隐含的开头1.
    非规格化数有两个用途，首先，它们提供了一种表示数值0的方法，因为使用规格化数，我们必须总是使M>=1，因此我们就不能表示0。实际上，+0.0的浮点表示的位模式为全0:符号位是0，阶码字段全为0，而小数域也全为0，这就得到M=f=0。
    非规格数的另外一个功能时表示那些非常接近于0.0的数。它们提供了一种属性，称为逐渐溢出（gradual underflow），其中，可能的数值分布均匀地接近于0.0。

  • 情况3：特数值
    最后一类数值是当指阶码全为1的时候出现的。当小数域全为0的时，得到的值表示无穷。当我们把两个非常大的数相乘，或者除以0时，无穷能够表示溢出的结果。当小数域位非零时，结果值被称为“NaN”，就是“不是一个数”（Not a Number）的缩写。一些运算的结果不能是实数或无穷，就会返回这样的NaN值，比如当计算sqrt(-1)时。

References:

Computer Systems: A Programmer’s Perspective 2E

More than your eyes can see