CS:APP 第二章

CS:APP

家庭作业

2.63

1
2
3
4
5
6
7
8
9
10
11
12
13
unsigned srl(unsigned x, int k) {
  /* Perform shift arithmetically */
  unsigned xsra = (int) x >> k;
  int w = sizeof(int) << 3;
  return xsra & ~(-2 << (w - k - 1));
}

int sra(int x, int k) {
  /* Perform shift logically */
  int xsrl = (unsigned) x >> k;
  int w = sizeof(int) << 3;
  return xsrl - ((xsrl << 1) & (2 << (w - k - 1)));
}

2.65

1
2
3
4
5
6
7
8
9
10
/* Return 1 when x contains an odd number of 1s; 0 otherwise.
   Assume w=32 */
int odd_ones(unsigned x) {
  x ^= x >> 16;
  x ^= x >> 8;
  x ^= x >> 4;
  x ^= x >> 2;
  x ^= x >> 1;
  return x & 1;
}

2.66

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 * Generate mask indicating leftmost 1 in x.  Assume w=32.
 * For example, 0xFF00 -> 0x8000, and 0x6600 --> 0x4000.
 * If x = 0, then return 0.
 */
int leftmost_one(unsigned x) {
  unsigned t = x;
  t >>= 1;

  t |= t >> 1;
  t |= t >> 2;
  t |= t >> 4;
  t |= t >> 8;
  t |= t >> 16;

  return (t + 1) & x;
}

2.75

1
2
3
4
unsigned unsigned_high_prod(unsigned x, unsigned y) {
  int w = sizeof(int) << 3;
  return signed_high_prod(x, y) + (((int) y >> (w - 1)) & x) + (((int) x >> (w - 1)) & y);
}

说明

x,yx,y 是补码数，令 x′←T2Uw(x),y′←T2Uw(y)x'\leftarrow T2U_w(x),y'\leftarrow T2U_w(y)。

x′⋅y′=(x+xw−1⋅2w)×(y+yw−1⋅2w)=x⋅y+(xw−1⋅y+yw−1⋅x)2w+xw−1⋅yw−1⋅22w \begin{align} x'\cdot y'&=(x+x_{w-1}\cdot 2^w)\times(y+y_{w-1}\cdot 2^w)\notag\\ &=x\cdot y+(x_{w-1}\cdot y+y_{w-1}\cdot x)2^w+x_{w-1}\cdot y_{w-1}\cdot 2^{2w} \end{align}

令 a←signed_high_prod(x, y),b←unsigned_high_prod(x', y')a\leftarrow\verb|signed_high_prod(x, y)|, b\leftarrow\verb|unsigned_high_prod(x', y')|，有 a=(x⋅y−(x⋅y) mod 2w)/2wb=(x′⋅y′−(x′⋅y′) mod 2w)/2w \begin{align} a&=(x\cdot y-(x\cdot y)\bmod 2^w)/2^w\\ b&=(x'\cdot y'-(x'\cdot y')\bmod 2^w)/2^w \end{align}

由 (1)(1) 可知 (x⋅y) mod 2w=(x′⋅y′) mod 2w(x\cdot y)\bmod 2^w=(x'\cdot y')\bmod 2^w，(3)−(2)(3)-(2) 得 b=a+xw−1⋅y+yw−1⋅x+xw−1⋅yw−1⋅2wb=a+x_{w-1}\cdot y+y_{w-1}\cdot x+x_{w-1}\cdot y_{w-1}\cdot 2^w

即 b=(a+xw−1⋅y+yw−1⋅x) mod 2w b=(a+x_{w-1}\cdot y+y_{w-1}\cdot x)\bmod 2^w

2.80

1
2
3
4
int threefourths(int x) {
  int p = x >> 2, q = x & 3;
  return p + (p << 1) + q - ((q == 0) & (~x >> 31));
}

2.95

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* computs 0.5*f.  If f is NaN, then return f. */
float_bits float_half(float_bits uf) {
  float_bits s = uf & 0x80000000, f = uf & 0x007FFFFF, e = (uf >> 23) & 0xFF;

  if (e == 0xFF) {
    return uf;
  }
  
  if (e > 1) {
    e--;
  } else {
    if (e == 1) {
      f |= 1 << 23;
      e = 0;
    }
    int t = f;
    f >>= 1;
    if (t & f & 1) {
      f++;
    }
  }
  return s | (e << 23) | f;
}

2.97

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
/* Compute (float) i */
float_bits float_i2f(int i) {
  if (i == -0x7FFFFFFF - 1) {
    return 0xCF000000;
  }

  if (i == 0) {
    return 0;
  }

  float_bits s = 0, f, e;
  if (i < 0) {
    i = -i;
    s = 0x80000000;
  }

  int hb = 30;
  while (!(i >> hb)) {
    hb--;
  }

  i ^= 1 << hb;
  e = hb + 127;
  int dif = hb - 23;
  if (dif > 0) {
    f = i >> dif;
    if ((i & ((1 << dif) - 1)) + (f & 1) > (1 << (dif - 1))) {
      f++;
      if (f & 0x00800000) {
        f = 0;
        e++;
      }
    }
  } else {
    f = i << -dif;
  }

  return s | (e << 23) | f;
}

datalab

https://git.gzezfisher.top/FISHER_/CSAPP-sol/src/branch/main/data/bits.c