Data Lab[Updated 11/2/18]
11/2/18 新鲜出炉的 Data Lab，不同时期的 lab 内容会不一样。
肝了两天还是没有全部做出来，之前很以为很简单呢（
最近也终于买了 CS:APP3e 英文版，配合 CMU 的课程视频食用更佳。顺便可以练习英语听力和阅读，阅读已经可以流畅了，这种英文书基本看得懂，但是听力就不行（
解题的思路一般会写在注释里的。
bitXor
1
2
3
4
5
6
7
8
9
10
11
12
13
|
/*s
* bitXor - x^y using only ~ and &
* Example: bitXor(4, 5) = 1
* Legal ops: ~ &
* Max ops: 14
* Rating: 1
*/
int bitXor(int x, int y) {
// 德摩根定律
// a xor b = (~a | ~b) & (a | b)
// = ~(a & b) & ~(~a & ~b)
return ~(~x & ~y) & ~(x & y);
}
|
虽然这题比较简单，但我还是想了好久。主要是我把这个德摩根定律忘得差不多了，记得在离散数学里讲过。
利用的性质主要是：
- a ^ b = (~a | ~b) & (a | b)
- (~a | ~b) = ~(a & b)
tmin
1
2
3
4
5
6
7
8
9
10
|
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
// minimum tow's complement is 0x80000000
return 1 << 31;
}
|
最简单的一题，最小的有符号数是 0x80000000。
isTmax
1
2
3
4
5
6
7
8
9
10
11
|
/*
* 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) {
// tmax = 0x7fffffff
return !(x ^ 0x7fffffff);
}
|
我一开始是像上面这样写的，如果没有限定的话这样是对的。但是整数部分的要求比较严格：
1
2
|
Integer constants 0 through 255 (0xFF), inclusive. You are
not allowed to use big constants such as 0xffffffff.
|
而且这一题不能使用移位操作，就不能通过移位来得到 0x7fffffff。然后只能Google了。。。
这是我 Google 到的版本:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
int isTmax(int x) {
// creates i = x plus 1 then makes x = that number plus x.
// then flips the bits of x and bangs i, adds them and returns.
// this effectively checks if the number was tmax
// because if it was adding 1 would result in a leading 1.
// you flips the bits to get 1 and add either 0 or 1
// and return the opposite of that by banging x to get 1 for true or 0 for
// flase
int i = x + 1;
x = x + i;
x = ~x;
i = !i;
x = x + i;
return !x;
}
|
allOddBits
和上一题一样，我一开始也违反了这条规定：
1
2
|
Integer constants 0 through 255 (0xFF), inclusive. You are
not allowed to use big constants such as 0xffffffff.
|
幸运的是，这题可以用移位：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
/*
* 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) {
// x AND mask 0xAAAAAAAA(1010...1010), then XOR mask
int m = 0xAA;
m = (m << 8) | m;
m = (m << 8) | m;
m = (m << 8) | m;
m = (m << 8) | m;
return !((x & m) ^ m);
}
|
主要是利用了 0xAAAAAAAA 这个 mask，x 和 mask 相与来判断是否全部的奇数位都被置1。
negate
1
2
3
4
5
6
7
8
9
10
11
|
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
// two's complement equals ones' complement + 1
return (~x) + 1;
}
|
一个数取反加一，就是它的负数，利用了补码的性质。
isAsciiDigit
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
/*
* 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) {
// todo flow max ops
int _0 = x ^ 0x30;
int _1 = x ^ 0x31;
int _2 = x ^ 0x32;
int _3 = x ^ 0x33;
int _4 = x ^ 0x34;
int _5 = x ^ 0x35;
int _6 = x ^ 0x36;
int _7 = x ^ 0x37;
int _8 = x ^ 0x38;
int _9 = x ^ 0x39;
return !_0 | !_1 | !_2 | !_3 | !_4 | !_5 | !_6 | !_7 | !_8 | !_9;
}
|
这题我目前想到的解法就是这样，很明显超过了操作符个数的限制，而且看上去很蠢。就是判断这个数是否等于‘0’到‘9’中的一个。
conditional
1
2
3
4
5
6
7
|
/*
* conditional - same as x ? y : z
* Example: conditional(2,4,5) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
|
在 15213 - Recitation 3 - Datalab 中有关于这题的小提示：
1
2
3
4
5
6
7
8
9
|
//Find an algorithm for computing the expression (cond) ? t : //f, which equals t if cond is
//1 and f if cond is 0.
int conditional(int cond, int t, int f) {
/* Compute a mask that equals 0x00000000 or
0xFFFFFFFF depending on the value of cond */
int mask = ______________________________________;
/* Use the mask to toggle between returning t or returning f */
return __________________________________________;
}
|
当 x 取 0 时，返回 z，否则，返回 y。假设 x = 0 时，取 mask = 0xffffffff，否则，mask = 0x0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
int conditional(int x, int y, int z) {
// when x = 0, t1 is overflow, it's value is 0
int t1 = ~x + 1;
// when x = 0, t2 =0, else its MSB is 1
int t2 = x | t1;
// when x = 0, t3 = 0xffffffff, else t3's MSB is 0
int t3 = ~t2;
// arithmetical shift
// x = 0, mask = 0xffffffff, else mask = 0x0
int mask = t3 >> 31;
// use mask to toggle between y and z
// x = 0, return z, else return y
return (~mask & y) | (mask & z);
}
|
isLessOrEqual
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
|
/*
* 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) {
// Cases:
// 1. x == y
// 2. x, y has different sign, so the negative is less
// if just do x -y, it may overflow when x,y has different sign.
// 3. x - y < 0, when x,y has same sign
int mask = 0x1;
int equals = !(x ^ y);
int x_sign = (x >> 31) & mask;
int y_sign = (y >> 31) & mask;
// sign is diff and x_sign is 1
int diff_sign = x_sign ^ y_sign;
int case2 = diff_sign & x_sign;
int neg_y = (~y) + 1;
// use logical right shift, but casting is not allowed.
// int less = (unsigned)(x + neg_y) >> 31;
// less is MSB(sign bit): 0 -> x - y > 0, 1-> x - y < 0
int less = ((x + neg_y) >> 31) & mask;
return equals | case2 | (!diff_sign & less);
}
|
考虑返回 1 的 3 种情况：
- x == y
- x , y 不同号且 x 是负数
- x, y 同号，x - y < 0
为什么需要考虑 x, y 是否同号呢？
其实我一开始也只考虑了两种情况，即 x == y；x - y < 0。在进行测试的时候有如下输出：
1
2
|
ERROR: Test isLessOrEqual(-2147483648[0x80000000],2147483647[0x7fffffff]) failed...
...Gives 0[0x0]. Should be 1[0x1]
|
很明显 0x80000000 应该小于 0x7fffffff，但是却输出了 0。因为 0x80000000 + 0x80000001 发生了负溢出，产生的结果是一个大于 0 的数。所以 less会是 0。
logicalNeg
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
/*
* 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) {
// when x = 0, t1 is overflow, it's value is 0
int t1 = ~x + 1;
// when x = 0, t2 =0, else its MSB is 1
int t2 = x | t1;
// when x = 0, t3 = 0xffffffff, else t3's MSB is 0
int t3 = ~t2;
// logical shift
// return (unsigned)t3 >> 31;
// x = 0, mask = 0x1, else mask = 0x0
return (t3 >> 31) & 1;
}
|
和 conditional 那题类似，不过我开始使用的是 (unsigned)t3 >> 31;，转化为 unsigned 执行逻辑右移来直接获取 MSB。但是题目是不允许使用强制类型转换的，所以改成 (t3 >> 31) & 1。
逻辑右移和算术右移
在调试 logicalNeg 这题时，发生了一个小插曲。我想知道 C 在什么时候会用逻辑右移，什么时候会用算术右移。
1
2
3
4
5
6
7
8
9
10
|
int logicalNeg(int x) {
// when x = 0, t1 is overflow, it's value is 0
int t1 = ~x + 1;
// when x = 0, t2 =0, else its MSB is 1
int t2 = x | t1;
// when x = 0, t3 = 0xffffffff, else t3's MSB is 0
int t3 = ~t2;
// 怎么使用 logical shift
return t3 >> 31;
}
|
当 x 是 0时，t3 = 0xffffffff。此时是要使用逻辑右移就可以变成 0x00000001。
再看下面的测试代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
int main(int argc, char const *argv[]) {
int neg_one = 0xffffffff;
int shift = neg_one >> 31;
int shift_inline = 0xffffffff >> 31;
printf("------right shift-----\n");
printf("0xffffffff >> 31 = %d", shift);
printf(" = \n");
show_bytes((byte_pointer)&shift, sizeof(int));
printf("------right shift inline-----\n");
printf("0xffffffff >> 31 = %d", shift_inline);
printf(" = \n");
show_bytes((byte_pointer)&shift_inline, sizeof(int));
return 0;
}
|
结果很奇怪，怎么两个一样的式子有不同的结果呢？第一个使用了算术右移，第二个使用了逻辑右移。唯一的区别就是 0xffffffff 所在的位置，第一个是被保存在 int 中的，第二个式子，则是包含在式子里面int shift_inline = 0xffffffff >> 31;。
1
2
3
4
5
6
7
|
▶ ./"right_shift"
------right shift-----
0xffffffff >> 31 = -1 =
ff ff ff ff
------right shift inline-----
0xffffffff >> 31 = 1 =
01 00 00 00
|
其实只要明白一点，就会茅塞顿开。（还是因为我没仔细看书吧），CSAPP上有这样一段话：
The c standards do not precisely define which type of right shift should be used with signed numbers-either arithmetic or logical shifts may be used. This unfortunately means that any code assuming one form or the other will potentially encounter portability problems.In practice,however, almost all compiler/machine combinations use arithmetic right shifts for signed data, and many programmers assume this to be the case. For unsigned data, on the other hand, right shifts must be logical.
可以看做，C 中无符号数采用逻辑右移，而有符号数采用算术右移。
那么 int shift_inline = 0xffffffff >> 31; 这个式子会采用逻辑右移，也说明 C 中 0x 开头表示的16进制数默认被当做 unsigned 。
而怎么使用逻辑右移的答案已经显而易见，return (unsigned)t3 >> 31;。
CTRL + KEY
今天(2018/11/27)，在跟着这个从0 开始写编辑器的教程敲代码的时候，发现几个有意思的位运算，同时不得不感叹ASCII表设计的很巧妙了。
CTRL-C 大家都用过，大部分情况是复制黏贴，或者是终止一个进程。它在 ASCII 表中的数值是 3，为什么是 3 呢？我从来没想过。
因为就是这样设计的，C 是字母表中的第3个字母，所以可能为了方便？CTRL-C 就是 3。
想在编辑器中捕捉CTRL-C首先要关闭CTRL-C的默认功能：发出SIGINT 信号终止程序。之后你可以写类似这样的代码：if(c == 3)
但是为了使代码更容易理解，使用这个宏来表示CTRL-KEY：
1
|
#define CTRL_KEY(k) ((k)&0x1f)
|
这样你便可以用if(c == CTRL_KEY('C')) 来表示 CTRL-C了。
CTRL 键和 26 个字母组合分别对应 ASCII 表中的 1～26。最少需要用 5 位二进制表示。所以只需要用0x1f(0001 1111) 这个 mask 取字母的低五位便可以把字母转化成CTRL+KEY的组合。
这个式子成立的前提还有一个，就是字母的低位必须是从1开始的，而 ASCII 表设计的恰恰满足这个条件：A：0x41，a：0x61。
Upercase & Lowercase
利用这个的性质，还可以用位运算完成大小写的转换。只需要变换第五位二进制数（大写字母和小写字母差32.）
1
2
3
4
|
unsigned char toggle_case(unsigned char a) {
int mask = 0x20;
return a ^ mask;
}
|