Fork me on GitHub

CSAPP-datalab

Posted on | In |
Words count in article: 2k 字 | Reading time ≈ 9 mins

看CSAPP看的实在是绝望，觉得假期肯定啃不完，所以决定先做实验，遇见不会的再翻书，过年这一个多周的时间，做了下datalab

bitAnd

题目：只能用～和|来实现位的与操作。

  • bitAnd - x&y using only ~ and |

    • Example: bitAnd(6, 5) = 4
    • Legal ops: ~ |
    • Max ops: 8
    • Rating: 1

思路：~x：非x，~y：非y，那么~x|~y就是既不是x也不是y，那~（~x|~y）就是既是x也是y，也就是x与y

1
2
3
4
int bitAnd(int x,int y)
{
	return (~(~x|~y));
}

getByte

题目：给定n （0<=n<=3），求出x第n个字节是哪数字。

  • 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

思路：（不做题觉得自己了解的还可以，一做题，就觉得，自己啥也没学到……）

第一感觉和CSAPP书上的一道习题挺像，移位运算，用0xFF移动n个字节，然后&一下

1
2
3
4
5
6
int getByte(int x,int n)
{
	int temp=x>>((n)<<3);
	temp=temp&0xFF;
	return temp;
}

logicalShift

题目：将x按逻辑位移移动n（0<=n<=31）位。

  • 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

思路：

一开始想定义的时候直接unsigned不就好了吗？觉得那这道题就没有意义了。先进行算术右移，然后将右移产生的1mask掉,关键是mask怎么构造，范围是0~31，那1左移31位，然后取反，就是0111……1，然后右移n位，左移1位这样就出来了0…0011…1110，然后加个1，就出来了

1
2
3
4
5
6
int logicalShift(int x,int n)
{
	int x1=x>>n;
	int mask=(~（1<<31)>>n<<1)+1
	return X1&mask；
}

bitCount

题目：用位运算计算出x中有多少个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

思路：一位一位的右移，然后看奇偶数，然后进行统计，但是不能用==，/，所以没有了思路。整道题看writeup，还是不懂，看完书再说。分治

bang

题目：不用！运算符求出！x结果

  • bang - Compute !x without using !
  • Examples: bang(3) = 0, bang(0) = 1
  • Legal ops: ~ & ^ | + << >>
  • Max ops: 12
  • Rating: 4

思路：一开始还是想用if，感觉自己还是没找到感觉。这个题就是找0和其他数之间的区别，0|0肯定还是0，但0|1=1，除了0以外，其他数都有1，所以想从这个方面入手。但是没有思路啊，看了别人的才知道，除了0，任何数自己|上自己的相反数最高位一定是1，那就好说了，直接|一下相反数，移位一下就OK

1
2
3
4
5
6
7
int bang(int x)
{
	int x1=~x+1;
	x=x|x1;
	x=x>>31;
	x=x+1；
}

tmin

题目：返回补码整数的最小整数数值。

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

思路：这不就是返回一个确定的值吗？

1
2
3
4
int tmin(void)
{
    return 0x80 << 24;
}

fitsBits

题目：只给出n个二进制位，能否表示x,能返回1.

  • fitsBits - return 1 if x can be represented as an
  • n-bit, two’s complement integer.
  • 1 <= n <= 32
  • Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 15
  • Rating: 2

思路：因为在前面的bitCount，我在歪路上想了怎么能知道移位移到了最后一位，也就是怎么知道x转为二进制需要多少位，所以这个题就很简单了。将x右移n-1位，判断是不是全1或全0.

1
2
3
4
5
6
7
int fitsBits(int x, int n)
{
   int x1 =~((~n)+1);
   x=x>>x1;
   int ans=(!tmpx|!(tmpx+1));
   return ans;
}

divpwr2

题目：给出整数x，整数n，求[x/(2^n)]，答案要接近趋向0方向。

  • divpwr2 - Compute x/(2^n), for 0 <= n <= 30
  • Round toward zero
  • Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 15
  • Rating: 2

思路：二进制的除就是右移，那就是x>>n.试了一下，只要x是负数，向下取整。首先判断是不是负数，(~( (x >> 31) & 0x1) )+1，是负数构造出0xFF……FF出来，然后构造q=2^n-1 既~((~0)<<n)，如果既然是负数的话就可以加上(tmp & q) 既 0x0…FFF，再右移动n位。

