今天开坑写一个系列，记录自己做11个CSAPP配套Lab的过程。
本帖为第一个实验，Data Lab。
实验内容下载地址：http://csapp.cs.cmu.edu/3e/labs.html
目录：
- Data Lab
- Bomb Lab
- Attack Lab
- Buffer Lab (IA32)
- Architecture Lab
- Architecture Lab (Y86)
- Cache Lab
- Performance Lab
- Shell Lab
- Malloc Lab
- Proxy Lab
1.实验文件
实验文件解压后 有一个datalab-handout文件夹，里面有很多c文件，我们只需要在 bits.c里面编写程序，然后运行评测程序即可。
2.使用方法
bits.c文件里面有许多空函数，我们的工作就是根据函数的描述把空函数补充完整。
补充完整后，进行编译，使用make命令即可，make编译无错误后，运行btest程序./btest即可进行评测。
只测试单个函数：
./btest -f [函数名]
指定参数
./btest -f [函数名] -1 [参数1] -2 [参数2] -3……
输出调试
可以直接在bits.c文件里面调用printf方法输出调试信息，不需要包含stdio.h头文件。
3.实验内容：
//1
/*
* bitXor - x^y using only ~ and &
* Example: bitXor(4, 5) = 1
* Legal ops: ~ &
* Max ops: 14
* Rating: 1
* bit异或
* 要求只用～和&完成异或操作
* 思路:第一题比较简单，任何逻辑操作都可以用～和&表达，异或也是，
* 去查一下亦或的等价表达式，用摩根公式简化一下即可
*/
int bitXor(int x, int y) {
int a = ~(~x & y);
int b = ~( x & ~y);
int c = ~( a & b);
return c;
}
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
* 返回补码表达的最小值
* 根据补码的知识，补码的最小值就是1000000……000B
*/
int tmin(void) {
return 1<<31;
}
//2
/*
* isTmax - returns 1 if x is the maximum, two's complement number,
* and 0 otherwise
* Legal ops: ! ~ & ^ | +
* Max ops: 10
* Rating: 1
* 检验参数x是否是补码最大值
* 思路，补码最大值是0111……1111 用~(1<<31))得到0111……111 然后和x进行一下亦或操作即可，如果完全一直则得0，取反为1
*/
int isTmax(int x) {
return !(x^(~(1<<31)));
}
/*
* 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 nX = ~x;
return !( (nX&0xAA) | (nX&(0xAA<<8)) | (nX&(0xAA<<16)) | (nX&(0xAA<<24)));
}
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return (~x)+1;
}
//3
/*
* 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 a = !(!(x>>8));//验证高24位是否全为0(符合要求),
int b = !(!(0x30^(x&0xF0)));
int c1 = (0x08&x)>>3;
int c2 = (0x04&x)>>2;
int c3 = (0x02&x)>>1;
int c = (c1 & c2) | (c1 & c3);//如果是0表示 低四位符合要求
// printf("x:0x%x a:0x%x b:0x%x c:0x%x c1:0x%x c2:0x%x c3:0x%x\n",x,a,b,c,c1,c2,c3);
return !(a | b | c);
}
/*
* 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) {
int a = ((!(!x))<<31)>>31;
return (y&a) | (z&~a);
}
/*
* 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 x_sign = x>>31&1;
int y_sign = y>>31&1;
int a = x_sign & (!y_sign);
int b = !(x_sign^y_sign);
int c = b & ((x+~y)>>31 & 1);
return a | c;
}
//4
/*
* 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) {
int x_sign = (x>>31) & 1;
int myx = x&(~(1<<31));
int a = (myx+~0)>>31;
return (a & ((~x_sign)&1));
}
/* 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 b16,b8,b4,b2,b1,b0;
int sign=x>>31;
x = (sign&~x)|(~sign&x);//如果x为正则不变，否则按位取反（这样好找最高位为1的，原来是最高位为0的，这样也将符号位去掉了）
// 不断缩小范围
b16 = !!(x>>16)<<4;//高十六位是否有1
x = x>>b16;//如果有（至少需要16位），则将原数右移16位
b8 = !!(x>>8)<<3;//剩余位高8位是否有1
x = x>>b8;//如果有（至少需要16+8=24位），则右移8位
b4 = !!(x>>4)<<2;//同理
x = x>>b4;
b2 = !!(x>>2)<<1;
x = x>>b2;
b1 = !!(x>>1);
x = x>>b1;
b0 = x;
return b16+b8+b4+b2+b1+b0+1;//+1表示加上符号位
}