CMU 15-213 A1 实现笔记

之前的图形学的 15-462 在 1 月 9 日的时候跟完了,不过 A2 和 A4 没有写实现笔记(A4 可能考虑补写一下,也可能会鸽掉)。

15-213 是 CS:APP 对应的课程,是我刚入大学时不久后就想跟的课程,一直拖到了现在,不过意外地发现可以和 CMU 同步。课程网站:Introduction to Computer System - CMU 15-213

这课还有一个 A0,不过比较基础就不记录了(但还是花了比预想多 10~15min 的时间吧。。。)

A1 的 pdf 没有挂在课程网站上,在 GitHub 上发现每年的题好像都略有不同,不过都挺有意思的。我用的是 tinylcy/cmu-15213 的版本(其实是因为 clone 后才发现每年不一样。。。)。

A1 是在一个比较严苛的约束下实现一些常见的操作,是若干道迷题的形式,感觉很好玩,而且有些并不容易。。。

简介

A1(Data lab)是在一个比较严苛的约束下实现一些常见的操作,「严苛的约束」具体指:

只允许:

  1. 使用 0 ~ 255 的 int 常量
  2. 定义 int 局部变量
  3. 使用运算符 !~&^|+>><<

不允许:

  1. 使用条件控制与循环语句
  2. 定义或使用宏和函数
  3. 使用要求以外的运算符
  4. 使用任何形式的类型转换
  5. 使用 int 以外的类型(int 数组也是禁止的)

可以认定:

  1. 使用补码
  2. >> 执行算术右移
  3. 超过字宽的移位操作是为定义的

此外,每道题目都有运算符使用数目的限制。在一些题目中,可用运算符的种类会进一步减少。

在浮点数部分,要求降低,额外允许:

  1. 条件控制与循环语句
  2. ||&&
  3. unsigned int 常量与变量,常量也不再有范围限制

可以认定是 IEEE 754 的浮点数。

题目还有 1、2、3、4 不同的分值,分值同时代表了难易度。

Bit Manipulations

1.1 bitAnd(int x, int y)

  • 按位与
  • 额外限制:只允许 ~ 和 |
  • 运算符数目限制:8

用德摩根定律就好了。

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));
}

使用运算符数:4

1.2 getByte(int x, int n)

  • 获取 \(x\) 的从低位起第 \(n\) 个字节的内容,从 \(0\) 开始
  • 运算符数目限制:6

右移并与 0xFF 取按位与就好了,乘以 2 的次幂用左移实现。

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 >> (n << 3)) & 0xFF;
}

使用运算符数:3

1.3 logicalShift(int x, int n)

  • 实现逻辑右移
  • 运算符数目限制:20

逻辑右移后,高位一定都是 0,只要把算术右移的结果对形如 \((0\dots01\dots1)_2\) 的数取按位与就好了。

实现中用到了算术右移的特性;此外,需要到右移 \(n - 1\) 位,用右移后左移实现。

1
2
3
4
5
6
7
8
9
10
11
/*
* logicalShift - shift x to the right by n, using a logical shift
* Can assume that 0 <= n <= 31
* Examples: logicalShift(0x87654321,4) = 0x08765432
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 3
*/
int logicalShift(int x, int n) {
return (x >> n) & ~(1 << 31 >> n << 1);
}

使用运算符数:6

1.4 bitCount(int x)

  • 求二进制下为 1 的位数
  • 运算符数目限制:40

我承认,我不会,我太菜了。。。

显然,一位一位的取出来并加起来运算符数是超了的。解决思路是分成 8 段,每段 4 位,先同步求出每段的 bitcount,再一半一半地加起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
* bitCount - returns count of number of 1's in word
* Examples: bitCount(5) = 2, bitCount(7) = 3
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 40
* Rating: 4
*/
/* It is NOT my work... */
int bitCount(int x) {
int m1 = 0x11 | (0x11 << 8);
int mask = m1 | (m1 << 16);
int s = x & mask;
s += x >> 1 & mask;
s += x >> 2 & mask;
s += x >> 3 & mask;
/* Now combine high and low order sums */
s = s + (s >> 16);

/* Low order 16 bits now consists of 4 sums.
Split into two groups and sum */
mask = 0xF | (0xF << 8);
s = (s & mask) + ((s >> 4) & mask);
return (s + (s >> 8)) & 0x3F;
}

代码中,15 行结束后,s 中存了 8 段的 bitcount,这些和的最低位分别在第 0、4、8、……、24、28 位上;17 行合并第 0 位与第 16 位、第 4 位与第 20 位等的和;22 行合并第 0 位与 4 位、第 8 位与第 12 位;23 行合并仅剩的第 0 位与第 8 位。

使用运算符数:25

1.5 bang(int x)

  • 实现 !x
  • 额外限制:不能使用 !
  • 运算符数目限制:12

