0%

CSAPP-DataLab WriteUp

在这个 Lab 中主要需要完成 bits.c 文件中的部分函数以实现函数功能,代码必须顺序执行,即不能使用 if 条件分支或者 While 循环这一类,此外对于函数的实现必须使用指定的位操作符,例如与或非 (&,|,) 等,具体每个函数的限制也不一样。

在完成 bits.c 后使用 dlc 进行检查,例如./dlc bits.c,检查函数的实现是否遵循指定的规则,检查通过后使用 btest 开始测试函数的输入与输出,btest 需要先编译再运行,例如make clean && make btest && ./btest。btest 将会对每一个函数给定指定的输入,检查输出是否正确,每一个函数都有一个等级与分值,等级越高难度和分数也越高。

具体规则如下:

  • 函数中禁止使用 if, do, while, for, switch 之类的控制语句。
  • 文件中禁止定义任何宏,禁止定义任何额外的函数。
  • 禁止调用函数。
  • 在 int 类型的题目中禁止定义除 int 类型以外的变量。在 float 类型的题目中禁止定义除 int 和 unsigned 类型以外的变量,也禁止使用 flaot 类型与浮点数操作符。
  • 函数中定义 int 类型的常量范围在0x00 <= int <= 0xff,不能大于 0xff。
  • 不能使用全局变量,只能使用函数参数与局部变量。
  • 操作符限制为一元操作符 ! ~ 和位操作符& ^ | + << >>,部分函数中可能仅允许使用一部分操作符。禁止使用二元与三元操作符,例如|| && ? -
  • 在每个函数中会限制出现的操作符的数量,一条语句可以使用多个数量限制内的操作符。

背景知识

在 C 语言中,32 位的操作系统上一个 int 类型的变量占 32 个比特位,即 4 个字节。从右向左,代表从低位到高位,其中最高位 (最左边) 的比特位表示该数字的符号,1 表示该数字为负数,0 表示该数字为正数,后续的 31 个比特位中存放才是该数字的二进制数据,能存储的数字范围为 $-2^31<=int<=2^31$,即 $-2147483648<=int<=2147483648$。与 int 相比,无符号数 unsigned int 不需要符号位,所以可以多存储一位数据,其范围为 $-4294967296<=unsigned<=4294967296$。

上述的数值二进制表示方法称为原码,除了原码,计算机中还有反码与补码两种表示方法。正数的反码与补码和原码相同,而负数的反码为:符号位不变,其余位取反,负数的补码为:负数的反码加 1。反码的意义在于进行减法的时候计算机计算比较方便,而补码的意义在于解决 +0 与 -0 的问题:由于 int 的最高位是符号位,当数据位都为 0 时,数字 0 就有了两种表示方法,符号位是 0(即 0x0)代表 +0 和符号位是 1(即 0x80000000)代表 -0。此外补码还可以得到该数的相反数。

位操作符是 C 语言中最基本的操作符,将两个数字按比特位进行操作,使用位操作符的计算速度是最快的。C 语言中主要有以下位操作符,其中移位运算符的优先级比算术运算符的优先级更低。

符号 名称 说明
& 位且 两个数按位进行且运算,两个相比较的比特位中只要有一个 0,那么该位的结果就是 0
| 位或 两个数按位进行或运算,两个相比较的比特位中只要有一个 1,那么该位的结果就是 1
^ 异或 两个数按位进行异或运算,两个相比较的比特位如果不一样那么该位的结果为 1,否则为 0
~ 取反 将该数按位进行取反,0 变成 1,1 变成 0
<< 算术左移 将该数每一位左移指定位数,右边补 0,左移几位就是将原数乘以 2 的几次方
>> 算术右移 将该数每一位右移指定位数,左边补符号位,若符号位是 1 则补 1,负责补 0,仅针对正数而言右移几位就是将原数除以 2 的几次方

