数据实验室
《深入理解计算机系统》书籍的配套作业。光看书实在是枯燥到有点看不下去，打算做一下MIT这门课程的实验，反正资源是公开的感觉也比较有趣。 实验资源
开始之前测试环境就遇到了报错：
错误: fatal error: bits/libc-header-start.h: No such file or directory #include
环境： Ubuntu （实验全部需要在32位环境下编译）
所以先确保可以在64位的Ubuntu上编译32位程序。
确认主机为64位架构的内核，应该输出为adm64，执行：
dpkg --print-architecture确认打开了多架构支持功能，应该输出为i386，执行：
dpkg --print-foreign-architectures安装gcc multilab，执行：
sudo apt-get install gcc-multilib g++-multilib bitAnd
题目描述：最简单的一道题作为开始，，只能用或和否两种运算操作实现位的与运算。
/* 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);
}验证答案使用运算操作符是否符合要求：
./dlc -e bits.c验证答案是否正确：
make btest
./btest -f bitAndgetByte
题目描述：32位16进制表示，获取指定的有效位数。
/*
* 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;
}MSB：最高有效位（最左侧） LSB：最低有效位
掩码运算：x&0xff生成一个由x的最低有效字节组成的值，其他字节被置为0。
logicalShift
题目描述：实现逻辑右移
/*
* 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) {
int mask = ~(((1 << 31) >> n) << 1); //nx0...111111
return (x >> n) & mask;
}对于有符号的int类型x，c语言默认执行>>为算数右移，所以这里构造一个屏蔽码来屏蔽右移后的非扩展位。
bitCount
题目描述：计算出32位二进制数中高位1的个数
/*
* bitCount - returns count of number of 1's in word
* Examples: bitCount(5) = 2, bitCount(7) = 3
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 40
* Rating: 4
*/
int bitCount(int x) {
int tmp = 0x11 | (0x11 << 8);
int mask = tmp | (tmp << 16); // form a mask 0x11111111
// divide into 8 groups(8 bytes)
int ans = mask & x;
ans += mask & (x >> 1);
ans += mask & (x >> 2);
ans += mask & (x >> 3);
// sum the values of every bytes in ans
ans += ans >> 16;
mask = 0xf | (0xf << 8); // form a mask 0x0f0f
// divide into 2 groups
ans = (ans & mask) + ((ans >> 4) & mask);
return (ans + (ans >> 8)) & 0x3f;
}这题好难，刚看到题目一点思路的都没有，不得已只能靠Google了。
解决方法大概就是通过构造常数，这里分别是0x11111111，将32位分成8个四位计算出每四位中高位的个数得到ans。再由ans>>16，将前16位和后16位表示的有效计算结果相加，此时后16位以4位为一组表示的数的总和就是高位的总个数。继续构造常数0x0f0f，将后16位中15~12位与11~8位相加，7~4位与3~0位相加，此时后16位的11~8位与3~0位所表示的数的总和为高位总个数，其余位置为0。最后将11~8位与3~0位相加，并用掩码0x3f（由于最高位最多是32位，此时保留最低有效位6位）将其余位置置0。
bang
题目描述：不使用！符号，实现！运算…
/*
* bang - Compute !x without using !
* Examples: bang(3) = 0, bang(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int bang(int x) {
/*
x=(x>>16)|x;
x=(x>>8)|x;
x=(x>>4)|x;
x=(x>>2)|x;
x=(x>>1)|x;
return ~x&0x1;
*/
int temp = ~x+1;
temp = temp|x;
temp = temp>>31;
return ~temp&0x1;
}第一种方式：通过移位和或运算，将高位一步一步折叠至最低有效位，最后取反并使用掩码只保留最低有效位。（掩码也太强了，几乎每题都有用到）
第二种方式：通过最高位来判断；因为只需要判断x是否为0，当x为0时，取反加一则会省略进位得到0x0（最高位为0），其余情况若x为负数则最高位为0，否则为1；通过temp|x来判断x是否为负数，若x为负数最高位重新置为1；此时即可通过最高位来判断x是否为0。
tmin
题目描述：求最小补码
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
return 1<<31;
}最开始还没太看懂这题什么意思…two’s complement的意思的二进制补码，我以为是2的补码…
tbc.
