【CMU 15-213: CSAPP】datalab

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

【CMU 15-213: CSAPP】datalab

作者：

为光nixiaK , 2024-09-11 19:35:42 , 所有人可见 , 阅读 6

bitXor

/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 1```4
 *   Rating: 1
 */
 int bitXor(int x, int y) {
  return ~(x & y) & ~(~x & ~y);
}

转化成集合问题，每个位代表一个元素，&取交集 |取并集 ^就是求A、B都有但同时没有的。

tmin

/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  return 1 << 31;
}

32位数，最小的应该是1000…00

isTmax

/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */
int isTmax(int x) 
  return !((x + 1) ^ (~x) | !(x+1));
}

最大数的特点，符号位为0，其他位都是1.

011..1111

观察这个数的特殊性，它+1与取反的值是一样的，所以考虑用这个作为判断条件：!((x + 1) ^ (~x)

但是问题就是111…111，它+1与取反的值是一样的（因为有进位），所以还需要加一个额外的判断。
提示：
在C语言中，非0即为真。利用 x+1=0时结果为假这一特点，当x=-1 时，!(x+1) = 1,
再用!(x+1) 与原判式进行或运算，即 (~(x+1)^x)|!(x+1), 则该式在x=-1时一定为真，
x!=-1 时真假就一定取决于 ~(x+1)^x 。

allOddBits

/* 
 * 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 t = ((0xAA << 24) + (0xAA << 16) + (0XAA << 8) + 0xAA);
  return !((t & x) ^ t);
}

构造奇数位全为1，其他位全为0的数：0xAAAAAAAA

如果一个数&0xAAAAAAAA仍然为0xAAAAAAAA，那这个数奇数位全为1

negate

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

负数就是取反+1

isAsciiDigit

/* 
 * 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 t = 0x37;
   int y = 0x30;
   return ((!((t & x) ^ x) | !((0x38 & x) ^ x) | !((0x39 & x) ^ x)) & (!((y & x) ^ y)));
}

0x30-0x39二进制表示：

00…0011 0000

00…0011 0001

00…0011 0010

00…0011 0011

00…0011 0100

00…0011 0101

00…0011 0110

00…0011 0111

00…0011 1000

00…0011 1001

首先需要检查第32-7位是否为0，第5、6位是否为1，可以与0x30 取&，如果是，则结果仍然是0x30。

然后需要检查后四位，可以发现：0x30-0x37 用满了后三位（从000-111），所以他们的后三位与00…0011 0111（0x37）取&应该是不变的，这可以作为他们的判断条件，对于0x38、0x39就分别特判即可。

conditional

/* 
 * 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 t = ((!(!x) << 31) >> 31);
  return (y & t) | (z & ~t);

}

提示：(y op expr) | (z op expr)

接下来就是想办法让x为1的时候左边的表达式为y，右边的表达式为0；

x为0的时候x为1的时候左边的表达式为0，右边的表达式为x；

所以expr应该为全0或者全1，op应该为&。

isLessOrEqual

/* 
 * 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 signx = (x >> 31) & 1;
    int signy = (x >> 31) & 1;

    int flag1 = !((y-x)>>31);
    int flag2 = (signx ^ signy) & signy;

    return flag1 | flag2;
}

分类讨论：

x y同号
- x-y不会溢出，可以通过x-y的正负得到大小关系
x y异号
- 直接判断符号，正数肯定大于负数

用两个flag联合判断。

logicalNeg

/* 
 * 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 t = (x | (~x+1)) >> 31;
    t = ~t;
    return t & 1;
}

0与其他数的区别就是他的相反数仍然是它本身，更有用的他的符号位~x+1是不变的，都是0。

howManyBits

/* 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) {
  // 0 1交接 正：0 1 负：1 0
  // 正：最左边的1在哪 负：最左边的0在哪

  //负数的话取反

  //以下内容是参考的
  int flag = (x >> 31);
  x = ((~x) & flag) | (x & (~flag));
  //问题都变成了找最高位的1

  //太妙了
  int bit_16 = (!!(x >> 16)) << 4;
  x = x >> bit_16;
  int bit_8 = (!!(x >> 8)) << 3;
  x = x >> bit_8;
  int bit_4 = (!!(x >> 4)) << 2;
  x = x >> bit_4;
  int bit_2 = (!!(x >> 2)) << 1;
  x = x >> bit_2;
  int bit_1 = (!!(x >> 1));
  x = x >> bit_1;
  int bit_0 = x;

  return bit_16 + bit_8 + bit_4 + bit_2 + bit_1 + bit_0 + 1;
}

分类讨论：

正数
- 寻找最左边的1的位置+1
负数
- 寻找最右边的0的位置+1

首先考虑将这两种情况归一，对于负数取反操作，所以问题就变成：最高位的1在第几位？

采用二分法，通过移位取!!符号判断是否有1.

例如

0001 1111

右移动4位，取! !，结果为1，所以至少需要4位，以此类推。

floatScale2

//float
/* 
 * floatScale2 - 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
 */
unsigned floatScale2(unsigned uf) {

  unsigned s = (uf >> 31) & 0x1;
  unsigned e = (uf >> 23) & 0xff;
  unsigned f = uf & 0x7fffff;

  if(e == 0xff){
    return uf;
  }

  if(e == 0){
    f = f << 1;
    return (s << 31) | (e << 23) | f;
  }
  e ++;
  return (s << 31) | (e << 23) | f;
}

分类讨论：

规格化
- 可以让e直接+1
非规格化
- e全为1
  - 直接返回
- e全为0
  - f左移1位

floatFloat2Int

/* 
 * floatFloat2Int - Return bit-level equivalent of expression (int) f
 *   for floating point argument f.
 *   Argument is passed as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point value.
 *   Anything out of range (including NaN and infinity) should return
 *   0x80000000u.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
int floatFloat2Int(unsigned uf) {

  unsigned s = (uf >> 31) & 0x1;
  unsigned e = (uf >> 23) & 0xff;
  unsigned f = uf & 0x7fffff;

  if(e == 0xff){
    return 0x80000000;
  }
  if(e == 0){
    return 0;
  }

  int E = e - 127;
  if(E < 0){
    return 0;
  }

  f = f | 1 << 23;

  if(E > 32){
    return 0x80000000;
  }

  if(E > 23){
    f <<= (E - 23);
  }
  else{
    f >>= (23 - E);
  }

  if(s == 1) f = ~f + 1;
  return f;
}

先得到各个部分的二进制表示

分类讨论

规格化
- 先得到E，指数部分
  - E<0 肯定小于0，所以直接返回0
  - 如果E>23,左移E-23位，因为已经移动了23位
  - 如果E<23,右边23-E
  - 如果E>32，超过int最大值，返回无穷
非规格化
- e为0
  - 值肯定小于0，直接返回0
- e全为1
  - 返回无穷

floatPower2

/* 
 * floatPower2 - Return bit-level equivalent of the expression 2.0^x
 *   (2.0 raised to the power x) for any 32-bit integer x.
 *
 *   The unsigned value that is returned should have the identical bit
 *   representation as the single-precision floating-point number 2.0^x.
 *   If the result is too small to be represented as a denorm, return
 *   0. If too large, return +INF.
 * 
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while 
 *   Max ops: 30 
 *   Rating: 4
 */
unsigned floatPower2(int x) {
  if(x < -149){
    return 0;
  }
  else if(x < -126){
    return 1 << (x + 149);
  }
  else if(x <= 127){
    return (x + 127) << 23;
  }
  else{
    return 0xff << 23;
  }
}

分类讨论：

规格化数
- bias = (2^(k-1)) - 1 = 2^7-1 = 127
- 最小值 E= 1-127 =-126，f为0.0…00，实际代表1.00…0 → 2^-126
- 最大值 e=~~011..11~~E=256-127 = 129，f:1.11..111:+ 2^-1 + 2^-2 + .. + 2^-23 → (2 - 2^-23)* 2^129 （错误理解）
- 最大值e=1111 1110（不全为0，那就最后一位不为0）E = 254-127=127
非规格化
- 最小值 E=1-127 0.0000..1 → 2^-23 * 2^-126 = 2^-149
- 最大值E=1-127 2^-1 + 2^-2 + .. + 2^-23 = 1 - 2^-23 → (1 - 2^-23) * 2 ^ -126
  所以：
x>127
- Nan
x<149
- 返回0
2^-126 ≤ x ≤ 2^127
- x=e-bias e = x + bias → e = x + 127
-149 ≤ x < -126
- 属于非规格化 E=1-bias固定的，所以只能改变f
- M * 2^-126 = 2^x, M = 2^(x+126)

2 评论

App 内打开