刚完成CSAPP的Data Lab，现做经验总结。

negate()

求x逆元只需对其取反再+1即可。

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

不只是对于补码的int类型成立，对于unsigned类型也成立（无符号整数x的逆元即为1 << 32 - x）。

int类型整数的正负

判断补码数字x正负有不止一种方式。

1. 通过1 << 31构造TMin即100...00，求x & TMin并进行逻辑NOT运算，有int s = !(x & (1 << 31))。此时s = <x非负> ? 1 : 0。
2. 第二种方式简单许多。直接对x进行位移操作求得x >> 31，根据算数右移性质将符号位填满了自身位数。此时再对x >> 31进行取反 + 1得到s即为正负性。同样，s = <x非负> ? 1 : 0。

三目运算符的构造

构造函数int conditional(int x, int y, int z)以实现x ? y : z的功能。因为我没学过数字电路等课程，只能用不太规范的语言来表述。

大体思路是先处理x，构造出一个值s用于与y和z分别进行运算，使得y和z其中一个保持不变，另外一个变为0，最后再对他们进行OR运算或XOR运算得到所需的值。

根据布尔代数，-1(即111..111) & x == x且0 & x == 0，所以我们希望x ? <s = ~0> : <s = 0>。首先对x进行两次逻辑NOT运算!!x使x = x ? 1 : 0，对x取反再 +1构造出s。而后分别对y和z与s进行&运算，再对结果进行|或^即可。

代码如下

int conditional(int x, int y, int z) {
  int t = !!x;
  int s = (~t) + 1;
  int dealy = y & s;
  int dealz = z & (~s);
  return dealy | dealz;
}

比大小

isLessOrEqual()这道题比前面的isAsciiDigit()要思考的东西更多，因为溢出情况会稍微复杂一点点，当然我们也不需要专门写一段代码去判断到底有没有溢出（这个纯逻辑实现稍有复杂，且会超出题目要求的Max ops）。

我们可以在纸上画个数轴，画出几种不同的情况（这里我就不写了）。首先可以肯定的是：当x < 0 && y >= 0成立时，x < y也必定成立。我们把这个条件写成result1 = (x < 0 && y >= 0) ? 1 : 0。

因为我们计算的是x - y（或写作x + (-y)），我们在数轴上目测出若两数同号，他们求差不会产生溢出，只需要对他们的结果进行正负号判断即可。同号与否可以使用XOR来判断。

代码如下

int isLessOrEqual(int x, int y) {
  int scheck = 1 << 31;
  // 有时候代码写的越短并不是好事，多加一个变量即方便当时写又方便日后读。
  int minus_x = (~x) + 1; 
  int cmp = minus_x + y;
  int cmp_s = !(cmp & scheck);
  int x_s = !(x & scheck);
  int y_s = !(y & scheck);
  int condtion1 = (!x_s & y_s);
  int condtion2 = !(x_s ^ y_s);
  return condtion1 | (cmp_s & condtion2);
}

逻辑非的实现

因为逻辑非运算符实在是太强大了，可以直接把非零量转化为1，所以我在解决前面的题目十分依赖他，但是这道题不让用了。这道题的关键在于思考0相比于其他数字在位运算上有什么特征，只要将0与其他所有数字区分开来，我们就能实现C语言的逻辑非运算符。

（我不是数学系学生，我的数学语言不是那么严谨，看得懂就行）

我们找到一个特性：在实数域上，0的加法逆元就是他本身。但是在补码加法中，有一个与0一样具有这个特性的数即1 << 31。好在他与0异号，我们只需要再加上一个符号判断条件即可。

除此之外，还可以利用0对自己逆元进行或运算不会改变符号位，求得对自己逆元的或运算后再右移31位再加1。而1 << 31就没这么好运了，将它作完上面的步骤后会发现得到的是0（自己动笔试试）。

代码如下

int logicalNeg(int x) {
  int a = (~x) + 1;
  int or = a | x;
  int deter = (or >> 31) + 1;
  return deter;
}

找最高有效位

不愧4分题中的压轴题。如果不是题目限制，这题利用了分而治之的思想可以写成很漂亮的递归形式。不仅不能使用函数，也不能使用条件判断语句。所以这道题难就难在要使用简单运算来实现分治。

在草稿纸上画画我们可以发现把负数取正他的最高有效位不变，所以如果函数传入的参数是负数我们就将其取反+1。

接下来是分治的实现。先贴几行代码

    int b16, b8;
    b16 = !!(x >> 16) << 4;
    x = x >> b16;
    b8 = !!(x >> 8) << 3;
    x = x >> b8;

