🏠主页 📁归档 🏷️标签 😋关于 🤝友链

CSAPP Datalab

     约 1725 字   预计阅读 4 分钟    次阅读     条评论  
警告
本文最后更新于 2023-03-21，文中内容可能已过时。

Ubuntu 12.04.5。

德摩根律。

1
2
3

int bitAnd(int x, int y) {
  return ~((~x)|(~y));
}

要取第 n 个字节，将 x 右移 n*8 位，再去除多余字节即可。

1
2
3

int getByte(int x, int n) {
  return (x>>(n<<3))&0xFF;
}

算数右移 n 位，并构造形如 0…01…1 的二进制串，将左边填充的 n 位清 0。 构造方法：将 1 « 31 取反得到 0x7fffffff，对于 n >= 1，将 0x7fffffff 右移 n - 1 位完成构造。但对于 n = 0，不能右移 -1 位，这是未定义行为。故最终方案为将 0x7fffffff 右移 n 位，再左移 1 位、加 1，完成构造。

1
2
3

int logicalShift(int x, int n) {
  return (x>>n)&((~(1<<31)>>n<<1)+1);
}

分解子问题。先求每 2 位有几个 1，再求每 4 位有几个 1，再求每 8 位有几个 1，再求每 16 位有几个 1，最后求所有 1 的个数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

int bitCount(int x) {
  int t1,t2,t3,t4,t5,cnt;
  t1=0x55|(0x55<<8);
  t1=t1|(t1<<16);
  t2=0x33|(0x33<<8);
  t2=t2|(t2<<16);
  t3=0x0F|(0x0F<<8);
  t3=t3|(t3<<16);
  t4=0xFF|(0xFF<<16);
  t5=0xFF|(0xFF<<8);
  cnt=(x&t1)+((x>>1)&t1);
  cnt=(cnt&t2)+((cnt>>2)&t2);
  cnt=(cnt&t3)+((cnt>>4)&t3);
  cnt=(cnt&t4)+((cnt>>8)&t4);
  cnt=(cnt&t5)+((cnt>>16)&t5);
  return cnt;
}
  • 对于非 0 数，其与自己相反数相或，最高位为 1，算数右移 31 位得到 0xffffffff，再加 1 则变为 0。
  • 对于 0，其与自己相反数相或，最高位为 0，算数右移 31 位得到 0x0，再加 1 则变为 0x1。
1
2
3

int bang(int x) {
  return ((x|(~x+1))>>31)+1;
}

补码可表示的最小值：最高位为 1，其余位为 0。

1
2
3

int tmin(void) {
  return 1<<31;
}

将 x 左移 32 - n 位，再右移 32 - n 位，若没有数据丢失，则满足题意。

1
2
3
4

int fitsBits(int x, int n) {
  int t=33+(~n);
  return !(x^(x<<t>>t));
}
  • x > 0 时，直接右移 n 位。
  • x < 0 时，需要加上偏置量保证除法结果向 0 取整。
1
2
3
4
5

int divpwr2(int x, int n) {
  int offset=(1<<n)+(~0);
  int flag=x>>31;
  return (x+(offset&flag))>>n;
}

相反数可表示为原数取反再加 1，可以由一个数和它的相反数相加为 0 推出此结论。

1
2
3

int negate(int x) {
  return ~x+1;
}

逆向思维，先找出 x <= 0 的情况。 当 x = 0 时，!x 为 1；当 x < 0 时，x 的符号位为 1。不满足这两种情况，则 x > 0。

1
2
3

int isPositive(int x) {
  return !((!x)|(x>>31));
}

满足 x <= y 的情况如下：

  • x、y 同号时，y - x 的符号位为 0。

  • x、y 异号时，x 负 y 正。

1
2
3
4
5

int isLessOrEqual(int x, int y) {
  int t=1<<31;
  int xs=x&t,ys=y&t,ss=(y+(~x)+1)&t;
  return !!((!(xs^ys)&!ss)|((xs^ys)&xs));
}

