CSAPP_DATALAB | luo's Blog

1 bitXor

题目：

目标：实现 x ^ y.
限制：只能使用操作符～，&
最大操作次数： 14
难度：1

解法1：观察异或运算的数字逻辑电路真值表

X	Y	Z
0	0	0
0	1	1
1	0	1
1	1	0

易得：

$Z=\overline{X}Y+X\overline{Y}$

因为不能使用+(或)符号，很容易想到德摩根定律

$\overline{X+Y}=\overline{X}\overline{Y}$

可以看到，用非运算和与运算可以解决或运算,转换得：

$Z=\overline{\overline{\overline{X}Y+X\overline{Y}}}=\overline{(\overline{\overline{X}Y})(\overline{X\overline{Y})}}$

解法2：用门电路实现(其实应该和解法1一样，只是从门电路的逻辑上去理解)

我们知道，一个异或门可以由与门，或门和非门实现，如图：

又因为或门规定不能使用，根据德摩根定律，可以用与门和非门实现或门，实现如图：

所以根据解法可以写出代码：

int bitXor(int x, int y) {
  return ~(~x&~y)&~(x&y);//	       解法2
  // return ~(~(~x&y)&~(x&~y));    解法1
}

2. tmin

题目：

目标：返回最小补码数，即 0x80000000.
限制：只能使用操作符！~ & ^ | + <<>>
最大操作次数： 4
难度：1

最小补码数，32位机器当然就是0x80000000，有符号数补码表示法，最高位为1时负权值，低位全为正权值
1
2
3
4
int tmin(void)
{
return 1 << 31;
}
补码可以用下图2-13左右箭头理解，最终值为左右箭头(各个位权值)相互抵消后的值

3. isTmax

题目：
- 目标：判断 x 是否是 Tmax，如果是，返回 1，否则返回 0。
- 限制：只能使用操作符！~ & ^ | +
- 最大操作次数： 10
- 难度：2
解题思路：首先是先要知道Tmax是什么值，第二题提到过，有符号数补码表示法最高位为1时，权值为负值，最终结果也会为负值，低位权值始终为正值，所以Tmax就是最高位(符号位)为0，其余各位全部为1，也就是0x7fff ffff，所以问题就是转化为如果判断给定的x为0xffff ffff。因为不允许用if等判断语句，所以自然而然思路就是要找特殊值0，如何去构造特殊值0，可以通过直接构造全0，或构造全1，全1取反就得到全0了嘛。

$0x7fff ffff +1=0x8000 0000$

$0x7fff ffff+0x80000000=0xffffffff$

全1出现，似乎已经可以写出代码了，如下：

int isTmax(int x) {
  int x_addone=x+1;  //加1得到0x80000000
  x=x+x_addone;  //相加得到0xffffffff
  x=~x;     //取反得到 0x00000000
  return !x;  //满足条件，返回1
}

提交后报错了，原因是0xfffffff也通过了我的代码测试，返回了1，分析

$0xffffffff+1=0x00000000$

$0xffffffff+0x00000000=0xffffffff$

得到结果也是全1，最终返回1，所以需要进行一个特判。

设置一个flag，当x为0xffffffff,flag设置为0x0，否则设置为0x1,最终成功代码为

int isTmax(int x) {
  int x_addone=x+1;  //加1得到0x80000000
  int flag=!(!x_addone); //x为0xffffffff时，x_addone为全0，flag设置为0x0，否则设置为0x1
  x=x+x_addone;  //相加得到0xffffffff
  x=~x;     //取反得到 0x00000000
  return flag&(!x);  //满足条件，返回1  注意(!x是0x0或者0x1,只有一位有效)
}

4. allOddBits

题目：

目标：如果 x 的二进位的所有奇数位全为1，则返回 1，否则返回 0。 注：二进制最低位是第 0 位。
例子：allOddBits (0xFFFFFFFD) = 0, allOddBits (0xAAAAAAAA) = 1
限制：只能使用操作符！~ & ^ | + << >>
最大操作次数： 12

难度：2

解题思路：判断x的二进制的所有奇数位全为1，其实就是判断该数是否为0xAAAAAAAA或0xffffffff。代码实现：