b<t>表示在前t位有或没有数字x分别所需要右移的位数。!!(x >> 16) = <前x位有数字> ? 1 : 0。如果有数字，再将这个数左移4位得到16，x再右移16。因为前16位有数字，我们就不再需要后16位了，直接从前16位的后8位开始找。如果没有数字，x就右移0位，直接从后16位开始找，找后8位。就这样递归到b0。最后将所有b<t>相加再加1（符号位）即可得到最高有效位。

代码如下

int howManyBits(int x) {
  int check, s, k, num;
  int b16, b8, b4, b2, b1, b0;

  check = 1 << 31;
  s = !(x & check);
  k = (~s) + 1;
  num = (x & k) | ((~x) & (~k));

  b16 = !!(num >> 16) << 4;
  num = num >> b16;
  b8 = !!(num >> 8) << 3;
  num = num >> b8;
  b4 = !!(num >> 4) << 2;
  num = num >> b4;
  b2 = !!(num >> 2) << 1;
  num = num >> b2;
  b1 = !!(num >> 1);
  num = num >> b1;
  b0 = num;

  return b16 + b8 + b4 + b2 + b1 + b0 + 1;
}

浮点数求幂

浮点数前两道题说实在就是力大砖飞大力出奇迹，就这一道需要好好思考一下数学相关内容。一共4种情况。

1. 当 x >= 128 时：返回正无穷大（+INF）

if(x >= 128) return 0x7f800000;

• IEEE 754中，规格化浮点数的指数范围是有限的：8位指数位的取值范围是0~255，但实际有效指数（E = 指数位值 - 127）的合法范围是 -126 ~ 127（指数位值1~254）。
• 当 x >= 128 时，2^x 已经超过了规格化浮点数能表示的最大指数（127），此时按IEEE 754标准，应表示为正无穷大（+INF）。
• 0x7f800000 的二进制结构为：符号位0（正）、指数位全1（0xff）、尾数位全0，正好是+INF的位表示。

2. 当 x >= -126 时：返回规格化浮点数表示

if(x >= -126) return (x + 127) << 23;

• 此范围的 x 属于规格化浮点数的有效指数范围（-126 <= x <= 127）。

• 对于 2^x，其浮点数形式可表示为 1.0 × 2^x（有效数字是1.0，小数部分为0）。

  • 指数位值 = 实际指数 x + 偏移量 127（即 x + 127）。
  • 尾数位全为0（因为有效数字是1.0，小数部分为0）。

• 因此，浮点数的位表示为：指数位值左移23位（跳过23位尾数位），符号位为0（已隐含在计算中）。

  例如：x=0 时，2^0=1.0，指数位值 = 0 + 127 = 127，127 << 23 = 0x3f800000，正是1.0的单精度位表示。

3. 当 x >= -149 时：返回非规格化浮点数表示

if(x >= -149) return 1 << (x + 149);

• 当 x < -126 时，规格化浮点数无法表示（因为最小有效指数是-126），此时使用非规格化浮点数。

• 非规格化浮点数的规则：指数位全为0，实际指数固定为 -126（而非 指数位值 - 127），有效数字为 0.frac（无隐含的1）。

• 对于 2^x，需转换为 0.frac × 2^(-126) 的形式：

  • 2^x = 0.frac × 2^(-126) → frac = 2^(x + 126)（frac是23位整数，表示小数部分）。
  • 由于 frac 需存储在23位尾数位中，x + 126 需满足 0 <= x + 126 <= 22（即 x >= -126 不成立，且 x >= -149，因为 -149 + 126 = -23？这里修正：x + 126 是 frac 的指数，frac 是2^k，k需在0~22之间才能用23位表示，因此 x + 126 >= 0 → x >= -126 不成立，而 x + 126 >= -23 → x >= -149，此时 frac = 2^(x + 126) = 1 << (x + 126)，而尾数位直接存储 frac，因此整体位表示为 frac（指数位全0，符号位0）。

  例如：x = -127 时，2^-127 = 0.5 × 2^-126，frac = 0.5 × 2^23 = 2^22，x + 149 = -127 + 149 = 22，1 << 22 = 4194304，正是该值的尾数位表示。

4. 当 x < -149 时：返回0

return 0;

• 当 x < -149 时，2^x 过小，即使非规格化浮点数也无法表示（此时 frac 会小于1，无法用23位整数存储，只能取0）。
• 浮点数0的位表示是：符号位0、指数位全0、尾数位全0，即 0x00000000。