采用二分思想，每一行的 t 计算的都是 x 的最高位的 1 至少在哪一位。 在已确定有 1 的 32 位中，若高 16 位有 1，则 t1 = 16，否则 t1 = 0。 在已确定有 1 的 16 位中，若高 8 位有 1，则 t2 = t1 + 8，否则 t2 = t1。 在已确定有 1 的 8 位中，若高 4 位有 1，则 t3 = t2 + 4，否则 t3 = t2。 在已确定有 1 的 4 位中，若高 2 位有 1，则 t4 = t3 + 2，否则 t4 = t3。 在已确定有 1 的 2 位中，若高 1 位有 1，则 t5 = t4 + 1，否则 t5 = t4。 t5 即为最终结果。

1
2
3
4
5
6
7
8

int ilog2(int x) {
  int t=(!!(x>>16))<<4;
  t=t+((!!(x>>(t+8)))<<3);
  t=t+((!!(x>>(t+4)))<<2);
  t=t+((!!(x>>(t+2)))<<1);
  t=t+(!!(x>>(t+1)));
  return t;
}

视 uf 的值而定。

  • NaN：若阶码为全 1，尾数不全为 0，则 uf 为 NaN，直接返回 uf。
  • 其他：符号位与 1 异或，实现取反即可。
1
2
3
4
5
6
7

unsigned float_neg(unsigned uf) {
  unsigned res=uf^0x80000000;
  if((uf&0x7fffffff)>0x7f800000){
    return uf;
  }
  return res;
}
  • x == 0：返回 0。
  • x != 0：通过左移找到 x 的绝对值（absx）的位表示的第一个 1，用 cnt 记录 absx 第一个 1 前有多少个 0，当第一个 1 左移到最高位时，开始计算阶码和尾数。
    • 阶码：exp = E + bias = (31 - cnt) + 127 = 158 - cnt。再左移 23 位，方便拼接结果。
    • 尾数：absx 的第一个 1 已经左移到最高位，我们再把 absx 右移 8 位，这样，第一个 1 就到了第 31 - 8 = 23 位，后面的第 22 ~ 0 位存入 frac。 接着拼接符号位、阶码和尾数，得到一个未舍入的结果。
    • 最后考虑舍入问题。absx 的第一个 1 已经左移到最高位，后面的连续 23 位是可以精确表示的，31 - 1 - 23 = 7，因此我们要对 absx 的第 7 ~ 0 位，即低 8 位考虑舍入问题。如果低 8 位大于 0x80，向上舍入，结果加 1；如果低 8 位等于 0x80，则考虑 frac 的末位是否为 1，若是，则向上舍入，结果加 1；除此之外，低 8 位舍弃。
 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

unsigned float_i2f(int x) {
  unsigned absx=x,s=0,cnt=0,exp=0,frac=0,low8=0,res=0;
  if(x==0){
    return 0;
  }
  if(x<0){
    absx=-x;
    s=0x80000000;
  }
  while((absx&0x80000000)==0){
    absx<<=1;
    cnt++;
  };
  exp=(158-cnt)<<23;
  frac=(absx>>8)&0x7FFFFF;
  res=s|exp|frac;
  low8=absx&0xFF;
  if(low8>0x80){
    res++;
  }
  else if(low8==0x80){
    if(frac&0x01){
      res++;
    }
  }
  return res;
}

先取出符号位和阶码，再分类讨论。

  • 阶码为全 0：将 uf 左移 1 位，再补上符号位。这样指数不变，尾数向高权值位移动，实现乘 2。
  • 阶码不为全 0，也不为全 1：uf 阶码部分加 1，即 uf + 0x800000。再补上符号位。这样尾数不变，指数加 1，实现乘 2。因为规格化值和非规格化值从二进制串映射到浮点数的方法有所不同，所以该情况和阶码全为 0 的情况采用不同的方法。
  • 阶码为全 1：不做改变。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

unsigned float_twice(unsigned uf) {
  unsigned s=0,exp=0,res=uf;
  s=uf&0x80000000;
  exp=uf&0x7F800000;
  if(exp==0x00){
    res=(res<<1)|s;
  }
  else if(exp!=0x7F800000){
    res+=0x800000;
  }
  return res;
}
更新于 2023-03-21
阅读原始文档
返回 | 主页