同样的,一位一位地或起来会超数目,所以用一半一半合并的思路得到所有位或起来的值。

这题做的比上一道早,明明这题里这个思路是能想到的,到上一题哪里怎么就想不到呢。。。QAQ

这几个分值为 4 的题,感觉要不是搞过 OI/XCPC,不然大概率是做不出来了。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
* bang - Compute !x without using !
* Examples: bang(3) = 0, bang(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int bang(int x) {
int t0 = x | (x >> 16);
int t1 = t0 | (t0 >> 8);
int t2 = t1 | (t1 >> 4);
int t3 = t2 | (t2 >> 2);
int t4 = t3 | (t3 >> 1);
return ~t4 & 1;
}

使用运算符数:12(怕不是撞了标程)

Two’s Complement Arithmetic

2.1 tmin()

  • 返回 INT_MIN
  • 运算符数目限制:4

直接返回 1 << 31 就是了。

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 1 << 31;
}

使用运算符数:1

2.2 fitsBits(int x, int n)

  • 判断 \(x\) 是否能用 \(n\) 位下的补码正确表示
  • 运算符数目限制:15

能在 \(n\) 位补码表示的数有一个特性是,除去低 \(n - 1\) 位,剩下的高位部分不是全 1 就是全 0,只要能判断一种情况,再用相同的方法判断一次 ~x ,把结果或起来即可。

我选择判断全 1,想法是用形如 \((1\dots 10\dots0)_2\) 的数与 \(x\) 按位与,判断得到的结果是否还满足这个形式,而这个形式的数在右移几位后(这里是 \(n\) 位)会得到 -1,-1 可以加一后用 ! 判断。

减法用加补码实现,也就是代码里的 n + ~0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
* 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 mask, t, r0, r1;
n = n + ~0;
mask = ~(1 << n) + 1;
t = (mask & x) >> n;
r0 = !(t + 1);
x = ~x;
t = (mask & x) >> n;
r1 = !(t + 1);
return r0 | r1;
}

使用运算符数:12

2.3 divpwr2(int x, int n)

  • 计算 \(x / (2^n)\),向零取整
  • 运算符数目限制:15

算术右移是向下取整,与向零取整的区别仅在负数时出现,所以只要分别计算向下取整和向上取整的结果,取出符号位后用类似 2-1 多路复用器的思路做返回值。(学了数逻后发现不会用多路复用器以外的词来描述这个东西。这个思路在我后续的解题中还出现了不少)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
* 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 r0, r1, sgn;
r0 = x >> n;
r1 = (x + (1 << n) + ~0) >> n;
sgn = x & (1 << 31);
sgn = sgn >> 31;
return (sgn & r1) | (~sgn & r0);
}

14 行利用了算术右移的特性,把 sgn 变成全 1 或全 0。

使用运算符数:13

2.4 negate(int x)

  • 返回相反数
  • 运算符数目限制:5

补码的定义。

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 + 1;
}

使用运算符数:2

2.5 isPositive(int x)

  • 判断是否为正数
  • 运算符数目限制:8

判断符号位能判断出非负数,再额外判一个 0 即可。

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 sgn = x & (1 << 31);
return !sgn & (!!x);
}

使用运算符数:6

2.6 isLessOrEqual(int x, int y)

  • 判断是否 \(x \leq y\)
  • 运算符数目限制:24

等价于判断 \(y - x \geq 0\) ,只需判断差的符号位,但这个差会爆 int,所以考虑分高低 16 位判断。

高位的差为正数,或高位差为 0 且低位差非负就说明 \(x \leq y\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
* 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 sgn, mask;
int xh, xl, yh, yl, dh, dl, sh, sl, rh, rl;
sgn = 1 << 31;
mask = (1 << 16) + ~0;
xh = x >> 16;
yh = y >> 16;
xl = x & mask;
yl = y & mask;
dh = yh + ~xh;
dl = yl + ~xl + 1;
sh = dh & sgn;
sl = dl & sgn;
rh = !sh;
rl = !(dh + 1) & !sl;
return rh | rl;
}

使用运算符数:21

一开始觉得负数的算术右移会影响我,想着转成无符号数比较(反转符号位后的无符号数大小关系与原来的有符号数大小关系相同),但运算符数超了 1 个。。。

2.7 ilog2(int x)

  • 返回 \(\lfloor \log_2(x) \rfloor\)
  • 运算符数目限制:90

看到 90 时吓了一跳,想了一段时间后还是出来了。

一开始写成了与 lowbit 相对应的「highbit」(即小于等于 \(x\) 的最大的 2 的整次幂),不过改成要求的东西并不需要改多少。

尽管限制有 90 个,一位一位地做还是会超的。