int allOddBits(int x) {
  x=x&0xAAAAAAAA;          //当且仅当x为0xAAAAAAAA或0xffffffff，x&0xAAAAAAAA的结果为0xAAAAAAAA 
  return !(x^0xAAAAAAAA); //上一步结果为0xAAAAAAAA,返回1，否者返回0
}

5. negate

题目：

目标：返回 -x
限制：只能使用操作符！~ & ^ | + <<>>
最大操作次数：5
难度：2

直接解就可以了 -x=~x+1

证明一下这个式子：

我们有(-x)+x=0，两边同时加**_{x**,，有（-x)+x+(}x)=0+(~x) 又x+(~x)为全1(0xffffffff)，也就是-1，所以有

(-x)-1=(~x)，把1移到右边，等式得证。

1
2
3

int negate(int x) {
  return (~x)+1;
}

6. isAsciiDigit

题目：

目标： return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters ‘0’ to ‘9’)
例子：
- isAsciiDigit(0x35) = 1.
- isAsciiDigit(0x3a) = 0.
- isAsciiDigit(0x05) = 0.
限制：只能使用操作符！~ & ^ | + <<>>
最大操作次数：15

难度：3

解题思路:就是简单判断x是否在区间内，没有if语句，还是跟前面那个想法，构造出0或1。想法也很简单，比较大小可以用减法，再观察差是正负即可。代码如下：

