CSAPP Data Lab

Data Lab 的题1,第一眼觉得不难,仔细一看发现限制非常严格,比如只允许部分位运算符等,难度一下子就上去了,所以花了不少时间。

dlc 是 64 位 Linux 程序,使用 ./dlc bits.c 来检查是否符合限制条件。但 Makefile 里却指定了 -m32,可能是考虑到 C 标准只规定 int 至少为 16 位,一些环境可能会生成非 32 位的 int

Debian 系 64 位 Linux 发行版可以安装:

1
$ sudo apt install build-essential gcc-multilib g++-multilib

后两个库用于在 64 位环境下编译 32 位程序。

编译并运行测试程序:

1
$ make clean && make btest && ./btest

bitXor

~& 来实现 ^

bits.cview raw
1
2
3
4
5
6
7
8
9
10
/* 
* bitXor - x^y using only ~ and &
* Example: bitXor(4, 5) = 1
* Legal ops: ~ &
* Max ops: 14
* Rating: 1
*/
int bitXor(int x, int y) {
return ~(~(x & ~y) & ~(~x & y));
}

根据

\[A \oplus{B} = A \cdot \overline{B} + \overline{A} \cdot B\]

来实现 ^,再根据

\[A + B = \overline{\overline{A + B}} = \overline{\overline{A} \cdot \overline{B}}\]

来实现 |

tmin

求补码最小值,送分题:

bits.cview raw
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;
}

isTmax

判断是否为 int 最大值 0x7fffffff,只允许使用 ! ~ & ^ | +

bits.cview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
/*
* isTmax - returns 1 if x is the maximum, two's complement number,
* and 0 otherwise
* Legal ops: ! ~ & ^ | +
* Max ops: 10
* Rating: 1
*/
int isTmax(int x) {
// If x is 0x7fffffff or 0xffffffff, then i is 1, else 0
int i = !(~x ^ (x + 1));
// If x == 0xffffffff, then !~x is 1, else 0
return i & !!~x;
}

先将问题转化为判断是否为最大值的取反 0x80000000

利用补码的特性,int 类型可以用取反加一来实现求相反数,而只有两个数满足与自身的相反数相等,即 00x80000000,其中后者是因为溢出。

再利用逻辑非 ! 排除 0 即可。

allOddBits

判断是否所有奇数位(最低位为 0 位)都为 1

bits.cview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 
* allOddBits - return 1 if all odd-numbered bits in word set to 1
* where bits are numbered from 0 (least significant) to 31 (most significant)
* Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 12
* Rating: 2
*/
int allOddBits(int x) {
int mask = 0xaa;
mask = (mask << 8) | mask;
mask = (mask << 16) | mask;
return !((x & mask) ^ mask);
}

只允许使用 00xff 之间的常数,故先用移位求 0xaaaaaaaa,再用 ^ 实现 ==

negate

求相反数,送分题:

bits.cview raw
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;
}

isAsciiDigit

判断是否为 '0''9' 之间的 ASCII 码:

bits.cview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 
* isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
* Example: isAsciiDigit(0x35) = 1.
* isAsciiDigit(0x3a) = 0.
* isAsciiDigit(0x05) = 0.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 3
*/
int isAsciiDigit(int x) {
int i = 0x30, result, mask = 1 << 31;
// x - 0x30 >= 0
result = !((x + ~i + 1) & mask);
i = 0x39;
// 0x39 - x >= 0
result = result & !((i + ~x + 1) & mask);
return result;
}

用求相反数和 + 来实现 -,再取符号位判断其正负。

中间可能有溢出的问题,当 x - 0x30 >= 0 时,可能 x 是一个很小的负数,负负得正产生溢出;当 0x39 - x >= 0 时,不会产生溢出,从而把前一种溢出的情况排除。

conditional

实现三元运算符 a ? b : c

bits.cview raw
1
2
3
4
5
6
7
8
9
10
11
12
/* 
* conditional - same as x ? y : z
* Example: conditional(2,4,5) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
int conditional(int x, int y, int z) {
// x = 0xffffffff or 0
x = ~!!x + 1;
return (y & x) | (z & ~x);
}

将非零数转换为掩码 0xffffffff,零转换为掩码 0

isLessOrEqual

实现 <=

bits.cview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
/* 
* 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 mask = 1 << 31, x_sign = !!(x & mask), y_sign = !!(y & mask), same_sign, le;
same_sign = !(x_sign ^ y_sign);
le = !((~x + 1 + y) & mask);
return (x_sign & !y_sign) | (same_sign & le);
}

问题转化为判断 -x + y 正负。

考虑溢出的问题,取 xy 的符号位,不同号时直接判断,若同号再判断 -x + y 正负。

logicalNeg

实现逻辑非 !

bits.cview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 
* logicalNeg - implement the ! operator, using all of
* the legal operators except !
* Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int logicalNeg(int x) {
// x = x | (x >> 1);
// x = x | (x >> 2);
// x = x | (x >> 4);
// x = x | (x >> 8);
// x = x | (x >> 16);
// return ~x & 1;

x = (x | (~x + 1)) >> 31;
return ~x & 1;
}

第一反应是将首个 1 之后的位全部置 1,若原值非零,则最低位为 1,否则为 0,然后将最低位直接取反即可。

后来发现了一种更简便的方法2,除 00x80000000 外,一个数必定与其相反数异号,若将 x-x 符号异或,则包括 0x80000000 在内 ,所有非零数异或结果必定为 1

howManyBits

求补码表示的最少位数:

bits.cview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* howManyBits - return the minimum number of bits required to represent x in
* two's complement
* Examples: howManyBits(12) = 5
* howManyBits(298) = 10
* howManyBits(-5) = 4
* howManyBits(0) = 1
* howManyBits(-1) = 1
* howManyBits(0x80000000) = 32
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 90
* Rating: 4
*/
int howManyBits(int x) {
int n = 0;
x = x ^ (x >> 31);
n = n + ((!!(x >> (n + 16))) << 4);
n = n + ((!!(x >> (n + 8))) << 3);
n = n + ((!!(x >> (n + 4))) << 2);
n = n + ((!!(x >> (n + 2))) << 1);
n = n + ((!!(x >> (n + 1))));
n = n + (x >> n);
return n + 1;
}