浮点数的表示方法与整数完全不同。IEEE 规定单精度浮点数 float 用 1 位表示符号,8 位表示指数,剩下的 23 位表示尾数,双精度浮点数用 1 位表示符号,11 位表示指数,剩下的 52 位表示尾数。在计算机中任何浮点数都可以表示为
$$(-1)^s*(1.m)^*2^(E-127)$$

其中 s 代表符号位,m 代表尾数,E 代表阶码。

  • 如果阶码 E=255 并且 m 非零,则该数不是一个属,代表 NaN(Not a number)。
  • 如果阶码 E=255 并且 m 为 0,那么该数根据符号位代表正负无穷。
  • 如果阶码 E=0 并且 m 为 0,那么该数根据符号位代表正负零。

Bit Manipulations

bitAnd

使用 ~|实现位与运算符,例如bitAnd(6, 5) = 6 & 5 =4,最大操作符数量为 8,等级为 1。根据对合律与对偶律可得a&b = ~(~(a&b))=~(~a|~b)

1
2
3
4
5
6
7
8
9
10
/*
* bitAnd - x&y using only ~ and |
* Example: bitAnd(6, 5) = 4
* Legal ops: ~ |
* Max ops: 8
* Rating: 1
*/
int bitAnd(int x, int y) {
return ~(~x | ~y);
}

getByte

获取一个整数 x 中的第 n 个字节,n 的范围在0 <= n <= 3,例如getByte(0x12345678,1) = 0x56。允许的操作符为! ~ & ^ | + << >>,最大操作符数量为 6,等级为 2。

可以利用位且操作符的性质,让其余位清 0 即可获取指定位的数值,例如0x1234 & 0x00ff= 0x340x1234 & 0xff00 = 0x12。可以让 0xff 左移 n*8 位就可以获取第 n 个字节,其余位都被清 0 了,之后再将获取到的字节右移回 n*8 位就可以了。由于无法使用乘号*,但是乘数刚好是 2 的倍数,因此可以使用左移代替乘法n * 8 = n << 3。原理如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
// x=0x12345678, n=1
0x12345678

// 将 0xff 左移 8*1 位
0x000000ff
0x0000ff00

// 与原数进行位且运算
0x00005600

// 再右移 8*1 位
0x00000056

注意 C 语言里使用的是算术右移,即有符号数右移时符号位保持不变,符号位向右移动后正数在符号位补 0,负数补 1,因此若右移了一个负数,则被右移的位数上将都为 1,因此在最后还需要使用位且运算符只保留前 1 个字节。如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// x=0x80000000, n=3
0x80000000

// 将 0xff 左移 8*3 位
0x000000ff
0xff000000

// 进行位且运算
0x80000000

// 再右移 8*3 位
0xffffff80 // 由于是负数,符号位补 1,因此右移了很多 1
0x000000ff // 进行位且运算将其余字节清 0
0x00000080
1
2
3
4
5
6
7
8
9
10
11
/*
* getByte - Extract byte n from word x
* Bytes numbered from 0 (LSB) to 3 (MSB)
* Examples: getByte(0x12345678,1) = 0x56
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 6
* Rating: 2
*/
int getByte(int x, int n) {
return ((x & (0xff<<(n<<3))) >> (n<<3)) & 0xff;
}

logicalShift

将整数 x 右移 n 位,n 的范围在0 <= n <= 31,例如logicalShift(0x87654321,4) = 0x08765432。允许的操作符为! ~ & ^ | + << >>,最大操作符数量为 20,等级为 3。

在 C 语言里的位右移是算术右移,若右移的数是有符号数,则符号位正数补 0,负数补 1,例如 0x8000 右移 8 位得到 0xff80,而逻辑右移是不管符号位的,全部补 0。因此在执行算术右移以后,需要将被移动的位数全部清 0。将 0x1 左移 31 位以后就变成了 0x80000000(0b100000…),这时再使用算术右移 n-1 位就可以将前 n-1 位指定为 1,再取反就可以将前 n-1 位清 0。原理如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0x00000001
// 左移 31 位
0x80000000
// 再右移 n-1 位,假设 n=5
0xf8000000
// 变成 0b1111 1000 0000... 再取反
0x07ffffff
// 变成 0b0000 0111 1111...

