《csapp》实践:信息的表示和处理

阅读深入理解计算机系统,书中的很多实践的练习值得尝试。

show bytes

1
2
3
4
void show_bytes(byte_pointer start, size_t len)
//这里的len表示从start开始
//包括start,例如ab ed 这样,每2个数字为一个单位
//总共有几个单位?

show_bytes的使用,具体能够打印类型为short、long和double的c语言对象的字节表示:
具体实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
/* $begin show-bytes */
#include <stdio.h>
/* $end show-bytes */
#include <stdlib.h>
#include <string.h>
#include <iostream>
/* $begin show-bytes */
using namespace std;
typedef unsigned char *byte_pointer;
//unsigned char * 显示一位
void show_bytes(byte_pointer start, size_t len) {
size_t i;
//int k=0;
for (i = 0; i < len; i++)
printf(" %.2x", start[i]); //line:data:show_bytes_printf
//buf[k++]=start[i];
printf("\n");
}
void show_int(int x) {
show_bytes((byte_pointer) &x, sizeof(int)); //line:data:show_bytes_amp1
}
void show_float(float x) {
show_bytes((byte_pointer) &x, sizeof(float)); //line:data:show_bytes_amp2
}
void show_pointer(void *x) {
show_bytes((byte_pointer) &x, sizeof(void *)); //line:data:show_bytes_amp3
}
void show_short(short x){
show_bytes((byte_pointer) &x, sizeof(short));
}
void show_long(long x){
show_bytes((byte_pointer) &x, sizeof(long));
}
void show_double(double x){
show_bytes((byte_pointer) &x, sizeof(double));
}
/* $end show-bytes */
/* $begin test-show-bytes */
void test_show_bytes(int val) {
int ival = val;
float fval = (float) ival;
int *pval = &ival;
show_int(ival);
show_float(fval);
show_pointer(pval);
}
/* $end test-show-bytes */
void simple_show_a() {
/* $begin simple-show-a */
int val = 0x87654321;
byte_pointer valp = (byte_pointer) &val;
show_bytes(valp, 1); /* A. */
show_bytes(valp, 2); /* B. */
show_bytes(valp, 3); /* C. */
show_bytes(valp, 4);
/* $end simple-show-a */
}
void simple_show_b() {
/* $begin simple-show-b */
int val = 0x12345678;
byte_pointer valp = (byte_pointer) &val;
show_bytes(valp, 1); /* A. */
show_bytes(valp, 2); /* B. */
show_bytes(valp, 3); /* C. */
/* $end simple-show-b */
}
void float_eg() {
int x = 3490593;
float f = (float) x;
printf("For x = %d\n", x);
show_int(x);
show_float(f);
x = 3510593;
f = (float) x;
printf("For x = %d\n", x);
show_int(x);
show_float(f);
}
void string_ueg() {
/* $begin show-ustring */
const char *s = "ABCDEF";
show_bytes((byte_pointer) s, strlen(s));
/* $end show-ustring */
}
void string_leg() {
/* $begin show-lstring */
const char *s = "abcdef";
show_bytes((byte_pointer) s, strlen(s));
/* $end show-lstring */
}
void show_twocomp()
{
/* $begin show-twocomp */
short x = 12345;
short mx = -x;
show_bytes((byte_pointer) &x, sizeof(short));
show_bytes((byte_pointer) &mx, sizeof(short));
/* $end show-twocomp */
}
//check is_litter_endian
bool is_litter_endian()
{
int a = 0x123456;
if( *((char*)&a) == 0x56)
return 1;
else
return 0;
}
int main(int argc, char *argv[])
{
int val = 12345;
if (argc > 1) {
if (argc > 1) {
val = strtol(argv[1], NULL, 0);
}
printf("calling test_show_bytes\n");
test_show_bytes(val);
}
else {
printf("calling show_twocomp\n");
show_twocomp();
printf("Calling simple_show_a\n");
simple_show_a();
printf("Calling simple_show_b\n");
simple_show_b();
printf("Calling float_eg\n");
float_eg();
printf("Calling string_ueg\n");
string_ueg();
printf("Calling string_leg\n");
string_leg();
//exercise 2.59
if(is_litter_endian())
cout<<"litter endian"<<endl;
else
cout<<"big endian"<<endl;
}
return 0;
}

结果见图:

02

可以发现,我的电脑是小端法机器,浮点数的编码方法,和二进制的编码方法不太一样,浮点数的编码方法,我在
浮点数编码方法
最后一个例子有详细说明。

其中值得一提的是,取最低有效字节的方法:

1
2
3
4
x & 0xFF //取出x的最低有效字节
y & ~0xFF //取出y的最低有效字节
((x & 0xff) | (y & ~0xff)) //能够实现x的最低有效字节和
//y除了最低有效字节外的其他字节合并

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
//注意:不要打0x作为输入
int main()
{
int x,y;
int res;
printf("Please int x(H) and y(H): ");
scanf("%x%x",&x,&y);
res = ((x & 0x000000ff) | (y & 0xffffff00));
printf("The result is %.8x(H)\n",res);
}

类似的方法,常常用于处理某一个字节替换问题:

结论见图:

