CSAPP:datalab

读,就硬读。光读没用,得做练习。这个系列记录思路不写答案。

拿到文件夹先读README。

第一个lab,关于位运算。通过受限制的c语言编程实现函数功能。

直接读bits.c,里面有全部信息。每次测试程序都要先make一下。

  • 1:只用按位与和非实现异或

/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */

&=全为1

~&=不全为1

异或=不全为0且不全为1,按此逻辑组合即可。

你让我用括号了???

反思:浪费时间,与和或傻傻分不清楚

  • 2:位运算取补码的最小值

英语时间:补码(two's complement)反码:(one's complement)。结合公式很好理解

/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */

补码公式:

B2Tw(x)=xw1+i=0w2xi2iB2T_w(\vec{x})=-x_{w-1}+\sum^{w-2}_{i=0}x_i2^i

最高位是符号位,要求最小值,则最高位为负1,其他位为0。

由于题目限制,只能使用最大为0xff的数字和位运算符,又int长度为4*8=32,故对0x1左移31即得。

  • 3:判断一个数是否为补码的最大值

/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise //0=1111 1111=0000 0000
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */

最大值:符号位0,其他位1,即max=011111...=0x7fffffff。

!0=1,故应使每一位化为0,再取非即为1;其他任何数取非都为0。

注意到max+1=~max,补码max加一得到其反码。反码相加得11111111,取反即得0。

特例:-1 = 0x1111 1111也有这个性质,故须排除。

寻找另一性质:!(max+1)=0,而!(-1+1)=1,结合上一步结果即可。

反思:逻辑非!和按位非~

  • 4:判断所有奇数位为1

/* 
 * 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
 */

要取奇数位,首先构造掩码:0xaaaaaaaa,用&取出奇数位,再异或,取反即得。

错误示范:m=0xaa;m+=m<<8;m+=m<<8;m+=m<<8;算出来个啥?

  • 5:取相反数

/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */

常识???反码加1

大佬题解:https://wdxtub.com/csapp/thick-csapp-lab-1/2016/04/16/

https://zhuanlan.zhihu.com/p/59534845题不一样???