// 假设原数为 0x80000000,即 0b1000 0000 0000...
0x80000000
// 将原数算术右移 n=5 位,变成 0b1111 1100 0000...
0xfc000000
// 再与前面得到的 0x07ffffff 位且运算,前 5 位被清零
0x04000000
// 即可得到逻辑位移的结果
1
2
3
4
int logicalShift(int x, int n) {
int one = 0x1;
return (x >> n) & ~(((one << 31) >> n) << 1);
}

bitCount

获得整数 v 中二进制 1 的个数,例如bitCount(5) = 2, bitCount(7) = 3。允许的操作符为! ~ & ^ | + << >>,最大操作符数量为 40,等级为 4。

这个题非常难,其原理就是将 32 位进行分组,每 2 位为一组,分别计算出每组 1 的数量,关于计算每组 1 的数量可以使用 010101…这样的掩码,先用位且运算计算每组低位 1 的数量,再将原数右移 1 位计算每组高位 1 的数量,相加即可得到每组 1 的数量,例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 假设原数为 0x7a2d,其二进制如下
0b01 11 10 10 00 10 11 01
// 掩码如下
0b01 01 01 01 01 01 01 01
// 进行且或运算得到每组低位 1 的数量得到结果 a
0b01 01 00 00 00 00 01 01

// 将原数右移 1 位,这样高位就到了低位
0b00 11 11 01 00 01 01 10
// 与掩码进行且或运算计算每组低位 1 的数量得到结果 b
0b00 01 01 01 00 01 01 00

// 将结果 a 与结果 b 相加即可得到每组 1 的数量
0b01 01 00 00 00 00 01 01 +
0b00 01 01 01 00 01 01 00 =
0b01 10 01 01 00 01 10 01

之后再每 2 组相加得到每 4 组 1 的数量,相加可以使用掩码 00110011…,分别得到低两位 1 的数量与高两位 1 的数量,再相加,例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 刚才计算每两位为一组的 1 的数量
0b0110 0101 0001 1001
// 掩码如下
0b0011 0011 0011 0011
// 进行且或运算得到每组低两位的 1 的数量得到结果 a
0b0010 0001 0001 0001

// 将原数右移 2 位,这样高两位就到了低两位
0b0001 1001 0100 0110
// 与掩码进行且或运算计算每 4 位一组的低两位 1 的数量得到结果 b
0b0001 0001 0000 0001

// 将结果 a 与结果 b 相加即可得到每组 1 的数量
0b0010 0001 0001 0001 +
0b0001 0001 0000 0001 =
0b0011 0010 0001 0010

之后再重复这样的操作,再分为 8 位一组计算,掩码为 0b0000111100001111…,再分为 16 位一组计算,掩码为 0b0000000011111111…,最后相加即可得到 32 位里 1 的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
* bitCount - returns count of number of 1's in word
* Examples: bitCount(5) = 2, bitCount(7) = 3
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 40
* Rating: 4
*/
int bitCount(int v) {
int tmp = 0x55|(0x55<<8);
int mask_2bit = tmp|(tmp<<16); // 0b01010101...
tmp = 0x33|(0x33<<8);
int mask_4bit = tmp|(tmp<<16); // 0b001100110011...
tmp = 0x0f|(0x0f<<8);
int mask_8bit = tmp|(tmp<<16); // 0b0000111100001111...
int mask_16bit = 0xff|(0xff<<16); // 0b0000000011111111...
int mask_32bit = 0xff|(0xff<<8); // 00000000000000001111111111...

int c = (v&mask_2bit) + ((v>>1)&mask_2bit); // Each group with 2 bits.
c = (c&mask_4bit) + ((c>>2)&mask_4bit); // Each group with 4 bits.
c = (c&mask_8bit) + ((c>>4)&mask_8bit); // Each group with 8 bits.
c = (c&mask_16bit) + ((c>>8)&mask_16bit); // Each group with 16 bits.
return (c&mask_32bit) + ((c>>16)&mask_32bit); // Only one group with 32 bits.
}