个人认为是最难的一题,参考了网上的答案3,并对其作了改进。

如何确定最少位数

对于非负数而言,开头连续的 0 可以去掉,只需保留其中最后一个 0 作为符号位即可(否则就会被当成负数了)。例如,0001...01... 表示的是相等值。

对于负数而言,同样从符号位开始,开头连续的 1 只需保留最后一个即可。例如,1110...10... 表示的是相等值。

将负数的情况转化为非负数的情况

x = x ^ (x >> 31) 的作用就是,若 x 为非负,则保持不变,若为负数,则取反。这样无论 x 符号,都可以按照非负数的情况来求解。

求最高位的 1 到最低位的长度,最终结果就是长度 + 1

这个步骤需要一些技巧。

例如,01** **** **** **** **** **** **** **** 的最高位 1 到最低位是 31 位,最终结果就是 32。

观察 31 = 16 + 8 + 4 + 2 + 1,与 x 右移试零的过程一致:首先取 x 最高 16 位,若非零,说明需要 16 位以上的位数,此时 n 计数 + 16,并将低 16 位去掉。接着尝试将低 8 位去掉,以此类推,直到 x 只剩一位。手动模拟一下会更容易理解。

上个步骤已经排除了负数的情况,所以无需担心算数右移高位产生 1 的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
01** **** **** **** **** **** **** ****

n = 16

01** **** **** ****

n = 16 + 8

01** ****

n = 16 + 8 + 4

01**

n = 16 + 8 + 4 + 2

01

n = 16 + 8 + 4 + 2 + 0

01

n = 16 + 8 + 4 + 2 + 0 + 1

floatScale2

书上的习题,求 \(2x\)

bits.cview raw
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
/* 
* floatScale2 - 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 floatScale2(unsigned uf) {
unsigned sign = uf & 0x80000000, exp = uf & 0x7f800000, frac = uf & 0x007fffff;
// 0 or denorm
if (exp == 0)
return sign | uf << 1;
// inf or NaN
if (exp == 0x7f800000)
return uf;
// norm
exp += 0x00800000;
// large number becomes inf
if (exp == 0x7f800000)
frac = 0;
return sign | exp | frac;
}

浮点数题目的限制比前面宽松很多,虽然构造复杂一点,只要按照定义求解即可。

floatFloat2Int

书上的习题,float 转换为 int

bits.cview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* 
* floatFloat2Int - Return bit-level equivalent of expression (int) f
* for floating point argument f.
* Argument is passed as unsigned int, but
* it is to be interpreted as the bit-level representation of a
* single-precision floating point value.
* Anything out of range (including NaN and infinity) should return
* 0x80000000u.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 4
*/
int floatFloat2Int(unsigned uf) {
int sign = uf >> 31, exp = ((uf >> 23) & 0xff) - 127, frac = (uf & 0x007fffff) | 0x00800000, value = 0;
if (exp < 0)
return 0;
if (exp > 30)
return 0x80000000;
if (exp < 23)
value = frac >> (23 - exp);
else if (exp > 23)
value = frac << (exp - 23);
return sign ? -value : value;
}

float 范围比 int 更广,但精度(有效数字)更低,注意溢出的情况。

floatPower2

书上的习题,求 \(2^x\)

bits.cview raw
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
/* 
* floatPower2 - Return bit-level equivalent of the expression 2.0^x
* (2.0 raised to the power x) for any 32-bit integer x.
*
* The unsigned value that is returned should have the identical bit
* representation as the single-precision floating-point number 2.0^x.
* If the result is too small to be represented as a denorm, return
* 0. If too large, return +INF.
*
* Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while
* Max ops: 30
* Rating: 4
*/
unsigned floatPower2(int x) {
if (x < -149)
return 0;
// denorm
if (x < -126)
return 1 << (149 + x);
// norm
if (x < 128)
return (x + 127) << 23;
// inf
return 0x7f800000;
}

参考资料


  1. CS:APP3e, Bryant and O'Hallaron↩︎

  2. Introduction to CSAPP(八):Datalab - 知乎↩︎

  3. CSAPP DataLab 题解 | Claude's Blog↩︎