考虑依次用 0xFFFF_00000xFF00_FF000xF0F0_F0F00xCCCC_CCCC0xAAAA_AAAA 的掩码取判断,第一个掩码检测通过时,答案加 16,否则不变,之后用结果改变第二个掩码为 0xFF00_00000x0000_FF00 ;第二个掩码通过时加 8,之后改变第三个掩码为 0xF000_00000x00F0_00000x0000_F0000x0000_00F0 中的一个,以此类推。

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
/*
* 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 m2, m4, m8, m16, m32, mask;
int t, b0, b1, res;

t = 1 << 31 >> 15;
m2 = t; // 0xFFFF_0000

t = t << 8;
mask = (1 << 16) + ~0;
m4 = (t >> 16) & mask;
m4 = m4 | (m4 << 16); // 0xFF00_FF00

m8 = 0xF0;
m8 = m8 | (m8 << 8);
m8 = m8 | (m8 << 16); // 0xF0F0_F0F0

m16 = 0xCC;
m16 = m16 | (m16 << 8);
m16 = m16 | (m16 << 16); // 0xCCCC_CCCC

m32 = 0xAA;
m32 = m32 | (m32 << 8);
m32 = m32 | (m32 << 16); // 0xAAAA_AAAA

t = x & m2;
b0 = (!t) << 31 >> 31;
b1 = ~b0;
mask = (b0 & m2) | (b1 & ~m2);
m4 = m4 & ~mask;
res = b1 & 16;

t = x & m4;
b0 = (!t) << 31 >> 31;
b1 = ~b0;
mask = mask | (b0 & m4) | (b1 & ~m4);
m8 = m8 & ~mask;
res = res + (b1 & 8);

t = x & m8;
b0 = (!t) << 31 >> 31;
b1 = ~b0;
mask = mask | (b0 & m8) | (b1 & ~m8);
m16 = m16 & ~mask;
res = res + (b1 & 4);

t = x & m16;
b0 = (!t) << 31 >> 31;
b1 = ~b0;
mask = mask | (b0 & m16) | (b1 & ~m16);
m32 = m32 & ~mask;
res = res + (b1 & 2);

t = x & m32;
b0 = (!t) << 31 >> 31;
b1 = ~b0;
// mask = mask | (b0 & m32) | (b1 & ~m32);
res = res + (b1 & 1);

return res;
}

使用运算符数:好像是 83,不想再数一遍了。。。

65 行的注释去掉,返回 ~mask 就是所谓「highbit」了。

Floating-Point Operations

3.1 float_neg(unsigned uf)

  • 返回 uf 相应的单精度浮点数的相反数,若为 NaN 则返回原值
  • 运算符数目限制:10

只要根据 IEEE 754 判断 NaN 就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
* 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 = 0x7F800000;
if ((mask & uf) == mask) {
mask = ~mask ^ (1 << 31);
if (mask & uf) return uf;
}
return uf ^ (1 << 31);
}

使用运算符数:7(好像是不算关系比较符的)

3.2 float_i2f(int x)

  • 返回 (float) x
  • 运算符数目限制:30

(float) x 是「四舍六入五靠偶」的,确切地说,是正好一半才靠偶。本题的唯一难点也就在这了。

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
/*
* 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 highbit, lb, sgn, exp;
unsigned res, y;
if (x < 0) {
y = -x;
sgn = 0x80000000;
} else {
y = x;
sgn = 0;
}
for (highbit = 31; highbit >= 0; highbit--) if (y & (1 << highbit))
break;
if (highbit < 0) return 0;
lb = highbit - 23;
if (highbit >= 24) {
int mask = (1 << lb) - 1;
int half = 1 << (lb - 1);
int trunc = y & mask;
res = y >> lb;
if (trunc > half || (trunc == half && (res & 1))) {
++res;
if (res & 0x01000000) {
res = res >> 1;
++highbit;
}
}
} else {
res = y << (-lb);
}
res = res | sgn;
exp = highbit + 127;
res = (res & 0x807FFFFF) | (exp << 23);
return res;
}

使用运算符数:26(好像是不算关系比较符的)

为了减少数目把类似 1 << xxx 的数都写成常数了。

3.3 float_twice(unsigned uf)

  • 返回 uf 相应的浮点数的两倍,NaN 则返回原值
  • 运算符数目限制:30

其实 inf 也是返回原值,而 inf 和 NaN 的指数部分是一样的。

规约化数只要指数部分加一,

而非规约化数,无论两倍后是非规约化数还是规约化数,操作都是左移底数,当结果是规约化数的时候正好是对的。

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
/*
* 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 exp, frac;
unsigned res;
if ((uf & 0x7F800000) == 0x7F800000) return uf;
exp = uf & 0x7F800000;
frac = uf & 0x007FFFFF;
if (exp) {
exp = exp + 0x00800000;
res = (uf & 0x807FFFFF) | exp;
} else {
res = (uf & 0xFF800000) | (frac << 1);
}
return res;
}

使用运算符数:9