bang

不使用非运算符计算出!x,例如bang(3) = 0, bang(0) = 1。允许的操作符为~ & ^ | + << >>,最大操作符数量为 12,等级为 4。

非运算符的作用非常简单,就是 0 返回 1,非 0 返回 0,所以重点就需要判断输入的数是否是 0。关于判断是否为 0 有两种方法,一种是将二进制位所有高位的 1 全部右移到低位,直到只剩下 1 个二进制位为止,直接判断该二进制是否为 0 即可,如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 设原数 x 为 0x18
0b00011000
// 右移一半(4 位)
0b00000001
// 与原数做位或运算得到结果 a
0b00011001
// 再将 a 右移一半(2 位)
0b00000110
// 与 a 做位或运算得到结果 b
0b00011111
// 再将 b 右移一半(1 位)
0b00001111
// 与 b 做位或运算得到结果 c
0b00011111
// 取 c 的最后一位就可以判断原数 x 是否含有 1

另一种方法就是利用 0 的补码的特殊性质。计算补码使用的公式为 ~x+1,而除了 0 和 0x80000000 以外其他数使用该公式都会得到其相反数,最高位符号位总是不同。而 0 和 0x80000000 这两个数计算出来的则是他们本身:如果要计算 0 的补码,就需要计算~0+1,而~0 的值是 0xffffffff,如果再加 1 则会溢出,变成 0x0,所以 0 的补码还是 0,最高位也是 0,而 0x80000000 的补码最高位还是 1,因此就可以通过比较x~x+1的符号位是否是 1 来判断 x 是否是 0。

1
2
3
4
5
6
7
8
9
10
/*
* bang - Compute !x without using !
* Examples: bang(3) = 0, bang(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int bang(int x) {
return ((x >> 31) | ((~x + 0x1) >> 31)) + 0x1;
}

Two’s Complement Arithmetic

tmin

返回最小的补码整数。限制的操作符为! ~ & ^ | + << >>。最大操作符数目为 4。等级为 1。最小的补码整数为 0x80000000。

1
2
3
4
5
6
7
8
9
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
return 0x1 << 31;
}

fitsBits

判断一个数 x 是否可以用 n 位补码表示,其中1 <= n <= 32。例如fitsBits(5,3) = 0, fitsBits(-4,3) = 1。允许使用的操作符为! ~ & ^ | + << >>。最大操作符数量为 15。等级为 2。

此题化简一下就是需要判断:

  1. 如果是正数且 x 的第 n 位为 0,那么就可以用 n 位补码表示。
  2. 如果是负数且 x 的第 n 位为 1,那么就可以用 n 位补码表示。

其原理为:如果要用 n 位的补码表示,那么所表示出来的补码第 n 位必须作为符号位,如果原码第 n 位与其符号位不相同,那么就需要 n+1 位补码才能表示。例如:

1
2
3
4
5
6
7
8
9
10
11
// 0x5
0b0000...0101
// 其补码为
0b0000...0101
// 如果要用 3 位补码表示那么表示出的补码第 3 位必须为 0,但是 0x5 的原码第 3 为是 1,所以至少需要 4 位 0b0101 才能表示 0x5。

// -0x4
0b1000...0100
// 其补码为
0b1111...1100
// 补码的第 3 位是 1,正好可以代表符号位,因此可以用 3 为补码 0b100 代表 -4。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
* fitsBits - return 1 if x can be represented as an
* n-bit, two's complement integer.
* 1 <= n <= 32
* Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 2
*/
int fitsBits(int x, int n) {
int isNeg = x >> 31;
int shift = n + (~0);
return (!(x >> shift) & !isNeg) | (!(~x >> shift) & isNeg);
}

