CS:APP Datalab。

很棒的lab,大二ICS课上写过,又写了一遍,花了大半天,学到许多👍

int

bitXor

将x y中不相同的bit置1，相同的置0即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {
  int a = (~x) & y;
  int b = x & (~y);
  int c = (~a) & (~b);
  return ~c;
}

isTmax

32位最大整数:m=0x7fff，m+1=m=0x8000,0xffff + 1 = ~0xffff = 0。
判d段x+1与x是否相等，再检查~x是否为0即可

1
2
3
4
5
6
7
8
9
10
11
12
/*
 * 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) {
  int c = (x+1) ^ (~x);
  int d = !(~x);
  return !(c | d);
}

allOddBits

构造奇数位为1，偶数位为0的mask，再看x&mask^mask是否为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 
 * 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 m = 0xAA;
  m = (m << 8) | m;
  m = (m << 16) | m;
  return !((x & m) ^ m);
}

isAsciiDigit

$$x <= 0x39 –> x & (~0x3f) == 0$$

$$0x30 <= x <= 0x39 –> x & 0x30 ^ 0x30 == 0$$

$$x & 0xf < 9 –> if x & 8 != 0 then x & 6 == 0$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 
 * 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 m = 0x3f;
  // int n = ~m;
  int y = x & (~0x3f); // the higher bits in x should be 0
  y |= (x & 0x30) ^ 0x30; // 0x30 <= x <= 0x3f --> m = 0
  //y !=0 --> false
  m = (x >>3) & 1 & (!!(x & 6)); 
  return !(m|y);
}

conditional

构造两个mask,根据x的true or false将mask1,mask2分别设置为0xffff,0x0，再分别与上y,z即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 
 * 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 m = !x; 
  int n;
  m = (m << 1) | m;
  m = (m << 2) | m;
  m = (m << 4) | m;
  m = (m << 8) | m;
  m = (m << 16) | m;
  n = ~m;
  return (m & z) | (y & n);
}

isLessOrEqual

比较y-x的符号位是否为1可得出当差不溢出时x是否小于等于y。仅当x,y异号时，两者相减可能发生溢出，因此需要单独拿出x为负y为正、x为正y为负这两种情况，显然此时不用相见就可直接得出结果；再缝上两者同号时的结果即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 
 * 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 z = 1 & ((y + 1 + (~x)) >> 31);// y - x
  x = (x >> 31) & 1;
  y = (y >> 31) & 1;
  int k = 1 & ((y + 1 + (~x)) >> 31);// k = 1 if x < 0 and y >= 0, return 1
  int m = 1 & ((x + 1 + (~y)) >> 31);// m = 1 if x >= 0 and y < 0, return 0
  return ((!z) | k) & (!m);
}

logicalNeg

只有当x为0时，x与-x的符号位都为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 
 * 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 y = (x >> 31) & 1; // x < 0 --> y = 1, x >=0 --> y = 0
  int z = ~x + 1;
  z = (z >> 31) & 1; // x >0 --> z = 1
  return 1 ^ (y | z);
}

howManyBits

好难啊🤯参考了一下网上的思路。首先梳理需求，需要找出给定整数补码的最少位数，观察给的example，将一个整数拆成符号位和无符号数两部分，找到无符号数最少要几位表示再加上一个符号位就行了。

首先根据x的符号位决定是否将x取反（即取出x的无符号数部分）

然后把最高位以下的所有位数全部置1（不断地右移同时或起来= =）

最后算出有多少位是1。思路是一位一位的移到右边看是不是1，是的话就加起来。但是由于运算的次数受限，所以先是两位两位地处理，用$mask=0101..01$屏蔽一些位再加起来，这样每两位一组算出一个组里有几个1，再把2位一组扩大到4位一组，类推下去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/* 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)  {
  int y = (x >> 31) & 1; // y = 1 if x < 0
  int n = (y << 1) | y;
  n = (n << 2) | n;
  n = (n << 4) | n;
  n = (n << 8) | n;
  n = (n << 16) | n; // n = 0xffffffff if x < 0
  x = (x & (~n)) | ((~x) & n); // x = abs(x)
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16; // set all the lower bits 1
  // count bit 1's number
  n = 0x55 | (0x55 << 8);
  n |= n << 16; //0x55555555
  x = (x & n) + ((x >> 1) & n);
  n = 0x33 | (0x33 << 8);
  n |= n << 16;
  x = (x & n) + ((x >> 2) & n);
  n = 0x0f | (0x0f << 8);
  n |= n << 16;
  x = (x & n) + ((x >> 4) & n);
  n = 0xff | (0xff << 16);
  x = (x & n) + ((x >> 8) & n);
  n = 0xff | (0xff << 8);
  x = (x & n) + ((x >> 16) & n);
  return x+1;
}

float

终于做到float了= =，复习下ieee floating-point representation

floatScale2

uf为NaN/Inf时直接return uf,规格化浮点数直接把exp+1,非规格化则要注意frac和exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/* 
 * 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 frac = uf & 0x7fffff;
  unsigned exp = (uf >> 23) & 0xff;
  unsigned s = uf & (1 << 31);
  if(exp == 0xff) { return uf; }
  if(exp) {
    // normalized
    exp += 1;
    if(exp == 0xff) { frac = 0;}
  }
  else {
    // denormalized
    unsigned M = frac >> 22;
    frac = (frac << 1) & 0x7fffff;
    if(M) {
      int mask = 1 << 22;
      int i = 1;
      while(i <= 22) {
        if(frac & mask) {
          exp = i;
          break;
        }
          frac = (frac << 1) & 0x7fffff;
      }
      i = i + 1;
    }
  }
  return s | (exp << 23) | frac;
}

floatFloat2Int

浮点数转整数，只要按照ieee标准运算就行了，注意一下溢出情况：float32的范围超出int32、Nan、Inf，以及精度太低时直接舍去取0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* 
 * 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 frac = uf & 0x7fffff;
  int exp = (uf >> 23) & 0xff;
  unsigned s = uf & (1 << 31);
  int E = exp - (1 << 7) + 1;
  if(!frac && !exp || E <0) { return 0; }
  if(exp == 0xff || E > 30) { return 0x80000000u; }
  frac |= 1 << 23;
  frac >>= (23 - E);
  if(s) { frac = ~frac + 1; }
  return frac;
}

floatPower2

注意溢出的范围，以及规格化与非规格化浮点数的范围即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/* 
 * 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) {
    // return 2;
    int bias = (1 << 7) - 1;
    int exp = x + bias;
    if(x < -23 - bias) { return 0; }
    if(x >= 0xff - bias) { return 0xff << 23; }
    if(x < -bias) {
      int n = -x - bias;
      return 1 << (23 - n);
    }
    return exp << 23;
}