Live in the shadow

0%

CSAPP-DataLab WriteUp

发表于 分类于
CS:APP 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= 0x34，0x1234 & 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);
}