divpwr2

实现计算 x 除以 2 的 n 次方,其中0 <= n <= 30,向 0 取整,例如divpwr2(15,1) = 7, divpwr2(-33,4) = -2。允许的操作符为! ~ & ^ | + << >>,最大操作符数量为 15,等级为 2。

如果是正数的话右移 n 位就是除以 2 的 n 次方,但是对负数并不适用,由于需要向 0 取整,而移位运算都是向下取整,因此就需要给负数添加一个补充值:$2^n-1$

1
2
3
4
5
6
7
8
9
10
11
12
/*
* divpwr2 - Compute x/(2^n), for 0 <= n <= 30
* Round toward zero
* Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 2
*/
int divpwr2(int x, int n) {
int comple = (1<<n) + (~0); // 2^n - 1
return (x + ((x >> 31) & comple)) >> n;
}

negate

返回 x 的相反数,例如negate(1) = -1。允许的操作符为! ~ & ^ | + << >>,最大操作符数量为 5,等级为 2。前面提到过,使用计算补码的公式即可得到一个数的相反数。

1
2
3
4
5
6
7
8
9
10
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return ~x + 0x1;
}

isPositive

判断一个数是否为正数,例如 isPositive(-1) = 0。允许的操作符为! ~ & ^ | + << >>,最大操作符数量为 8,等级为 3。首先需要使用!x 判断是否为 0,之后就可以判断符号位是否为 1。

1
2
3
4
5
6
7
8
9
10
11
/*
* isPositive - return 1 if x > 0, return 0 otherwise
* Example: isPositive(-1) = 0.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 8
* Rating: 3
*/
int isPositive(int x) {
int isZero = !x;
return !((x >> 31) & 0x1) & !isZero;
}

isLessOrEqual

判断一个数是否小于等于另一个数,例如isLessOrEqual(4,5) = 1。允许的操作符为! ~ & ^ | + << >>,最大操作符数量为 24,等级为 3。

根据不等式的性质可以将 x <= y 转化为 0 <= y-x,就是需要判断y-x 是不是负数,其中 -x 可以表示为~x+1,但是要分三种情况:

  1. x 和 y 同号,直接做减法不会溢出。
  2. x 和 y 异号,可能会发生溢出。该情况下若 x 为负数,则肯定返回 1,否则肯定返回 0。
  3. x 和 y 相等。
1
2
3
4
5
6
7
8
9
10
11
/*
* isLessOrEqual - if x <= y then return 1, else return 0
* Example: isLessOrEqual(4,5) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
* Rating: 3
*/
int isLessOrEqual(int x, int y) {
int diffSign = !(x >> 31) ^ !(y >> 31);
return (diffSign & (x >> 31)) | (!diffSign & !((y + (~x + 1)) >> 31));
}

ilog2

返回以 2 为底的 log(x),其中x > 0,例如ilog2(16) = 4。允许的操作符为! ~ & ^ | + << >>,最大操作符数量为 90,等级为 4。

此题解法来自stackoverflow

可以用公式表示为

$$log_2(x) = 16a + 8b + 4c + 2d + 1*e (a,b,c,d,e = 0 or 1)$$

依次求出 abcde 即可。

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
/*
* ilog2 - return floor(log base 2 of x), where x > 0
* Example: ilog2(16) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 90
* Rating: 4
*/
int ilog2(int x) {
int i, j, k, l, m;
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);

// i = 0x55555555
i = 0x55 | (0x55 << 8);
i = i | (i << 16);

// j = 0x33333333
j = 0x33 | (0x33 << 8);
j = j | (j << 16);

// k = 0x0f0f0f0f
k = 0x0f | (0x0f << 8);
k = k | (k << 16);

// l = 0x00ff00ff
l = 0xff | (0xff << 16);

// m = 0x0000ffff
m = 0xff | (0xff << 8);