01

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <iostream>
using namespace std;
unsigned replace_byte(unsigned x, unsigned char b, int i)
{
return (x & ~(0xff<<(i<<3))) | (b<<(i<<3));
}
int main()
{
printf("0x%x\n",replace_byte(0x12345678,0xab,2));
printf("0x%x\n",replace_byte(0x12345678,0xab,0));
}
`

位级整数编码原则

算术右移和逻辑右移的关系

算术右移和逻辑右移是不一样的
算术右移需要考虑符号位,右移一位,若符号位为1,在左边补1
逻辑右移,补0就可以

这里以-1为例,-1算术右移一位,所产生的二进制码代表的数值不变;而逻辑右移则会使最高位为0,变成(1<<63)-1,最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <iostream>
using namespace std;
int judge_if_all_1(int x)
{
return !(~x);
}
int judge_if_all_0(int x)
{
return !x;
}
int judge_low_is_0(int x)
{
//最低有效字节:x & 0xff
return !(x & 0xff);
}
int judge_low_is_1(int x)
{
return (x & 0xff);
}
int judge_high_is_0(int x)
{
//除最高字节以外的位数
//howmanybit=(sizeof(int)-1)<<3
// a<<3表示a*8,因为一位有8个比特
//右移howmanybit位
return !( (x>>((sizeof(x)-1)<<3)) );
}
int main()
{
int a;
scanf("%x",&a);
cout<<judge_low_is_0(a)<<endl;
cout<<judge_low_is_1(a)<<endl;
cout<<judge_high_is_0(a)<<endl;
cout<<judge_if_all_0(a)<<endl;
cout<<judge_if_all_1(a)<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <iostream>
using namespace std;
//int_shifts_are_arithmetic()
//对int类型数使用算术右移返回1,否则返回0;
//显然,只需考虑负数即可(非负数算术右移与逻辑右移相同)。
//显这里以-这里以-这里以-这里以-1为例,
//-1算术右移一位,所产生的二进制码代表的数值不变;
//-而逻辑右移则会使最高位为0,变成(1<<31)-1,最大值。
int int_shifts_are_arithmetic()
{
printf("%x %x\n", ((-1)>>1),-1);
return ((-1)>>1)==-1;
}
int main()
{
cout<<int_shifts_are_arithmetic()<<endl;
return 0;
}

算术右移有一个特点,移几位,补几个最高位
举一个例子
$[x_{w-1},x_{w-1}…x_{w-1},x_{w-2}…x_{k}]$

算术右移和逻辑右移相互表示

这里先提一点:算术右移和逻辑右移,其中涉及到有符号数和无符号数的相互转换,这个问题比较重要,公式如下:

一个无符号数,转换成对应的有符号数,依据是:补码原则

其中$TMax_w$表示符号类型如$int$最大的位数

基于以上公式,我们发现从$int$类型向$unsigned$类型转换的时候,只有x为负数,逻辑右移和算术右移才能够体现出区别,我们这里仅研究$x<0$的情况

1
2
sra()表示用逻辑右移完成算术右移
srl()表示用算术右移完成逻辑右移

原理表示如下(仅仅研究$x<0$情况):
03

04

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int sra(int x,int k)
{
//Perform shift logically
int xsrl = (unsigned)x >> k; //转换成为无符号数
int w = (sizeof(int))<<3;
returnx xsrl |= (-1 << (w-k));
}
unsigned srl(unsigned x, int k)
{
//Perform shift arithmetically
unsigned xsra = (int) x >> k;
int w = (sizeof(int)) << 3;
return xsra &= ~(-1 << (w-k));
}

判断奇数位是否为1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <iostream>
bool any_odd_one(unsigned x)
{
//将所有的奇数位全部置为0,偶数位不变
//考虑&...01010101
//&0x55555555(32bits)
//若奇数位有1,则提取奇数位,结果不为0
return 0!=(x&0x55555555);
}
int main()
{
printf("%d\n",any_odd_one(0x5) );
printf("%d\n",any_odd_one(0x25) );
printf("%d\n",any_odd_one(0x7) );
return 0;
}

二分法位运算:有多少个位包含1

注意:^异或运算,相当于无进位的加法,可以消除位中的1

05

有两种方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#include <iostream>
using namespace std;
//不用位运算的方法
int even_ones_without_bit(unsigned x)
{
int result = 0;
for(int i=0;i<(sizeof(int)<<3);i++)
{
int y = x>>i;
y=y&1;
if(y)
result++;
}
if(result%2)
return 1;
else
return 0;
}
int odd_ones(unsigned x)
{
//用异或运算消除偶数
x ^= (x>>16);
x ^= (x>>8);
x ^= (x>>4);
x ^= (x>>2);
x ^= (x>>1);
return (x&1);
}
int main()
{
int x;
scanf("%x",&x);
int res=odd_ones(x);
printf("%d\n",res);
}

二分法运算:只保留最高位的1

06

函数功能如下:

1
0xFF00-->0x8000 0x6600-->0x4000

实现方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
int leftmost_one(unsigned x)
{
x |= (x>>1);
x |= (x>>2);
x |= (x>>4);
x |= (x>>8);
x |= (x>>16);
x &= ~(x>>1);
return x;
}
int main()
{
int x;
scanf("%x",&x);
int res=leftmost_one(x);
printf("%x\n",res);
}

移位运算需要注意的

可以知道:移位运算,移位的量,区间是$(0,w-1)$
通过移位运算,使得在32位的机器上可以运行

这里说一下移位运算的溢出:
注意第一位是符号位

1
2
3
4
5
6
0000 -- 0
0001 -- 1
0010 -- 2
...
0111 -- 7
1000 -- -8

以32位机器举例,int的最大值位$2^{32-1}=2147483648$
int型,若为正数,可以表示的最大的数为

1
2
3
4
5
0111 1111 1111 1111 1111 1111 1111 1111
//最高位是符号位,为0,值为2147483647
//加上1之后
1000 0000 0000 0000 0000 0000 0000 0000
//值为负数,-2147483648

判断一个机器是否为32位,只要用上述方法可以判断。
具体实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
bool int_size_is_32()
{
int set_msb = ~(1<<31);
return (set_msb+1<0);
}
int main()
{
bool res = int_size_is_32();
printf("%d\n",res);
}

位级运算完成置位

lower_one_mask

使用位级运算完成置位的过程,通常需要将二进制转换成如下形式:

1
2
3
4
5
6
00000 111111
//即前几个数都为0,后几个数都为1的形式
//lower_one_mask函数的实现
//0xFFFFFFFF>>(32-n)
//00...011...1形式,最后就有n位为1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
int lower_one_mask(int n)
{
unsigned mark = 0xffffffff;
mark = mark >> (32-n);
return mark;
}
int main()
{
int n;
scanf("%d",&n);
int res = lower_one_mask(n);
printf("%x",res);
}

旋转:rotate_left

1
2
3
//取最高m位和最低n位的方法:
x>>(32-m)
x<<(32-n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
unsigned rotate_left(unsigned x, int n)
{
if(n==0)
return x;
else
{
unsigned low = x<<n;
unsigned high = x>>(32-n);
return low | high;
}
}
int main()
{
int x,n;
scanf("%x%d",&x,&n);
int res=rotate_left(x,n);
printf("%x\n",res);
}

补码运算的原理

1、补码中取反,反码的求法。

1
2
3
4
反码,以下讨论不包括符号位
010110的反码
111111-010110 = 101001
这里不讨论符号位

2、补码原理:

假设计算机字长为n,源码、反码和补码的关系如下:
07

原码:

1
2
3
4
5
6
[+1]_源 = 0000 0001
[-1]_源 = 1000 0001
其中第一位为符号位
取值范围
[1111 1111, 01111 1111]
-->[-127,127]

从公式上看,当$x>0$时,很显然x的源码就是x自身
$x<0$时候,除去最高位外,剩下的位数的值等于$|x|=-x$,
再加上最高位的1,即加上$2^{n-1}$,最后的值为$2^{n-1}-x$

反码:

1
2
3
4
5
6
正数反码不变
负数反码,符号位不变,各位取反
[+1]=[0000 0001]_源=[0000 0001]_反
[-1]=[1000 0001]_源=[1111 1110]_反
可以用[1000 0000]表示-128

负数的反码,除了符号位,各位取反,其实是

1
2
仅看数值位(n-1)
11...1 - xxxxx

数值位取反即为$2^{(n-1)}-1-(-x)=2^{(n-1)}-1+x$
解释:

1
0xffffffff-(-x)

最高位,即符号位为$2^{n-1}$,数值位全部为1,表示为$2^{n-1}-1$
数值位取反$2^{n-1}-1-(-x)$

最后我们再加上符号位$2^{n-1}$
所以答案为$2^{n-1}+(2^{n-1}-1+x)=2^n+x-1$

补码:
为什么是取反码加一?
假设我们有正数 0000 0000 0000 1111,我们如何表示其相反数呢?一般我们的思路是,找一个数,跟它相加的结果等于0,但是我们发现,要找出一个与它相加后结果等于0的数还是要略加思考一下的(因为要计算进位),所以,为何不找出一个与它相加后结果是1111 1111 1111 1111的数,然后该数+1即是我们所要的答案啦。

A+(相加等于全部是11111的数)+1 = 0
所以A的相反数等于:求出与A相加全部是11…1的数,然后加1
于是就推出:
补码等于反码+1

08
缩进后再暴露最高位的方法,来看看补码是否等于原来的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
//一个数能够用二进制补码表示
//可以知道这个数为正数
int fits_bits(int x, int n)
{
//对最高位进行缩进表示
int bias = (sizeof(int) << 3)-n;
return ((x<<bias)>>bias)==x;
}
int main()
{
int x,n;
scanf("%d%d",&x,&n);
int res = fits_bits(x,n);
printf("%d\n",res);
}

xbyte

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
typedef unsigned packed_t;
int xbyte(packed_t word, int bytenum)
{
int move_to_high = (3-bytenum)<<3;
//将要处理的字节移动到首字节
unsigned mask = (0xff) << 24;
//第一个字节设置掩码
int res = (word << move_to_high) & mask;
res = res >> 24;
return res;
}
int main()
{
int hex,n;
scanf("%x%d",&hex,&n);
printf("%x\n",xbyte(hex,n));
return 0;
}

特别注意的地方:

1
2
3
4
5
6
7
8
if(maxbytes-sizeof(val)>=0)
{
//
}
条件是恒正的,因为结果是无符号数,无符号数大于0是肯定的
正确写法:
if(maxbytes>=sizeof(val))

位运算实现饱和加法

饱和加法,在正溢出的时候,返回$TMax$。

先来看正常情况下的加法

1
2
3
两个正数加法溢出
011...1 + 1 = 100...0
最后sum的符号位被置为1

所以最后的$TMax$会是一个绝对值比较大的负数

这里我们要返回$TMax$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>
#include <iostream>
using namespace std;
int saturating_add(int x, int y)
{
int mask = INT_MIN;
//INT_MIN所有位均为1,构成了掩码
int sum = x+y;
int w = sizeof(int)<<3;
//负溢出的时候,获取最小值
//负溢出的情况,原来x,y的第一位为1
//即有(x & mask) (y & mask)
//注意&&运算,() && (),
//注意&&运算,连接两个非0数,
//结果也只为0或者1
//(x & mask) && (y & mask) && !(sum & mask)
//在负溢出的时候为1,1<<(w-1)>>(w-1)
//会把所有的位置为1,因为有符号数要补上符号位
//最后 & INT_MIN,保证INT_MIN正确输出
int tmin = ( ((x&mask) && (y&mask) && !(sum&mask)) <<(w-1)>>(w-1) ) & INT_MIN;
//这一步,关键是如果前半部分的值为1,说明溢出,溢出返回的是INT_MIN
//不用if语句,我们要得到INT_MIN,需要INT_MIN & 11...1
//前半部分的值为1,要让所有的位值都是1,需要<<(w-1)>>(w-1)
//算术右移,前面是带上符号位的
int tmax = ( ((~x&mask) && (~y&mask) && (sum&mask)) <<(w-1)>>(w-1) ) & INT_MAX;
return (sum& ~(!(tmin | tmax))) | tmin | tmax;
//这里重点说明一下没有溢出的情况:
//[tmin,tmax) 其中tmin=11...1 tmax=011...1
//tmin|tmax = 11...1,这样的目的是把符号位的1也参与进运算中
//--> !(tmin | tmax)=00...0 --> ~(!(tmin|tmax))=11...1
//sum & res = sum,符号位也原封不动地包含下来
}
void show_saturating_add(int x,int y)
{
printf("satuarating_add(0x%08x,0x%08x)=0x%08x-->%d\n",x,y,saturating_add(x,y),saturating_add(x,y));
printf("%d+%d=%d\n",x,y,x+y);
printf("\n");
}
int main()
{
int x,y;
scanf("%x%x",&x,&y);
show_saturating_add(x,y);
}

同样,怎么判断减法是否溢出呢?
减法的溢出会导致一个非常大的正数,用这样的思路来分析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#include <iostream>
using namespace std;
//判断x-y溢出,返回1
int tsub_ok(int x,int y)
{
return ( (y>0 && x-y>x) || (y<0 && x-y<x) );
}
void show_tsub_ovf(int x, int y)
{
printf("%d-%d=%d %s\n",x,y,x-y,tsub_ok(x,y)?"overflow":"not_overflow");
}
int main()
{
int x,y;
scanf("%x%x",&x,&y);
show_tsub_ovf(x,y);
}

理解定点数的乘法

对于位模式$x$,我们计算$B2U_w(x)-B2T_w(x)=x_{w-1}(2^{w-1}-(-2^{w-1}))=x_{w-1}2^w$
$B2U_w(T2B_w(x))=T2U_w(x)=x+x_{w-1}2^w$
$x’=x+x_{w-1}2^w$
$y’=y+y_{w-1}2^w$
$(x’\times y’)mod 2^w =$
$[(x+x_{w-1}2^w)\times (y+y_{w-1}2^w)]mod 2^w=[x \times y+(x_{w-1}y+y_{w-1}x)2^w+x_{w-1}y_{w-1}2^{2w}]mod 2^{w}$
$=(x \times y)mod2^w$

重点看一下定点数乘法的运算过程

原码乘法

原码乘法的原理可以用下图表示:

09

原码乘法的计算过程,如上面的公式表示的那样,$w$位的两个数相乘,最后得到的数是$2w$位。所以用“部分积寄存器”来表示积的高位,用“乘数寄存器”来表示低位。其中,乘数的位为0或者1,0表示不加任何数,1表示加上被乘数。乘数的位值,仅仅是一个标志,表示是否加上被乘数。被乘数保持不变。

具体的实现方法如下:

10
值得注意的是,原码乘法执行的是逻辑右移

11

12

补码乘法

补码乘法有两种:
第一是校正法,注意在末尾加上$[-x]_{complement}$

13

14

第二种方法是booth方法,booth方法,最后一步不移位,那怎么判断乘积是否结束了呢?
看看在乘数寄存器中,新更新的位数,是不是恰好为$w$位?

15

位运算与定点数乘法

从上面的分析可以看出,定点数乘法,$w$位的两个数相乘,我们可以得到$2w$位。
如果$x$和$y$都是无符号数,并且运行在数据类型是unsigned的$w$位机器上。乘积的低$w$位能够用表达式$x\times y$计算。我们需要一个具有下列原型的函数:

1
2
unsigned unsigned_high_prod(unsigned x,unsigned y);
//计算无符号变量x*y的高w位

1
2
int signed_high_prod(int x,int y)
//计算x和y采用补码形式的情况下,x*y的高w位

针对上面的公式,我们不妨把计算结果用$2w$来表示
$[(x+x_{w-1}2^w)\times (y+y_{w-1}2^w)]mod 2^w=[x \times y+(x_{w-1}y+y_{w-1}x)2^w+x_{w-1}y_{w-1}2^{2w}]mod 2^{w}$

将计算结果对$2^w$取余,比如64位的量,可以对$2^64$取mod,最后的结果是有64位:
位分别为0,1,2…63

我们要获得高$32$位,可以

1
2
3
4
unsigned unsigned_high_prod(unsigned x, unsigned y) {
int sig_x = x >> 31;
int sig_y = y >> 31;
int signed_prod = signed_high_prod(x, y);

上述运算实现了:
$[x \times y+(x_{w-1}y+y_{w-1}x)2^w]mod 2^{w}$

我们将上述值同时移位$w$,就可以实现
$[(x \times y) (>>w)+(x_{w-1}y+y_{w-1}x)]$

其中$x_{w-1}$就是$x$的符号位

1
2
int sig_x = x >> 31
//获取x_(w-1)的值

其中$x\times y$表示int类型的值,是有符号数。

实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#include <inttypes.h>
int signed_high_prod(int x,int y)
{
int64_t mul = (int64_t) x*y;
return mul >> 32;
}
unsigned unsigned_high_prod(unsigned x,unsigned y)
{
int sig_x = x >> 31;
int sig_y = y >> 31;
int signed_prod = signed_high_prod(x,y);
return signed_prod + sig_x * y + sig_y * x;
}
unsigned compared_high_prod(unsigned x,unsigned y)
{
uint64_t mul = (uint64_t) x*y;
return mul >> 32;
}
int main()
{
unsigned x = 0x12345678;
unsigned y = 0xffffffff;
int test = unsigned_high_prod(x,y);
int compared = compared_high_prod(x,y);
printf("Test: %8x\n",test);
printf("compared: %8x\n",compared);
}

本章中的其他一些问题(库函数)

calloc.c

1
void* calloc(size_t nmemb, size_t size);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
void* my_calloc(size_t nmemb,size_t size)
{
if(nmemb==0 || size==0)
return NULL;
size_t buf_size = nmemb * size;
if(nmemb == buf_size/size)
{
void* ptr = malloc(buf_size);
memset(ptr,0,buf_size);
return ptr;
}
return NULL;
}
int main()
{
void* p;
p = my_calloc(0x1234,1);
//一共有0x1234个元素,每个元素1字节
bool flag = (p!=NULL);
if(flag)
printf("Case 1 :Not Null \n");
else
printf("Case 1 :Null\n");
free(p);
p = my_calloc(SIZE_MAX,2);
flag = (p==NULL);
if(flag)
printf("Case 2 :NULL\n");
else
printf("Case 2 :Not Null\n");
}

使用移位运算完成倍乘

1
2
3
4
5
6
//注意乘数为负数的时候怎么表示?
int A(int x)
{
return x - (x << 3);
//表示-7x
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#include <assert.h>
#include <iostream>
using namespace std;
int A(int x)
{
return x + (x << 4);
}
int B(int x)
{
return x - (x << 3);
}
int C(int x)
{
return (x << 6) - (x << 2);
}
int D(int x)
{
return (x << 4) - (x << 7);
}
int main()
{
int x = 0x1;
printf("Case A: %d\n",A(x));
printf("Case B: %d\n",B(x));
printf("Case C: %d\n",C(x));
printf("Case D: %d\n",D(x));
}

移位运算与舍入问题

仅有乘法或除法

16

移位运算的舍入问题,遵循以下不等式:
$[x]+[x+\frac{1}{n}]+[x+\frac{2}{n}]+\cdots+[x+\frac{n-1}{n}]=[nx]$

观察上图:
从上表中可以看到,当右移8位的时候,得到-49,这与向零舍入的结果-48并不吻合。
右移总是向下舍入,而对于向零舍入的负数来说是向上舍入,因此为了保证结果吻合,需要进行一个偏置。

bias偏移规律如下:

17
18
19

1
2
3
if(A<0)
A+=(1<<k)-1;
A>>n;

实现方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
#include <assert.h>
#include <limits.h>
int divide_power2(int x, int k)
{
int is_neg = x & INT_MIN;
if(is_neg)
x += (1<<k)-1;
return x>>k;
}
int mul3div4(int x)
{
int mul3 = x+(x<<1);
return divide_power2(mul3,2);
}
int main()
{
int x;
scanf("%x",&x);
printf("%8x\n",divide_power2(x,2));
printf("%8x\n",x/4);
int y;
scanf("%x",&y);
printf("mul3div4: %x\n",mul3div4(y));
printf("check: %x\n",3*y/4);
return 0;
}

乘除法相结合

20
可以发现我们需要:1、最后$k$位置为0,得到$low$。2、将前面$w-k$位置为0,得到$high$

1
2
3
4
5
6
7
8
//例如:x*(6/8),8=2^3
int low = x & 0x7;
//仅仅保留最后3位,用掩码(111 & x)
int high = x & ~0x7
//掩码获得x的高位,将低3位置为0
//low high分别计算

具体实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
#include <limits.h>
int threefourths(int x)
{
int is_neg = x & INT_MIN;
int low = x & 0x3;
int high = x & ~0x3;
int highd4 = high >> 2;
int highd4m3 = highd4 + (highd4 << 1);
int lowm3 = low + (low << 1);
int bias = (1<<2) - 1;
if(is_neg)
lowm3 += bias;
int lowm3d4 = lowm3 >> 2;
return lowm3d4 + highd4m3;
}
int main()
{
int x;
scanf("%d",&x);
printf("Test: %d\n",threefourths(x));
printf("Real: %d\n",x*3/4);
}

位模式的表示方式

$1^{w-k}0^k$
$0^{w-k-j}1^k0^j$

这两种都可以用移位来表示

其中$0^{w-k-j}1^k0^j$
可以分成三步走:
第一步:获取$1^{w-k}0^k$,通过右移实现
第二步:获取$0^{w-k}1^k$,通过取反实现
第三部:再右移$j$位

实现方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include <iostream>
int A(int k)
{
return -1 << k;
//表示-1重复k次
}
int B(int k,int j)
{
return (~A(k)) << j;
}
int main()
{
int x;
scanf("%d",&x);
printf("%8x\n",A(x));
printf("0xFFFFFF00\n");
printf("%8x\n",B(16,8));
printf("0x00FFFF00\n");
}

移位运算时候常见的错误

1
2
3
4
5
int x = random();
int y = random();
unsigned ux = (unsigned) x;
unsigned uy = (unsigned) y;

补码的非位级表示:对于任意数值

1
-x == ~x+1

从数学上解释这一点:

$2^w-x=-x$
$-x$表示$x$的相反数

$2^w-x-1=-x-1$
$2^w-1-x$表示全1的位减去$x$,得到~x

1
-x=~x+1

成立

1
2
3
4
5
(x<y) == (-x>-y)
//wrong! x=INT_MIN
//此时-x = ~x + 1
//~x=011...1
//~x+1 = 100...0 仍然为INT_MIN
1
((x+y)<<4)+y-x == 17*y+15*x
1
2
3
~x+~y+1=(~x+1)+(~y+1)-1
=-x+-y-1
=-(x+y)-1
1
2
3
(ux-uy)==-(unsigned)(y-x)
--> -(ux-uy)==(unsigned)(y-x)
--> (uy-ux)==(unsigned)(y-x) 显然成立
1
2
3
4
(x>>2)<<2
--> x& ~(0x3)
--> x + -num(00/01/10/11)
--> (x>>2)<<2 <= x

特殊的二进制无穷串

一些数字的二进制表示是$0.yyy\cdots$,其中$y$是一个$k$位的序列。

1
2
3
4
n = 0.yyy...
n<<k = y.yyy...=Y+n
--> n<<k-n=Y
--> n = Y/(2^k-1)
1
2
3
4
5
6
7
应用:
a) 101
Y=5 k=3 n=5/7
b) 0110
Y=6 k=4 n=6/15=2/5
c) 010011
Y=19 k=6 n=19/63

用unsigned测试float型数据的大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
unsigned f2u(float x)
{
return *(unsigned*) &x;
}
int float_le(float x,float y)
{
unsigned ux = f2u(x);
unsigned uy = f2u(y);
unsigned sx = ux >> 31;
unsigned sy = uy >> 31;
return sx==sy ? (sx==0 ? ux<=uy : ux>=uy) : sx>sy;
}
int main()
{
int x,y;
scanf("%d%d",&x,&y);
int flag = float_le(x,y);
printf("%d\n",flag);
}

浮点数概论

21

为什么要引入$bias$?
因为就小数部分而言,比如$0.1010$,计算机是按照二进制编码来计算$1010=10$,无法表示$2^{-k}$,所以我们引入$bias$来表示。
因为没有负值的符号位啊!
$e_{k-1}e_{k-2}\cdots e_{0}$,要表示$(-1)00\cdots 0$,只要$0-2^{k-1}$,表示把符号位置为$-1$。
可是为什么bias取$2^{k-1}-1$而不是$2^{k-1}$
直观上可以这么理解,$00\cdots 0$表示0,而$11\cdots 1 \ 00\cdots0$表示无穷大。
所以要除掉那个无穷大的,即为$2^{k-1}-1$

几个问题:
1、32位ieee 754的阶码偏移量为何用127?而不是128
为了让表示的范围能够对称起来。

当阶码E为全0且尾数M也为全0时,表示的真值x为零,结合符号位S为0或1,有正零和负零之分。
当阶码E为全1且尾数M为全0时,表示的真值x为无穷大,结合符号位S为0或1,也有+∞和-∞之分。
这样在32位浮点数表示中,要除去E,用全0和全1(255)表示零和无穷大的特殊情况,指数的偏移值不选128(10000000),而是127(01111111)。
对于规格化浮点数,阶码E范围是1~254。

非规格化数$E=1-bias$
规格化数$E=e-bias$,其中$e=e_{k-1}e_{k-2}\cdots e_{0}$

对于规格化的值
当$exp$的位模式既不全为0,也不全为1,$E=e-bias$
$e=e_{k-1}e_{k-2}\cdots e_{0}$
$bias=2^{k-1}-1$
很显然$e_{min}=1$,则$E_{min}=1-2^{k-1}+1=2-2^{k-1}\geq 2-1=1$
同理$e_{max}=2^k-2$,(扣除全部为1的值),$E_{max}=2^k-2-2^{k-1}+1=2^{k-1}-1$

$127=2^{8-1}-1$,此时$k=8$
想一想,如果我们让偏移值为128,而不是127,会是什么样?
$E_{min}=1-2^7=-127$,所表示的值为$2^{-127}=5.877471754111438\times 10^{-39}$
$E_{max}=2^7-2=126$,所表示的值$2^126=8\times 10^{37.9297}$
不对称。

而相反,我们让偏移值为127,可以得到取值范围为:
$E_{min}=1-2^{7}+1=-126$,$2^{-126}=1.1754943508222875\times 10^{-38}$
$E_{max}=2^7-1=127$,$2^{127}=1.7 \times 10^{38.23080944932561}$

很显然,偏移值为127的时候上下对称。

非规格化数的平滑处理
为什么要将$E$定义为$1-bias$,这样的方法归功于平滑性的设计。
你肯定想问,1是哪里来的?

22

浮点数编码表示方法

注意《深入理解计算机系统》这本书中,尾数的表示方法,和现行的中文教材不太一样。
在《深入理解计算机系统》这本书中提到:尾数的范围是$[1,2-\epsilon)$
而在我们现行的教材上,尾数的范围是$[0,1-\epsilon)$

23

浮点数编码能够表示的范围

24

注意在尾数部分,小数点是跟在数符后面的。

25

26

浮点数的规格化

浮点数的规格化表示,要求小数点后的第一位必须是$1$(基数$r=2$),其他情况如果$r=4$,则小数点后最高2位不全为0。

27

举例1

28

29
特别注意,在这个例子中,阶码是正数,它的补码保持不变,尾数的补码要取反加一

30

在《深入理解计算机系统》这本书中,规定尾数M是二进制小数,它的范围是$[1,2-\epsilon)$
如果按照这样的规定:
$7.0=111.0$
$111.0=1.11\times 2^{10}$,特别说明这里$2^{10}$表示小数点往右移动2位,$10$是二进制数。
可以知道阶码用2位来表示,$E=2$,$M=1.11$,$f=0.11$,$e=bias+E$

举例2

与Intel兼容的处理器采用“扩展精度”浮点形式。这种格式具有80位字长,1个符号位,k=15个阶码位,1个单独的整数位和n=63个小数位。
注意,阶码位15个,其中一个位用来保存阶符。所以如果阶码部分全部为1,其阶码值为$bias=2^{14}-1$
最小的正非规格化数
$1,11\cdots 1(14) \; 00\cdots 0(62)1$,括号表示位值重复了多少次。
相对应的十进制值为$2^{-bias}\times 2 \times 2^{-63}=2^{1-bias-63}$
特别注意,非规格化数的偏置值为$1-bias$而不是$-bias$,多乘了一个2,为什么?这个是为了表示非规格化值平滑转换到规格化值。

最小的正规格化数
$1,11\cdots 1(14) \; 100\cdots 0(62)=2^{-bias}\times 2^{-1}=2^{-(bias+1)}$

最大的规格化数
$0,11\cdots 1(14) \; 11\cdots 1(63)=2^{bias}\times (1-2^{-63})$

举例3

在2008版的IEEE浮点数标准中,为了表示数$\frac{7}{8}$,很显然$s=0$,表示正数,$7=111.0$,$\frac{7}{8}$表示小数点左移3位。
$\frac{7}{8}=\frac{7}{4} \times 2^{-1}$,其中$V=(-1)^{s}\times M \times 2^{E}$,对比一下可以推出$M=\frac{7}{4}$,$E=-1$
$bias=2^{4}-1=15$,$e=E+bias=-1+15=14$,14用二进制表示为$01110$,这是阶码字段。
尾数字段计算如下:$1.11 \times 2^{E}$,其中1.11扩充成10位。$1100000000$表示尾数字段。
$01110 \ combined \ with \ 1100000000=hex(3b00)$

由此我们可以填表:
情况1:机器0
$bias=2^{4}-1=15$
-0,表示机器0,机器0的$M$值为0,由于规格化表示隐含小数点后的第一位是1,所以$e=XXX.100\cdots 0$,即$e=1$,$E=e-bias=1-15=-14$
$V=-0 \ D=-0.0$
$hex(0b10000 \ 0000000000)=0x8000$

情况2:最小的大于2的值
$(-1)^{s} \times M \times 2^{E}$,要使得最小,很显然$E=1$,并且使得$s=0$并且$M$最小。
$e=E+bias=1+15=16$,所以阶码部分可以表示成$10000$,再来看$M$,$M$要尽可能小,怎么样才能让$M$尽可能小,$M$为正数。
$M=0000000001$,这样该值的二进制表示为$100000000000001$,十六进制为$0x4001$
注意到由于是规格化表示,这个数的尾数数值部分应该是$1.000000001$,如果看成是小数点移动,则$10000000001=2^{10}+1=1025$,可以看作小数点向左移动10位,所以$1.000000001=1025/2^{10}=1025/1024$,
所对应的$V=\frac{1025}{1024} \times 2^{E}=\frac{1025}{512}=2.001953125$

情况3:512
$512.0=2^{9} \times 1$,$1=2^{0}$,可以看作不移动小数点。
$M=1.0000000000$,这里只研究小数部分,所以为$.0000000000$
$M=1 \; E=9 \quad e=E+bias=9+15=24=0b11000$
组合起来$11000 \; 0000000000=0x6000$

最大的非规格化数
此时$M$不包括开头的1,最大的值对应的尾数部分是$0.0111111111=001111111111 \times 2^{-10}=\frac{1023}{1024}$
再看阶码部分,非规格化数的阶码恒为$E=1-bias=1-15=-14$,综合看来,$\frac{1023}{1024} \times 2^{-14}=\frac{1023}{2^{24}}$
上述结果为$6.097555160522461e-05$
十六进制的值为$00000001111111111=0x3ff$

负无穷
负无穷就是阶码值全部为1,尾数字段全部为0
$1111110000000000=0xfc00$

十六进制为3bb0的数
$3bb0=011101110110000$,可以去除阶码部分的5位数$01110=14 \quad e=14 \quad E=e-bias=14-15=-1$
再看$M=1110110000=$,其实,实际上表示的数为$1.111011$,规格化数中这里的1省略,$.111011=\frac{111011}{2^{6}}=59/64$
综上$\frac{59}{64} \times 2^{E}=\frac{59}{128}$

举例4

31
对于第一行的例子:$\frac{9}{16}$要凑成一个大于1的数
$\frac{9}{16}=\frac{9}{8} \times \frac{1}{2}=(1+\frac{1}{8}) \times 2^{-1}=(1+\frac{2}{16}) \times 2^{-1}$
$E=-1 \quad e=E+bias=-1+7=6$
可以写成是:$f \quad 0010 \quad \quad e \quad 0110$
$1 \ 0110 \ 0010$

对于1
阶码为$10110$,
$e=22 \quad E=e-bias=22-15=7 \quad f=\frac{0b101}{2^{3}}=\frac{1+4}{8}=\frac{5}{8}$
$M=1+\frac{5}{8}=\frac{13}{8} \quad V=(-1)^{s} \times M \times 2^{E}=13 \times 2^{4}$

先确定下在格式B中的$frac=1010$,$f=\frac{0b1010}{2^{4}}=\frac{5}{8} \quad M=\frac{13}{8}$
$V=(-1)^{s} \times \frac{13}{8} times 2^{E} \quad E-3=4 \quad e=7+bias=14$
$14=0b1110$
$0 \ 1110 \ 1010$

对于2
$e=00111=7 \quad E-7-bias=7-15=-8$
$f=\frac{0b110}{8}=\frac{6}{8} \quad M=1+f=\frac{7}{4}$
$V=(-1)^{s} \times 2^{E} \times M=- \frac{7}{2^{10}}$

在格式B下:
$frac=1100$
$f=\frac{0b1100}{16}=\frac{12}{16}=\frac{3}{4} \quad M=1+f=\frac{7}{4}$
$M \times 2^{E}=\frac{7}{2^{10}} \quad E=-8 \quad e=E+bias=-8+7=-1$
推出在格式B下为非规格化数
由此$e=0b0000 \quad E=1-bias=1-7=-6 \quad 2^{-6} \times M = 7 \times 2^{-10}$
$f=M=7 \times \frac{1}{2^{4}}$
$frac=f \times 16 = 7 = 0b0111$
$1 \ 0000 \ 01111$

对于3
$e=0b00000 \quad E=1-bias=1-15=-14$
$f=M=\frac{0b101}{8}=\frac{1+4}{8}=\frac{5}{8} \quad V=\frac{5}{8} \times 2^{-14}=\frac{5}{2^{17}}$

对于非规格化数
$e=0b0000 \quad E=1-bias=1-7=-6$
$M \times 2^{E}=\frac{5}{2^{17}} \quad M=f=5 \times 2^{-11}$
$frac=f \times 2^4=\frac{5}{2^{7}}$,舍入到1,结果为
$0 \ 0000 \ 0001$

$e=0b0000 \quad E=1-bias=1-7=-6$
$f=M=\frac{1}{16}$
$V=M \times 2^{-6}=\frac{1}{2^{10}}$

对于4
$e=0b11011=27 \quad E=e-bias=27-15=12$
$f=\frac{0b000}{2^3}=0 \quad M=1$
$V=-M \times 2^{12}=-2^{12}$

$frac=0b0000$肯定是不行的,会出现溢出,仅靠e的部分无法表示$2^{12}$
阶码位最大为$4$位,能够取得的最大值为$0b1111$,$e=15 \quad E=e-bias=15-7=8$
但注意到在IEEE标准中,$1111 \ 0000$表示$\infty$,所以我们让$e=14$
$e=14 \quad e=0b1110 \quad E=e-bias=14-7=7$
$V=-2^{12}=-2^{5} \times 2^{7}$
$-2^{5}$舍入到$-31$,所以$V=-31 \times 2^{7}$

$0000$要向上舍入,而原来的A<0,所以取绝对值减一,舍入到$0000-1=1111$
$frac=1111 \quad f=\frac{1111}{16}=\frac{15}{16} \quad M=1+f=\frac{31}{16}$
$V=(-1)^{s} \times \frac{31}{16} \times 2^{E}$
$\frac{31}{16} \times 2^{E}=31 \times 2^{7}$
$e \leq 14$,所以$e \leq 1110 \quad E \leq (e-bias=7)$
$\frac{31}{16}$舍入到$31$
$E=7 \quad e=1110$
$e=1110 \quad frac=1111$
$1 \ 1110 \ 1111 \quad V=- \frac{31}{16} \times 2^{7}=-31 \times 2^{3}$

对于5
$frac=0b100 \quad f=\frac{0b100}{8}=\frac{4}{8}=\frac{1}{2} \quad M=\frac{3}{2}$
$e=0b11000=24 \quad E=e-bias=24-15=9$
$V=(-1)^{s} \times 2^{E} \times M=3 \times 2^{8}$

对于B,$frac=0b1000=8$
$f=\frac{8}{16}=\frac{1}{2} \quad M=1+f=\frac{3}{2}$
$V=3 \times 2^{8}$
$3 \times 2^{8}=\frac{3}{2} \times 2^{E} \quad 2^{8}=2^{E-1} \quad E=9$
$e=9+7=16$,很显然溢出了。
向正无穷舍入$\frac{3}{2}$舍入到$\frac{6}{2}$,即有$3 \times 2^{8}=\frac{3}{2} \times 2^{E}$
$E=8 \quad e=8+7=15 \quad e=0b1111$
$e=0b1111$,很显然结果为$\infty$
$0 \ 1111 \ 0000 \quad V=\infty$

举例5

float类型的值使用32位的IEEE格式,double类型的值使用64位IEEE格式。
随机数转换成为double类型的值,来测试精度的转换。

这里值得注意的是,浮点运算一般是不能结合的。
主要是因为舍入的问题,容易出错。

1
2
3
4
5
6
7
8
9
0.2+0.3=0.5->1
1+0.5=1.5->2
0.3+0.5=0.8->1
0.2+1=1.2->1
(0.2+0.3)+0.5=1+0.5->2
0.2+(0.3+0.5)=0.2+1->1
二者并不相等

在本机上,运行相关代码得到的结果如下:
32

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <stdio.h>
#include <iostream>
#include <limits.h>
#include <assert.h>
#include <ctime>
using namespace std;
/*int create_random()
{
srand((unsigned)time(NULL));
return rand();
}*/
int A(int x,double dx)
{
return (float) x == (float) dx;
}
int B(int x,int y,double dx,double dy)
{
return (dx-dy) == (double) (x-y);
}
int C(double dx,double dy,double dz)
{
return (dx+dy)+dz == dx+(dy+dz);
}
int D(double dx,double dy,double dz)
{
return (dx*dy)*dz == dx*(dy*dz);
}
int E(double dx,double dz)
{
return dx/dx == dz/dz;
}
int main()
{
srand( (unsigned)time(NULL) );
int x = rand();
int y = rand();
int z = rand();
printf("x: %d\n",x);
printf("y: %d\n",y);
printf("z: %d\n",z);
double dx = (double) x;
double dy = (double) y;
double dz = (double) z;
printf("check:\n");
cout<<"A: "<<A(x,dx)<<endl;
cout<<"Another A: "<<A(0x20001,(double)0x20001)<<endl;
cout<<"B: "<<B(0,INT_MIN,(double)0,(double)INT_MIN)<<endl;
dx = (double)0x2001;
dy = (double)INT_MIN;
dz = (double)100;
cout<<"C: "<<C(dx,dy,dz)<<endl;
cout<<"rand c:"<<endl;
dx = (double)rand();
dy = (double)rand();
dz = (double)rand();
cout<<C(dx,dy,dz)<<endl;
dx = (double)rand();
dy = (double)0xFFFFFFFF;
dz = (double)INT_MIN;
cout<<"D: "<<D(dx,dy,dz)<<endl;
dx = (double)rand();
cout<<"E: "<<E(dx,(double)0)<<endl;
}

从以上代码可以看出:
减法行为,在

1
2
x=0;
y=INT_MIN;

会出现溢出错误。

除法行为,在除数为0的时候会发生错误。

举例6

编写一个C函数来计算$2^{x}$的浮点表示。完成这个任务最好的方法是直接创建结果的IEEE单精度表示。当$x$太小时,你的程序会返回$0.0$,当x太大时,它会返回$+ \infty$。填写代码的空白部分,计算正确结果。假设函数$u2f$返回的浮点值与它的无符号参数有相同的位表示。

浮点值和无符号参数的位表示相同

1
2
3
4
5
6
7
float u2f(unsigned x)
{
return *(float*) &x;
// &x是变量x的地址
// (float*) &x 获取float型指针
// *(float*) &x 对指针解引用,得到float型的值
}

$2^{x}$的浮点表示,最终结果是IEEE的单精度表示,如下图所示:
33

先确定偏置量,$bias$等于$exp$中的位数。

1
2
3
4
5
6
7
bias=1<<(8-1)-1=pow(2,7)-1=127
//Denormalized
E=1-bias=2-pow(2,7)
//Normalized
E=e-bias=e-pow(2,7)

1
2
3
4
float fpwr2(int x)
{
// x仅仅表示指数,只需要观察指数部分
}

浮点表示:$(-1)^{s} \times frac \times 2^{E}$

1、x小于最小的非规格化数
此时$E=1-bias=2-pow(2,7)$,而frac部分有23位,全部清0,相当于$2^E>>23$,右移23位可以让$frac$部分清0,这样得到的数比最小的非规格化数还小
$2^{E}>>23$,此时满足的条件是:$x<2-pow(2,7)-23$

2、x小于最小的规格化数,此时$2^x$表示非规格化数
此时$e=1$,$bias=pow(2,7)-1$,$E=e-bias=2-pow(2,7)$
$x<2-pow(2,7)$,此时仅有frac部分。

很显然,此时$E=0$,$2^{E}=1$,所以$2^{x}=frac$
$frac=2^{x}=2^{b}$,$b$此时的值是$x$相对于最小基准$2-pow(2,7)-23$,即只取超出$2-pow(2,7)-23$的部分。

1
frac=1<<(unsigned)(x-(2-pow(2,7)-23))

3、x小于最大的规格化数,此时$2^x$表示规格化数
最大的规格化数,此时指数$E=bias=pow(2,7)-1$,注意到此时E可以取到$pow(2,7)-1$

此时取$frac=0$
$2^{x}=2^{E}$,$x=E=exp-bias$,可以得到$exp=x+bias=x+pow(2,7)-1$

4、剩余情况,取无穷
$exp=0xFF$
$frac=0$

实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
#include <assert.h>
#include <math.h>
#include <iostream>
using namespace std;
float u2f(unsigned x)
//这里涉及到无符号数转换成浮点数
//使用引用
{
return *(float*) &x;
// &x是变量x的地址
// (float*) &x 获取float型指针
// *(float*) &x 对指针解引用,得到float型的值
}
float fpwr2(int x)
{
unsigned expr,frac;
unsigned u;
if(x < 2-pow(2,7)-23)
{
expr = 0;
frac = 0;
}
else if(x < 2-pow(2,7))
{
expr = 0;
frac = 1 << (unsigned)(x - (2-pow(2,7)-23) );
}
else if(x < pow(2,7)-1+1)
{
expr = x + pow(2,7) - 1;
frac = 0;
}
else
{
expr = 0xFF;
frac = 0;
}
u = expr << 23 | frac;
return u2f(u);
}
int main()
{
cout<<"calculate: "<<powf(2,0)<<" test: "<<fpwr2(0)<<endl;
cout<<"calculate: "<<powf(2,100)<<" test: "<<fpwr2(100)<<endl;
cout<<"calculate: "<<powf(2,-100)<<" test: "<<fpwr2(-100)<<endl;
cout<<"calculate: "<<powf(2,10000)<<" test: "<<fpwr2(10000)<<endl;
cout<<"calculate: "<<powf(2,-10000)<<" test: "<<fpwr2(-10000)<<endl;
return 0;
}

举例7

$\pi$的单精度浮点值的十六进制表示为$0x40490FDB$
注意,给的数为单精度浮点型的小数,frac部分有23位,exp部分有8位。
1、二进制小数
表示的二进制小数的小数部分为:
$100 \ 1001 \ 0000 \ 1111 \ 1101 \ 1011$
二进制小数的阶码部分为:
$1000 \ 0000$
$bias=2^{8-1}-1=127$
$E=exp-bias=128-127=1$
由于二进制的阶码部分不为0,所以二进制小数是规格化数,二进制小数可以如下表示:
$1.100 \ 1001 \ 0000 \ 1111 \ 1101 \ 1011$
二进制小数可以表示成:
$1.100 1001 0000 1111 1101 1011 \times 2^{1}=11.0010010000111111011011$

2、$\frac{22}{7}$的二进制小数表示是什么
$\frac{22}{7}=3+\frac{1}{7}$
$3=0b11$
$\frac{1}{7}$的二进制小数表示是:
$\frac{Y}{2^{k}-1}$,可以知道$Y=1 \ k=3$,$y$是一个3位的序列。
可以看作$1>>3=\frac{1}{2^{3}-1}=0.001$
综上$\frac{22}{7}$的二进制表示是:$0b11.001001001(001)$

3、这两个$\pi$的近似值从小数点后第九位开始不同

位级浮点编码规则

对于参数$f$,如果$f$是非规格化的,该函数返回$\pm0$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
float_bits float_denorm_zero(float_bits f)
{
unsigned sign = f >> 31;
//相当于把小数点放置在第31位后面,这样就得到符号位
unsigned exp = f >> 23 & 0xFF;
//相当于把小数点放置在exp位置之后,这样就得到了阶码部分
//取出相应的值,只要&ff就可以
unsigned frac = f & 0x7FFFFF;
//只取小数位,共23位
if(exp == 0)
{
frac = 0;
}
return (sign << 31) | (exp << 23) | frac;
//这里移动小数点,相当于右移小数点
}

例1

对于浮点数$f$,计算$-f$,如果$f=\infty$,函数返回$f$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <iostream>
#include "float_negate.h"
#include <math.h>
#include <cmath>
#include <algorithm>
#include <assert.h>
#include <string.h>
#include <cstring>
#include <limits.h>
#include <climits>
using namespace std;
float_bits float_negate(float_bits f)
{
unsigned sign = f >> 31;
cout << sign << endl;
unsigned exp = f >> 23 & 0xFF;
cout << exp << endl;
unsigned frac = f & 0x7FFFFF;
cout << frac << endl;
if(exp == 0xFF && frac != 0) //NAN
return f;
return (~sign << 31) | (exp << 23) | (frac);
}
int main()
{
unsigned testV;
cin >> testV;
unsigned res = float_negate(testV);
cout << "test value is " << *(float*) (&res) << endl;
cout << "The real value is " << -(*(float*)(&testV)) << endl;
}

实现结果:
34

例2

遵循位级浮点编码规则,实现具有如下原型的函数:

1
float_bits float_absval(float_bits f);

实现方法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <stdio.h>
#include <iostream>
#include <limits.h>
#include <math.h>
using namespace std;
/*
* float-absval.h
*/
typedef unsigned float_bits;
float_bits float_absval(float_bits f);
float_bits float_absval(float_bits f)
{
unsigned sign = f >> 31;
unsigned exp = f >> 23 & 0xFF;
unsigned frac = f & 0x7FFFFF;
int is_NAN = (exp == 0xFF) && (frac != 0);
if(is_NAN)
return f;
return 0 << 31 | exp << 23 | frac;
}
float u2f(unsigned u)
{
return *(float*) &u;
}
unsigned f2u(float u)
{
return *(unsigned*) &u;
}
int main()
{
unsigned testV;
float f_test;
cin >> testV >> f_test;
float testF = u2f(testV);
unsigned u_test = f2u(f_test);
if(isnan(testF))
{
cout << "test " << testF;
cout << "real " << testV;
}
else
{
cout << "test1= " << u2f(float_absval(testV)) << endl;
cout << "real1= " << fabs(testF) << endl;
cout << "test2= " << u2f(float_absval(u_test)) << endl;
cout << "real2= " << fabs(f_test) << endl;
}
}

结果:
35

例3

实现能够计算$2.0 \times f$的函数。

实现函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <stdio.h>
#include <iostream>
#include <limits.h>
using namespace std;
typedef unsigned float_bits;
float_bits float_half(float_bits f);
/*
本例中要求舍入到偶数
0b00 --> 0b00 + addition(0) = 0b00
0b01 --> 0b00 + addition(0) = 0b00
0b10 --> 0b01 + addition(0) = 0b01
0b11 --> /2=1.5=2 --> 0b01 + addition(1) = 0b10
only 0b11 --> addition = 1
if &0b11 == 0b11
addition = 1
else
addition = 0
addition = (frac & 0x3) == 0x3
*/
float_bits float_half(float_bits f)
{
unsigned sign = f >> 31;
unsigned exp = f >> 23 & 0xFF;
unsigned frac = f & 0x7FFFFF;
unsigned remain = f & 0x7FFFFFFF;
int is_NAN_or_infinity = (exp == 0xFF);
if(is_NAN_or_infinity){
return f;
}
int addition = (frac & 0x3) == 0x3;
if(exp == 0)
{
//Denormalized
frac >>= 1;
frac += addition;
}
else if(exp == 1)
{
//Normalized to Denormalized
remain >>= 1;
remain += addition;
exp = (remain >> 23) & 0xFF;
frac = remain & 0x7FFFFF;
}
else
{
//include factor 2
exp -= 1;
}
return sign << 31 | exp << 23 | frac;
}
float u2f(unsigned u)
{
return *(float*) &u;
}
unsigned f2u(float u)
{
return *(unsigned*) &u;
}
int main()
{
float f_test;
cout << "input float : ";
cin >> f_test;
unsigned u_test = f2u(f_test);
float real = f_test / 2;
cout << "real: " << real << endl;
cout << "test: " << u2f(float_half(u_test)) << endl;
}

结果:
36

例4

对于浮点数f,这个函数计算(int)f,如果f是NaN,你的函数应该向0舍入。如果f不能用整数表示,例如,超出表示范围,或者它是一个NaN,那么函数应该返回0x800000000

我们这里仅仅考虑正数的情况:
有如下几种:

第一种:

1
2
3
0 00000000 00000000000000000000000
===>
0 01111111 00000000000000000000000

值所能表示的范围是:
$1.0 \times 2^{0}$,此时$2^{E}=2^0$,对应的指数的值为$E=exp-bias=0$,可以求出$exp=7$

取值范围为:$0 \leq f \leq 1$,值舍入到0

第二种:

1
2
3
0 01111111 00000000000000000000000
===>
0 (01111111+31) 00000000000000000000000

此时,我们得到的上界为$NaN$,浮点数可以表示32为整数,其中最高位为符号位,能够表示的最大的值为$2^{31}-1$,所以最大的$int$用浮点数表示就是:
0 (01111111+31) 00000000000000000000000

第三种:

1
2
3
4
0 (01111111+31) 00000000000000000000000
===>
infinity
return 0x80000000

值得注意的是,把浮点数转换成整形,必须

1
frac | 0x80000000

来获取整数部分,如何最后我们如何舍去小数部分?
采用移位的方式:
$\pm \ 1.frac \times 2^{exp-bias}$,用移位的方式去掉frac部分,如下图:
37

最后我们得到$M \times 2^{E}$,相当于我们在$M$的基础上,执行M<<E运算。

如果$E>23$,则执行$ M \times 2^E $,相当于小数点右移23位,除去小数点,然后再整体执行左移(E-23)位,即M<<(E-23)

如果$E<23$,则执行$M \times 2^{E}$之后还会有小数点,小数点并不能完全消除掉。我们要人为地把小数点后的数全部抛弃,此时小数点的位置在距离末尾(23-E)处,此时M>>(23-E),即可舍去小数点后的部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/*
* float-f2i.h
*/
#include <stdio.h>
#include <iostream>
#include <limits.h>
using namespace std;
typedef unsigned float_bits;
int float_f2i(float_bits f);
int float_f2i(float_bits f)
{
unsigned sign = f >> 31;
unsigned exp = f >> 23 & 0xFF;
unsigned frac = f & 0x7FFFFF;
unsigned bias = 0x7F;
/*
consider positive numbers
0 00000000 00000000000000000000000
===>
0 01111111 00000000000000000000000
1.0*(2^0),now E=exp-bias=0,means exp=7
exp=1111111
now 0<=f<=1
we get integer 0
0 01111111 00000000000000000000000
now E=exp-bias=0 2^E=1
===>
NaN的取值为多少?我们注意到浮点数可以表示32位整数,最高位是符号位
所以能表示的最大的值是2^{31}-1
上面这个数用浮点数表示是:
0 (01111111+31) 00000000000000000000
*/
unsigned M;
unsigned E;
int val;
if(exp >=0 && exp < 0 + bias)
{
val = 0;
}
else if(exp >= 31 + bias)
{
//overflow
val = 0x80000000;
}
else
{
E = exp - bias;
M = frac | 0x800000;
if(E > 23)
val = M << (E - 23);
else
val = M >> (23 - E);
}
return sign ? -val : val;
}
int u2i(unsigned u)
{
return *(int*) &u;
}
unsigned i2u(int u)
{
return *(unsigned*) &u;
}
unsigned f2u(float u)
{
return *(unsigned*) &u;
}
int main()
{
float f_test;
cout << "input float : ";
cin >> f_test;
unsigned u_test = f2u(f_test);
int real = (int)f_test;
//注意,float转换为int,要舍入,直接(int) float_v
//而不是*(int*) float_v
cout << "real : " << real << endl;
cout << "test : " << float_f2i(u_test) << endl;
}

注意,float转换为int,要舍入,直接(int) float_v
而不是(int) float_v

例5

给出一个函数计算(float) i的位级表示。
浮点数向偶数舍入的问题
有效数字超出规定数位,例如,多余数字是1001,超出了规定最低位的一半,(规定最低位的一半为:1000),故最低位进1.
如果多余数字是0111,它小于最低位的一半,则舍掉多余数字(截断尾数)即可
如果对于数字是1000,正好是最低位一半的特殊情况,例如:0 1000,最低位为0,舍掉多余位,1 1000,最低位为1,则舍掉多余位后加1,使得最低位为0(偶数)。

举例,要求保留小数点后3位。

对于1.0011001,舍入处理后为1.010(去掉多余的4位,加0.001)
对于1.0010111,舍入处理后为1.001(去掉多余的4位)
对于1.0011000,舍入处理后为1.010(去掉多余的4位,加0.001,使得最低位为0)

对于1.1001001,舍入处理后为1.101(去掉多余的4位,加0.001)
对于1.1000111,舍入处理后为1.100(去掉多余的4位)
对于1.1001000,舍入处理后为1.100(去掉多余的4位,不加,因为最低位已经为0)

对于1.01011,舍入处理后为1.011(去掉多余的2位,加0.001)
对于1.01001,舍入处理后为1.010(去掉多余的2位)
对于1.01010,舍入处理后为1.010(去掉多余的2位,不加)

对于1.01111,舍入处理后为1.100(去掉多余的2位,加0.001)
对于1.01101,舍入处理后为1.011(去掉多余的2位)
对于1.01110,舍入处理后为1.100(去掉多余的2位,加0.001)

在整数向浮点数转换的过程中,很重要的一点是,浮点数写成$2^{E}$,一定是规格化数,所以$exp$不为0。因为$exp$等于0的情况我们单独考虑。

整数转换成浮点数,需要以下几个函数:
$bit-length()$判断int型有几位,是否超过了最大的32位
frac的位数可能会超过23位,这个时候我们要把特定的舍入位数,比如低xx位取出来,完成这个取出任务所需要的函数是$bits-mask()$,给位数盖一个面罩,然后取出
值得注意的是,由于int转换成float,必定为规格化数,所以最后的fbits=bits-1,float型的frac部分要减去最开始的1

比较难以理解的是$i=0xffffffff$的情况,此时整数转换成浮点数,是一个$-2^{E}$,注意此时frac为0,因为整数并不包含小数点后的部分,frac部分为1.0000…,是一个绝对值非常非常大的负数,指数expe要尽可能大,如果把指数看成是小数点移位的话,指数最大可以取多少呢?可以移动多少位呢?最多为31位。
expe=bias+31

我们让expe=bias+fbits,这样可以看成是小数点在最左边,然后往右移动fbits位。唯一要考虑的就是23位够不够放int型的整数?
int型的整数,罩上mask,获取val值,来进行移位操作
val=i & bits_mask(fbits)

如果值为负数,记得取反加1

思路

1、首先考虑符号位,然后讲i取绝对值,当成一个正数转化即可。然后判断i是2的几次幂,可以通过类似于二分法的方式判断。即右移16位判断是否不为0,如果不为0则exp+16,然后判断右移16位后剩余的位数有几位,否则右移8位判断依次类推。
2、因为是正数,小数点左边存在一个隐式的1,所以num=( ~ (1<< exp ) ) & num ;把最高的1去掉,然后把剩余的数放进frac中,同时要考虑向偶数取整的问题。
3、如果num不足23位,直接移动相应位数,放入frac中,否则截掉多余的位数,如果最后一位并且舍去一段中的最高也为1或者舍去的东西超过0.5那么就给frac+1,判断一下frac时候有溢出,溢出的话给exp+1,然后取剩余的23位的值即可。最后就是给exp加上bias偏置值,前提是如果num不为0。

重要思路:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
unsigned val = i;
unsigned sign = i < 0 ? 1 : 0;
if(sign)
val = ~val + 1;
unsigned exp = 0;
unsigned frac = 0;
unsigned temp = val;
if(val >> 16)
{
exp += 0x10; //除以16,再加回来
val = val >> 0x10;
}
if(val >> 8)
{
exp += 0x8;
val = val >> 0x8;
}
if(val >> 4)
{
exp += 0x4;
val = val >> 0x4;
}
if(val >> 2)
{
exp += 0x2;
val = val >> 0x2;
}
if(val >> 1)
{
exp += 0x1;
val = val >> 0x1;
}
//此时exp表示小数点从右边开始,往左多少位
//去掉小数点最高位1
val = temp;
val = (~(1 << exp)) & val;
//此时val为小数点后面的部分
// (temp >> 23)判断temp大于23位

最终$\times 2^{expe}$小数点在最右边,所以expe实际上表示小数点的实际位置:即从最右边开始,向左移动expe位就是小数点实际位置

舍入原则上面说明了,值得注意的是,向偶数舍入,frac+=1,可能会造成frac溢出
例如: frac=111 1111 1111 1111 1111 1111
frac+1=1000 0000 0000 0000 0000 0000
相当于小数点从右边开始移动到实际位置要多移动1位,所以是expe+=1
frac=frac & 0x7fffff
取最后23位

可能遇到的情况描述如下图:
38
39
40

实现方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <stdio.h>
#include <limits.h>
#include <iostream>
#include <cstdio>
#include <math.h>
using namespace std;
typedef unsigned float_bits;
float_bits float_i2f(int i);
unsigned mask(unsigned bits)
{
return (1 << bits) - 1;
}
unsigned leftmost(unsigned bits)
{
return 1 << bits;
}
float_bits float_i2f(int i)
{
unsigned val = i;
unsigned sign = i < 0 ? 1 : 0;
if(sign)
val = ~val + 1;
unsigned expe = 0;
unsigned frac = 0;
unsigned temp = val;
if(val >> 16)
{
expe += 0x10; //除以16,再加回来
val = val >> 0x10;
}
if(val >> 8)
{
expe += 0x8;
val = val >> 0x8;
}
if(val >> 4)
{
expe += 0x4;
val = val >> 0x4;
}
if(val >> 2)
{
expe += 0x2;
val = val >> 0x2;
}
if(val >> 1)
{
expe += 0x1;
val = val >> 0x1;
}
//此时expe表示小数点从右边开始,往左多少位
//去掉小数点最高位1
val = temp;
val = (~(1 << expe)) & val;
//此时val为小数点后面的部分
if(temp >> 23)
{
unsigned offset = expe - 23;
//溢出部分
frac = val >> offset;
unsigned roundv = 0;
unsigned round_bits = val & mask(offset);
int cond1 = ( (val & mask(offset)) > leftmost(offset-1));
int cond2 = ( (frac & 0x1) && (round_bits == leftmost(offset-1)) );
if( (expe != 23) && (cond1 || cond2) )
{
frac += 1;
}
//向偶数舍入溢出了怎么办?
//小数点从右边开始,往左边多移动1位
if(frac >> 23)
{
expe += 1;
frac = frac & 0x7fffff;
}
}
else
frac = val << (23 - expe);
if(temp)
expe += 127;
return sign << 31 | expe << 23 | frac;
}
float u2f(unsigned u)
{
return *(float*)&u;
}
int main()
{
int i_test;
cout << "input int: ";
scanf("%d",&i_test);
float real = (float) i_test;
printf("real: %f\n",real);
printf("test: %f\n",u2f(float_i2f(i_test)));
}

41

原创技术分享,您的支持鼓励我继续创作