1
2
3
4
5
6
7
int divpwr2(int x, int n)
{
    int tmp = (~( (x >> 31) & 0x1) )+1 ;
    int q= ~((~0)<<n);
    int ans = (x + (tmp & q) ) >> n ;
    return ans;
}

negate

题目：求相反数

  • negate - return -x
    • Example: negate(1) = -1.
    • Legal ops: ! ~ & ^ | + << >>
    • Max ops: 5
    • Rating: 2
1
2
3
4
int negate(int x)
{
	return ((~x)+1)
}

isPositive

题目:判断x是不是正数

  • isPositive - return 1 if x > 0, return 0 otherwise
    • Example: isPositive(-1) = 0.
    • Legal ops: ! ~ & ^ | + << >>
    • Max ops: 8
    • Rating: 3

思路：因为有0，所以不能看符号位，那就转换一下思路，取反，如果0，那么结果是1，如果为负数，那结果为正数，符号位为1，如果x为0或负数，那么!x | (x >> 31) != 0，再！一下就OK了

1
2
3
4
int isPositive(int x)
{
	return !(!x|(x>>31)); 
}

isLessOrEqual

题目：用位运算判定x<=y，如果是就返回1，如果不是就返回0。

  • isLessOrEqual - if x <= y then return 1, else return 0
  • Example: isLessOrEqual(4,5) = 1.
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 24
  • Rating: 3

思路：分两种情况，同号和异号，异号比较一下符号位就好，同号x-y的符号位是不是0.

1
2
3
4
5
6
7
8
9
int isLessOrEqual(int x, int y)
{
   int signx = (x >> 31);
   int signy = (y >> 31);
   int isSameSign=!(signx^signy) ;
   int p=!(((~x)+1+y)>>31);
   int ans=(isSameSign&p)|((!isSameSign)&signx);
   return ans;
}

ilog2

题目：求整数的log(x)。

  • ilog2 - return floor(log base 2 of x), where x > 0
  • Example: ilog2(16) = 4
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 90
  • Rating: 4

思路：感觉和之前C程里解方程的实验应该差不多。二分法找最高位为1的位置。

1
2
3
4
5
6
7
8
9
10
int ilog2(int x)
{
	int num=0;
	num=(!!(x>>16))<<4;
	num=num+((!!(x>>(8+num)))<<3);
	num=num+((!!(x>>(4+num)))<<2);
	num=num+((!!(x>>(2+num)))<<1);
	num=num+((!!(x>>(1+num)))<<0);
	return num;
}

float_neg

题目：返回输入uf的负数形式-uf。如果uf是NAN形式就直接返回参数。

  • float_neg - Return bit-level equivalent of expression -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 representations of
  • single-precision floating point values.
  • When argument is NaN, return argument.
  • Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
  • Max ops: 10
  • Rating: 2

思路：题目读不懂，翻书+google，uf：unsigned float ； NaN（非数）:未定义或不可表示的值，先判断是不是NaN(>0x2f800000)，是就直接返回，不是则取反

1
2
3
4
5
6
7
8
9
unsigned float_neg(unsigned uf)
{
    unsigned result;
    unsigned tmp;
    result=uf^0x80000000;
    tmp=uf&0x7fffffff;
    if(tmp>0x7f800000) result=uf;
    return  result;
}

float_i2f

题目：将int型的x转为float型的x。

  • float_i2f - Return bit-level equivalent of expression (float) x
  • Result is returned as unsigned int, but
  • it is to be interpreted as the bit-level representation of a
  • single-precision floating point values.
  • Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
  • Max ops: 30
  • Rating: 4

思路：没思路，翻书，感觉一到浮点数就一脸懵逼，完全没有概念，又是一道把别人的答案从头到尾看了好几遍的题，等看完书再说叭（头秃……）。

如果是0，直接返回即可

如果是0x80000000,返回0xcf000000

如果负数：变为整正数之后按照正数计算

正数：计算尾数部分左移还是右移，然后计算阶码，加上偏置值127，尾数向偶数舍入。

float_twice

题目：就是将浮点数乘以2倍。

  • float_twice - 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

嘤嘤嘤~浮点数真令人头大

0%