x = (x & i) + ((x >> 1) & i);
x = (x & j) + ((x >> 2) & j);
x = (x & k) + ((x >> 4) & k);
x = (x & l) + ((x >> 8) & l);
x = (x & m) + ((x >> 16) & m);
x = x + ~0;
return x;
}

Floating-Point Operations

float_neg

返回 uf 的相反数,如果 uf 是 NaN 则返回自身。允许使用条件与循环语句。允许使用任何 int 与 unsigned 操作符。最大操作符数量为 10,等级为 2。

可以直接修改符号位返回相反数。另外如果 uf 的指数位为 0xff 并且小数位非 0 时,uf 为 NaN,因此就需要判断 uf 的绝对值是否大于 0x7f800000。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
* float_neg - Return bit-level equivalent of expression -f for
* floating point argument f.
* Both the argument and result are passed as unsigned int's, but
* they are to be interpreted as the bit-level representations of
* single-precision floating point values.
* When argument is NaN, return argument.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 10
* Rating: 2
*/
unsigned float_neg(unsigned uf) {
int mask = 1 << 31;
if ((uf & ~mask) > (0xFF << 23))
return uf;
return uf ^ mask;
}

float_i2f

将一个整数转换为浮点数表示的形式。允许使用条件与循环语句,允许使用任何 int 和 unsigned 操作符。。最大操作符数量为 30,等级为 4。

浮点数的表示主要有三个部分:符号位 sign,指数位 exp 和小数位 frac。首先找到符号位后将 x 取绝对值 (符号位归 0),通过右移找到 x 最高位的 1 的位置(找到 x 的 2 的最高次方) 再加 127 就得到指数位 exp,之后就需要计算小数位 frac,由于 int 有 31 位,而浮点数小数位只有 23 位存放数据,因此从 int 转为 float 会丢失 8 位的精度,这时就需要对小数位向偶数舍入。int 类型中有两个特殊值:0 和 0x80000000,这两个特殊值不能通过移位计算指数位与小数位因此要单独处理。

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
/*
* float_i2f - Return bit-level equivalent of expression (float) x
* Result is returned as unsigned int, but
* it is to be interpreted as the bit-level representation of a
* single-precision floating point values.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 4
*/
unsigned float_i2f(int x) {
int sign, exp, frac, bitc, tailb;

if (x == 0) return 0;
else if (x == 0x80000000) return 0xCF000000;

sign = (x >> 31) & 0x1;
if (sign) x = -x;

// count bits to the right of MSB
bitc = 1;
while ((x >> bitc) != 0)
bitc++;
bitc--;

exp = bitc + 127;

x = x << (31 - bitc); // clear all those zeros to the left of MSB
frac = (x >> 8) & 0x7FFFFF;

// round to even (nearest)
if (bitc > 23) {
tailb = x & 0xFF; // byte to round

if ((tailb > 128) || ((tailb == 128) && (frac & 1))) {
frac += 1;
if (frac >> 23) {
exp += 1;
frac = 0;
}
}
}

return (sign << 31) | (exp << 23) | frac;
}

float_twice

返回浮点数 uf 乘 2 的结果,如果 uf 为 NaN 则返回自身。允许使用条件与循环语句,允许使用任何 int 和 unsigned 操作符。最大操作符数量为 30,等级为 4。浮点数乘 2 其实就是将 exp 加 1,但是需要单独处理一些特殊情况,例如 NaN,正负 0(0x0, 0x80000000)和非规格化的浮点数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
* float_twice - Return bit-level equivalent of expression 2*f for
* floating point argument f.
* Both the argument and result are passed as unsigned int's, but
* they are to be interpreted as the bit-level representation of
* single-precision floating point values.
* When argument is NaN, return argument
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 4
*/
unsigned float_twice(unsigned uf) {
int mask = (0x1 << 31);

if ((uf & ~mask) >= (0xFF << 23))
return uf;
else if ((uf & (0xFF << 23)) == 0)
return (uf & ~(0x1FF << 23)) << 1 | (uf & mask);

return uf + (1 << 23);
}