💻实验 1：Data Lab
实验附件
Computer Systems: A Programmer's Perspective——Lab Assignments：http://csapp.cs.cmu.edu/3e/labs.html
Github下载地址：https://github.com/Xuyan-cmd/CUC_CSAPP
Gitee下载地址：https://gitee.com/rockjames/CUC_CSAPP
实验简介
bitXor(x,y)
只使用 ~ 和 & 实现 ^
1
14
tmin()
返回最小补码
1
4
isTmax(x)
判断是否是补码最大值
1
10
allOddBits(x)
判断补码所有奇数位是否都是 1
2
12
negate(x)
不使用负号 - 实现 -x
2
5
isAsciiDigit(x)
判断 x 是否是 ASCII 码
3
15
conditional(x, y, z)
类似于 C 语言中的 x?y:z
3
16
isLessOrEqual(x,y)
x<=y
3
24
logicalNeg(x)
计算 !x 而不用 ! 运算符
4
12
howManyBits(x)
计算表达 x 所需的最少位数
4
90
floatScale2(uf)
计算 2.0*uf
4
30
floatFloat2Int(uf)
计算 (int) f
4
30
floatPower2(x)
计算 2.0x
4
30
我们只需要更改bits.c文件，里面有13道题（13个函数）
通过修改代码实现简单的逻辑函数、二进制补码和浮点函数，但必须使用 C 语言的一个高度受限的子集。例如，可能会要求仅用位级运算和直线代码（straightline code）来计算一个数的绝对值。学会理解C 语言数据类型的位级表示和数据操作的位级行为。
参考链接
实验注意事项
明确禁止：
使用任何控制结构，例如
if、do、while、for、switch等。定义或使用任何宏。
在此文件中定义任何附加函数。
调用任何函数。
使用任何其他操作，例如
&&、||、-或?：使用任何形式的铸造。
使用除 int 以外的任何数据类型。这意味着你
不能使用数组、结构或联合。
实验内容
BitXor(x,y)
只使用两种位运算实现异或操作。这个算是一个比较简单的问题了，难度系数1。学数电和离散二布尔代数的时候了解过。
//1
/*
* 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 2;
}g: 1 */int bitXor(int x, int y) { return 2;}解析：
这道题是手动实现异或操作。
已知对两个位进行异或操作，同0得0，同1得0，不同得1，所以，我们先求出x和y同为0的位：
(~x & ~y)x与y同为1的位：
(x & y)相同得0，所以要对上面的位进行取反，整个函数就一句话：
int bitXor(int x, int y) {
return ~(~x & ~y) & ~(x & y);
});}tmin()
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
return 2;
}解析：
二进制无符号数的值其实可以看作每一位的数（1或0）乘上2的x次方（从第0位开始）的总和，这个x就是第0位到第31位。
而补码的话就是从第0位加到第30位，最后一位则是负的1或者0乘以2的31次方，所以只要第31位是1，0-30位为0，即可得到补码最小值。
int tmin(void) {
return 1 << 31;
}isTmax(x)
//2
/*
* 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) {
return 2;
}解析：
这道题是判断这个数是否为最大的数（2^31 - 1），我习惯使用异或来判断是否相等。
首先求这个最大的数0x7FFFFFFF，可以通过
~(1 << 31)来得到这个数，与其本身异或，求逻辑非的值，即为结果：
int isTmax(int x) {
return !(~(1 << 31) ^ x);
}allOddBits(x)
/*
* 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) {
return 2;
}解析：
这道题是求一个数所有的奇数位是否为1，满足则返回1，否则为0。
Easy，先求出所有奇数位都为1，偶数位为0的数，8位则是0xAA，通过左移可以得到0xAAAAAAAA：
int val1 = 0xAA;
val1 = val1 + (val1 << 8) + (val1 << 16) + (val1 << 24);将x与0xAAAAAAAA进行位与运算，过滤掉所有偶数位的数据，得到所有奇数位的数据。
再将val1与进行位与运算后得到的值进行异或，一样的话会得到0，取逻辑非则为1，不一样的话会得到一个数，取逻辑非为0。
int allOddBits(int x) {
int m = 0xAA + (0xAA << 8);
int mask = m + (m << 16);
return !((x & mask) ^ mask);
}negate(x)
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return 2;
}解析：
这道题只是求负数，所有位取反加1即可。
int negate(int x) {
return ~x + 1;
}isAsciDigit(x)
/*
* 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) {
return 2;
}解析：
判断一个数是否是ASCII码里面的数字，这个有点难想，后来看到别人的思路瞬间豁然开朗。
首先取0x30的负数val1，此时如果把这个数与val1相加，则如果这个数大于等于0x30，则结果大于等于0，而小于0x30的话则结果小于0。已知负数符号位为1，0和正数符号位为0，因此可得到这个数是否大于等于0x30。
int val1 = ~0x30 + 1;类似的方法，取val2为0x80000000减去0x3a，此时val2符号位为1。将这个数与val2相加，如果这个数大于0x39，则结果会大于或等于0x80000000，即符号位为1，而如果小于0x39，结果会小于0x80000000，符号位为0，取反即可得到想要的结果。
int val2 = (1 << 31) + ~0x3a + 1;将两个结果都进行逻辑非运算，然后位与运算，即为返回值
int isAsciiDigit(int x) {
int val1 = ~0x30 + 1;
int val2 = (1 << 31) + ~0x3a + 1;
return (!((val1 + x) >> 31)) & (!((val2 + x) >> 31));
}conditional(x, y, z)
/*
* 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) {
return 2;
}解析：
这道题是实现 ：？运算符，首先，先把x取布尔值，然后取反加一，如果x布尔值为0，则所有位为0，如果布尔值为1，则所有位为1：
int val = ~(!!x) + 1;然后使用位或运算，左边放val & y，右边放~val & z，这样如果val为全1，则返回y的值，如果为全0，则返回z的值：
int conditional(int x, int y, int z) {
int val = ~(!!x) + 1;
return (val & y) | (~val & z);
}isLessOrEqual(x, y)
/*
* 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) {
return 2;
}解析：
这道题是实现<=运算符，要分情况讨论
1、符号位一样，判断x - y的符号位即可。
2、符号位不一样，x符号位为0则返回1，符号位为1则返回0。
取两个数符号位相加，0 + 0 = 0； 1 + 1 = 2；第一位都是0，如果两个数符号位相加后第一位为0，则符合相同：
int val1 = (x >> 31) + (y >> 31);求x - y的符号位，这里加逻辑非是为了结果统一：
int val2 = !((y + (~x) + 1) >> 31);用上一题位与运算类似的办法来进行结果的选择：
int isLessOrEqual(int x, int y) {
int val1 = (x >> 31) + (y >> 31);
int val2 = !((y + (~x) + 1) >> 31);
int val3 = x >> 31 & 1;
return (val1 & val3) | ((~val1) & val2);
}logicalNeg(x)
/*
* 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) {
return 2;
}解析：
这道题是实现逻辑非，一个数，取反加一，再与原来的数字进行位或运算，如果是0，那结果还是0，如果不是0，则符号位必为1。将结果右移31位，如果符号位为0，则结果为0，如果符号位为1，则结果为全1。
把上一个结果再加1，0 + 1为1，0xFFFFFFFF + 1 = 0，即为返回值。
int logicalNeg(int x) {
return ((x | (~x + 1)) >> 31) + 1;
}howManyBits(x)
/* 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) {
return 0;
}解析：
首先是0和-1两个特殊情况，都是一位，-1的二进制补码是全1，也就是说，取反之后跟0是一样的，只需要一个符号位就可以表示。而一般的数，取反之后跟取反之前都可以用一样的位数来表示，这道题的方法来自
因此，对传入的数x，如果是正数，就不用动，如果是负数，就取反。可以通过把x右移31位后的值与x进行异或运算，这样如果符号位为0，0和任何数异或不变，如果符号位为1，补码右移的规则是在右移之后的空位补上符号位，即如果符号位为1，则右移31位后的值为0xFFFFFFFF。x与0xFFFFFFFF异或的效果即为取反。
int op = x ^ (x >> 31);这里设3个变量，
如果x == 0，val1 = 1;
如果x == -1，val2 = 1;
如果x != 0 && x != -1，val3 = 0xFFFFFFFF;
然后就是0和-1之外的情况的操作，这里的方法很巧妙：
取op右移16位后的布尔值，这样可以判断高16位是否为0；
将刚刚得到的布尔值左移4位，存放在bit_16，如果布尔值为0，bit_16 = 0，如果布尔值为1，则bit_16 = 1；
将op右移bit_16位，如果op多于16位，则之后只剩下高16位，否则不变。
这时候这个数就只剩下16位要处理了，用同样的方法：
取op右移8位后的布尔值，这样可以判断高8位是否为0；
将刚刚得到的布尔值左移3位，存放在bit_8，如果布尔值为0，bit_8 = 0，如果布尔值为1，则bit_8 = 1；
将op右移bit_8位，如果op多于8位，则之后只剩下高8位，否则不变。
把下面的bit_16 , 16, 4 分别换成[bit_8, 8, 3]、[bit_4, 4, 2]、[bit_2, 2, 1]、[bit_1, 1, 0]，都运算一遍.
bit_16 = (!!(op >> 16)) << 4;
op = op >> bit_16;再把bit_xx的值相加，因为不为0，所以还有一位是不用判断必为1的，再有一个符号位为1，所以：
sum = 2 + bit_16 + bit_8 + bit_4 + bit_2 + bit_1;返回值为：
return (val1) | (val2) | (val3 & sum);完整代码：
int howManyBits(int x) {
int val1 = !(x ^ 0);
int val2 = !(x ^ (~0));
int val3 = ~(~(val1 | val2) + 1);
int bit_16, bit_8, bit_4, bit_2, bit_1;
int sum;
int op = x ^ (x >> 31);
bit_16 = (!!(op >> 16)) << 4;
op = op >> bit_16;
bit_8 = (!!(op >> 8)) << 3;
op = op >> bit_8;
bit_4 = (!!(op >> 4)) << 2;
op = op >> bit_4;
bit_2 = (!!(op >> 2)) << 1;
op = op >> bit_2;
bit_1 = (!!(op >> 1));
op = op >> bit_1;
sum = 2 + bit_16 + bit_8 + bit_4 + bit_2 + bit_1;
return val1 | val2 | (val3 & sum);
}floatScale2(uf)
//float
/*
* 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) {
return 2;
}解析：
这道题是求浮点数乘二，一般的浮点数乘二只要阶码加一即可，不过我们要考虑几种特殊情况：
0乘2
无穷大或者NaN乘2
非规格数乘2
题目对于浮点数的函数格式要求放宽了不少，可以使用选择，循环，并且常量值可以使用Int范围内的所有数。
首先对浮点数的各部分进行提取：
int exp = uf & 0x7f800000;
int frac = uf & 0x7fffff;判断是否为无穷大或者NaN：
if (exp == 0x7f800000)
return uf;判断是否为0或非规格数，非规格数乘2为左移1位：
else if (exp == 0)
frac = frac << 1;然后就是一般的情况：
else
exp = exp + 0x800000;最后就是把结果合并：
ret = (uf & 0x80000000) | exp | frac;值得一提的是，非规格数如果尾数最高位为1时，右移1位会使阶码最低位从0变为1，而这时候恰好就是正确的结果，并不需要额外的处理。这是因为乘2之后完成了进位，刚好规格数在小数点前有一个1，规格数和非规格数从而无缝衔接。
完整的函数：
unsigned floatScale2(unsigned uf) {
int ret;
int exp = uf & 0x7f800000;
int frac = uf & 0x7fffff;
if (exp == 0x7f800000)
return uf;
else if (exp == 0)
frac = frac << 1;
else
exp = exp + 0x800000;
ret = (uf & 0x80000000) | exp | frac;
return ret;
}floatFloat2Int(f)
/*
* 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) {
return 2;
}解析：
这道题是实现浮点型转整型，需要分情况讨论：
浮点数超过整形能表达的最大值
浮点数小于1
同上一题一样，先提取浮点数各部分出来：
int exp = 0xff & (uf >> 23);
int frac = 0x7fffff & uf;
int sign = !!(uf >> 31);按照题目要求，超过最大值返回0x80000000u：
if (exp > 127 + 30)
return 0x80000000u;小于1，返回0：
if (exp < 127)
return 0;正常情况，特别的，如果浮点数符号位为1，在得到浮点数的绝对值之后取反加一：
tmp = ((frac >> 23) + 1) << (exp - 127);
if (sign)
return (~tmp) + 1;
else
return tmp;完整函数：
int floatFloat2Int(unsigned uf) {
int exp = 0xff & (uf >> 23);
int frac = 0x7fffff & uf;
int sign = !!(uf >> 31);
int tmp;
if (exp > 127 + 30)
return 0x80000000u;
if (exp < 127)
return 0;
tmp = ((frac >> 23) + 1) << (exp - 127);
if (sign)
return (~tmp) + 1;
else
return tmp;
}floatPower2
/*
* 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) {
return 2;
}解析：
三种情况：
x小于-127，结果为0
x大于128，结果为无穷大（阶码全为1，指数为0）
结果为阶码 = x + 127（阶码的偏移量）
unsigned floatPower2(int x) {
if (x < -127) return 0;
if (x > 128) return 0xff << 23;
return (x + 127) << 23;
}Last updated