int isAsciiDigit(int x) {
  int neg_Num_zero=~(0x30)+1;
  int neg_Num_nine=~(0x39)+1;
  int judge1=!(((x+neg_Num_zero)>>31)&1); //x>=0x30 judge1 is true
  int judge2=(((x+neg_Num_nine)>>31)&1);   //x<0x39 judge2 is true
  int judge3=!(x^(0x39); // x=0x39  judge3 is ture;
  return judge1& (judge2|judge3);
}

7. conditional

题目：

目标：实现三目运算符 same as x ? y : z
限制：只能使用操作符！~ & ^ | + << >>
最大操作次数：16
难度：3

解法：实现三目运算符，根据X条件选择Y或Z，可以巧妙运用数电的思想(类似于一个选择器)X=1时，选择Y，X等于0时，选择Z的值

$RESULT=XY+\overline{X}Z$

代码实现：

int conditional(int x, int y, int z) {
  int flag=!(!x);  //x等于0时不做转化，x为非0时，转化为1
  return ((~(flag-1)&y) | (flag-1)&z); //flag为1时，即要选择Y，所以~（flag-1)变为全1，&上y后仍然是y的值
}

8. isLessOrEqual

题目：

目标：如果 x<=y ，则返回 1，否则返回 0.
限制：只能使用操作符！~ & ^ | + <<>>
最大操作次数：24
难度：3

解题思路：同样使用减法实现判断小于等于号 y-x>=0

int isLessOrEqual(int x, int y) {
  int neg_x=~x+1;  //-x的值
  int judge1=!(((y+neg_x))>>31)&(0x1);  //x,y符号相同的情况，根据相减的符号位判断是否是<= 是<=则judge1=1
  int judge2=(x>>31)^(y>>31);  //x,y符号不相同，直接判断，judge2=0时，符号位相同，为1时，符号位不同
  int flag=~(~judge2+1); //flag，与上一题相同，相当于一个选择器，当judge2=0时，符号位相同，flag为全一，此时选择的是judge1的结果(即要根据相减的符号位是0或1进行判断) 当judge2=1时，flag为全0，~flag为全1，此时选择判断的依据为(x>>31)&0x1，即判断x的符号位
  return (flag&judge1) | (~flag&((x>>31)&0x1));
}

9. logicalNeg

题目：

目标：实现！操作
例子： logicalNeg (3) = 0, logicalNeg (0) = 1
限制：只能使用操作符～& ^ | + <<>>
最大操作次数：12
难度：4

本题要实现的是!操作，道理很简单就是0返回1，非0返回0

刚拿到这道题，有点懵，想了很久没有思路，网上借鉴了大牛的思路，列真值表判断情况

X	X符号位	X+0xffffffff 符号位
0	`0`	`1`
正数	0	0
负数	1	1 or 0

由表可知，只有X=0时，X符号位与X+0xffffffff符号位的组合为0 1 此时返回1，其余情况均返回0，可以写出代码：

int logicalNeg(int x) {
  int k=0xffffffff;
  return (~(x>>31)& 0x1)&(((k+x)>>31)&0x1);
}

10. howManyBits

题目：

目标：返回表示一个数（补码形式）所需要的最小 bit 数。
例子：
- howManyBits(12) = 5
- howManyBits(298) = 10
- howManyBits(-5) = 4
- howManyBits(0) = 1
- howManyBits(-1) = 1
- howManyBits(0x80000000) = 32
限制：只能使用操作符！~ & ^ | + <<>>
最大操作次数： 90
难度：4

emmmmmm，真不会做，看了别人的思路，觉得记录下来也有学习的意义 大概思路是：

首先正数的话，就是要从高位到地位找第一个值为1的位，此时所需要的bit数为该bit位的位置+1，因为还需要一个符号位。

对于负数，负数需要找的是从高位到地位首个值为0的bit位，所以“对于负数，我们可以用对待正数的算法去处理”，将负数取反即可。

接下来的处理方法，就是如何确实找到的首个位是第几个比特位，换句话说，也就是该比特位后面还有多少比特位，为处理方便，可以将后面的比特位全部置为1。再利用掩码+移位的方法确实后面有多少个1，也就是有多少个位。具体代码：

int howManyBits(int x) {
  int re_x=~x;//取反
  int neg_one=~0x1+1;
  int flag=!(x>>31);
  x=(~(flag+neg_one)&x) | ((flag+neg_one)&re_x);  //同样是类似一个选择器，保证x为正值
  x=x | x>>1;
  x=x | x>>2;
  x=x | x>>4;
  x=x | x>>8;
  x=x | x>>16;   //将32位最高位1后的所有位全部填充为1
  int sum=0;
  int one=0x1;
  sum+=x & one;
  sum+=(x>>1)& one;
  sum+=(x>>2)& one;
  sum+=(x>>3)& one;
  sum+=(x>>4)& one;
  sum+=(x>>5)& one;
  sum+=(x>>6)& one;
  sum+=(x>>7)& one;
  sum+=(x>>8)& one;
  sum+=(x>>9)& one;
  sum+=(x>>10)& one;
  sum+=(x>>11)& one;
  sum+=(x>>12)& one;
  sum+=(x>>13)& one;
  sum+=(x>>14)& one;
  sum+=(x>>15)& one;
  sum+=(x>>16)& one;
  sum+=(x>>17)& one;
  sum+=(x>>18)& one;
  sum+=(x>>19)& one;
  sum+=(x>>20)& one;
  sum+=(x>>21)& one;
  sum+=(x>>22)& one;
  sum+=(x>>23)& one;
  sum+=(x>>24)& one;
  sum+=(x>>25)& one;
  sum+=(x>>26)& one;
  sum+=(x>>27)& one;
  sum+=(x>>28)& one;
  sum+=(x>>29)& one;
  sum+=(x>>30)& one;
  sum+=(x>>31)& one;   //暴力求解，每一位都与掩码相与，得到1的个数
  return sum+1; //+1位 +的是符号位
}

总结：整数部分的实验就到这里为止了，这是我第一次做CSAPP的实验，有好一些题都得看了别人的题解才会做，觉得设计的解法很巧妙，学习到了还可以运用数电的思想去解决逻辑上的问题，后知后觉理解了其实逻辑上的硬件实现其实本身就是从最简单门电路的设计开始的。学习到了学习到了！也学习到了一些规律，特别是

$RESULT=XY+\overline{X}Z$

这条公式背后蕴含的根据X的值选择Y和Z其1的思想。

还有比如 -x=~x+1 ，32位的最大值0x7fffffff +1 就变成了最小值0x8000000,将最大最小相加又变成了-1(0xffffffff)等一些位运算规律。

慢慢填坑吧，就到这~~~

注意：本文的很多解法都来自网络，我怕我日后忘记所以才记录下来。