CS:APP Data Lab实验

本文是CS:APP学习笔记的一部分：

• Data Lab
• Bomb Lab
• Attack Lab
• Architecture Lab
• Cache Lab
• Shell Lab
• Malloc Lab
• Proxy Lab

相关的代码都放在了GitHub下了：RayZhang13/CSAPP-Labs

久仰《深入理解计算机系统CS:APP》的大名，可惜之前自己一直是个懒狗，一听有人抱怨难就识趣的开溜了，哦那个时候编程也没开窍啊，那没事了…

原版视频在这里，如果英语好的小伙伴可以试试呢：

2015 Fall: 15-213 Introduction to Computer Systems

网课界面还是做的相当好的，幻灯片、摄像头、投影都可以按照时间轴同步播放，体验极佳：

总之这下得好好的把CS:APP这本书过下来，首先得感谢B站上的CMU课程视频和相关的翻译，链接在这里：

【精校中英字幕】2015 CMU 15-213 CSAPP 深入理解计算机系统 课程视频

字幕里面看起来还是有少许错误，这是作者的翻译项目GitHub链接：中英双语字幕精校版 CSAPP CMU 15-213 课程 2015 Fall 视频翻译计划，那是真的牛皮👍

另外关于习题课Recitation，这里也有视频，一条龙了属于是（可惜没有中文字幕，好消息是有英文字幕）：

2015 CMU 15213 CSAPP 深入理解计算机系统 习题课视频

准备

对应课程

这次的Data Lab作业，如果是自学，在刚才的B站课程中，你需要完成P2~P4的课程学习掌握相关的概念。

课程文件

相关的作业可以在CMU的官网上找到：

Lab Assignments

在Data Lab一栏里面，我们可以查看相关文件，例如：

• README文档

• Writeup PDF说明材料

• 自学材料 最重要的作业文件Self-Study Handout

下载后并解压的文件如图所示：

关于接下来的使用可以看一下文件夹里的README，配合刚才的PDF食用更佳。

使用环境

我们主要通过btest、dlc、fshow、ishow和driver.pl这几个文件来完成作业相关的样例测试和打分。

看起来macOS对这里头的32位代码检查工具dlc支持有亿点点小问题，所以我们还是整一个正经的Linux环境吧~

我在这里使用了Arch Linux在VMware下的虚拟机：

使用的GCC版本为11.1.0：

我们将文件传到虚拟机里面，作业都在bits.c文件里，我们按照要求完成代码保存即可。

（理论上）写完代码之后在文件夹下运行make之后，例如调用driver.pl就可以完成代码检查了。如图：

这里我们每道题都还没动，所以最后的评分都是0分，也算是挺智能的打分系统了hhh

可能的坑

先说结论，建议将Makefile中的参数稍加修改成如下形式：

64位系统

我们的Linux系统是x86_64的，如果无法成功make可以考虑将Makefile里面的gcc参数中的-m32修改为m64。

未定义行为

根据Wikipedia中的定义，在计算机程序设计中，未定义行为（英语：undefined behavior）是指执行某种计算机代码所产生的结果，这种代码在当前程序状态下的行为在其所使用的语言标准中没有规定。常见于翻译器对源代码存在某些假设，而执行时这些假设不成立的情况。

例如，在整数运算过程中，对一个整型进行大于31位的移位就是一个未定义行为，编译器可以自由发挥进行优化，这点在Recitation习题课上16:10时刻，也被提及了。

另外，需要说明的是，在C语言中带符号的整数溢出是未定义行为，编译器会假设不会发生整数溢出这样的情况，因此编译时的可能会做出特殊的优化。我们不能理所应当的认为由于所以处理器都使用二进制补码表示法就直接对数字进行随意的溢出运算，这样会导致奇怪的结果。

而在Data Lab中，由于我们经常性的需要对一个32位的整型进行加法、与运算、或运算等，我们可能有意或者无意的会利用到相关的补码运算性质，可能会发生带符号整型溢出这样的情况，这点是我们需要警惕的。

为了让程序严格遵守正常的数学逻辑，在溢出后保证截断行为，将溢出位进行抛弃，我们需要在Makefile中的gcc参数下添加-fwrapv。

在知乎上我也找到了做Data Lab时有类似同学的迷惑：为什么只是加了printf得到的结果就不同了？

我在自己的机器上也做了几个小实验，我分别运行两次这样的代码，结束后都使用GCC不带参数进行编译：

//代码A
#include<stdio.h>
int main(){
  int x = 0x80000000;
  printf("%d\n", !(x + x));
  return 0;
}

//代码B
#include<stdio.h>
int main(){
  int x = 0x80000000;
  int y = x + x;
  printf("%d\n", !y);
  return 0;
}

结果为：

按照我们的理解，0x80000000对应的二进制是1000 0000 0000 0000 0000 0000 0000 0000，如果我们将两个0x80000000相加，我们就会发生溢出，理论上说去掉溢出的进位，我们会得到结果0。

但是为什么当我们进行是否为0的判断时，两端看起来功能完全一致的代码结果却不同呢？

我们使用GDB分别对两次生成的执行文件进行反编译，为了清晰Intel和AT&T的语法都打印了一下，结果为：

在代码A的反汇编过程中，我们看到执行时我们甚至都没有使用add命令进行加法运算，简单的过程大概就是在<+8>位置将0x80000000写进内存地址rbp-0x4的4字节空间里了（相当于完成了int x = 0x80000000;）（PS: DWORD代表双字，也就是4字节，[]中存储的是地址），然后在<+15>位置将地址里面存储的0x80000000直接和0x0使用cmp指令进行了比较，然后就出了结果。

大致猜测，编译器觉得如果需要确定x + x是否是0，编译器默认觉得不会发生溢出这种蠢事，既然我们x + x对中间过程又没啥要求，干脆不算了，就直接优化成了x是否为0，而我们都知道0x80000000不是0，所以直接打印出了一个false。

而在代码B的反汇编中，在<+8>位置将0x80000000写进了内存地址rpb-0x8的4字节空间里，随后在<+15>位置将rpb-0x8里面的数据放入累加器eax中，并在<+18>使用add eax, eax自己加了自己一次，随后在<+20>将eax中加出来的结果放在了新的4字节空间rbp-0x4里面（相当于完成了int y = x + x;），最后在<+23>位置使用cmp指令比较了rbp-0x4里面存储的数字（加法溢出后应当是0x0）和0x0，那自然是true。

综上，我们发现只有在代码B中，程序才认真的执行了加法运算操作，而在代码A中直接发生了优化，给出了不同的答案。这也警示我们需要注意带符号整型的溢出问题，这是一个未定义行为(UB)，我们不能理所因当的觉得程序会对应的做出溢出后的截断等操作，事实上编译器可能会自己偷偷的做出了意想不到的优化。

使用建议

评分工具

在bits.c文件中，给出了每道题目的相关要求，下方的函数是你需要做的作业，这里没做的情况下，老师随便填了一堆return xxx，这显然是不可能对的。

例如：

第一题，题目名字叫做bitXor，要求实现两数按位的异或，要求为：

• 可以使用的运算符限制在~和&
• 运算总步数限制在14次
• 整型常数最大只能用到0xff，不能用0xffffffff这样的数；禁止全局变量减少总步数偷鸡（最顶上还有点条件别漏看了）

只有同时满足了答案的正确性和限制条件，这道题才会被判定为得分。

driver.pl到时候运行的时候得分会全部显示出来，像这样（当然这是我做完后的样子了）：

那么如果好巧不巧，你的做了某道题但是在对应的Rating里面看不到得分（也就是0），说不准旁边还爆出了几个Error，那该怎么办呢？

例如：

其实大可不必摸瞎排查问题，通不过总评分测试driver.pl，说明我们的答案的正确性和限制条件可能没有得到满足，这个时候我们调用btest工具，进行正确性分析：

他会把每道题目带入样例里面没通过的情况打印给你看，信息相当详细，精确到传入参数是什么，你的答案是什么，正确答案是什么。也是方便你进行排查错误。

面对偷鸡方法，我们还有dlc进行条件检查限制，比如在第一题bitXor中，我们直接使用return x ^ y;，这样的话可以满足答案正确性，却没有满足限制条件。例如修改后运行：

我们看到driver.pl中第一题仍然没有得分，但是调用btest已经成功通过第一题了，这个时候我们调用./dlc -e bits.c，就能看到问题：

对于满足正常限制条件的题目，dlc会正常打印出步数相关信息，但是对于不满足限制条件的会直接警告，例如这里第一题：dlc:bits.c:146:bitXor: Illegal operator (^)，你不应该使用^运算符。

通过这三款工具我们就能很好的应对做题中的问题了，并能快乐的开始调试了。

当然，需要说明的是，测试样例只能证明你是错的，通过所有的测试样例却不一定能说明你是做对的。做题时一定要大胆假设小心求证。

做题小工具

此外，文件夹里还提供了两款小工具，分别是ishow和fshow。

ishow功能很简单，每次你传进去一个数字，他就能给你显示这个数的16进制表示形式，作为无符号数是多少，有符号数是多少：

fshow的功能也是类似的，你传入一个数字，他会将它转成32位二进制形式并套用在单精度浮点数的模版上，然后生成一个对应的浮点数：

题目

整型运算

首先还是贴一下做题的约束和规范，这块你在bits.c文件的头部也能找到：

INTEGER CODING RULES:
 
  Replace the "return" statement in each function with one
  or more lines of C code that implements the function. Your code 
  must conform to the following style:
 
  int Funct(arg1, arg2, ...) {
      /* brief description of how your implementation works */
      int var1 = Expr1;
      ...
      int varM = ExprM;

      varJ = ExprJ;
      ...
      varN = ExprN;
      return ExprR;
  }

  Each "Expr" is an expression using ONLY the following:
  1. Integer constants 0 through 255 (0xFF), inclusive. You are
      not allowed to use big constants such as 0xffffffff.
  2. Function arguments and local variables (no global variables).
  3. Unary integer operations ! ~
  4. Binary integer operations & ^ | + << >>
    
  Some of the problems restrict the set of allowed operators even further.
  Each "Expr" may consist of multiple operators. You are not restricted to
  one operator per line.

  You are expressly forbidden to:
  1. Use any control constructs such as if, do, while, for, switch, etc.
  2. Define or use any macros.
  3. Define any additional functions in this file.
  4. Call any functions.
  5. Use any other operations, such as &&, ||, -, or ?:
  6. Use any form of casting.
  7. Use any data type other than int.  This implies that you
     cannot use arrays, structs, or unions.

 
  You may assume that your machine:
  1. Uses 2s complement, 32-bit representations of integers.
  2. Performs right shifts arithmetically.
  3. Has unpredictable behavior when shifting if the shift amount
     is less than 0 or greater than 31.


EXAMPLES OF ACCEPTABLE CODING STYLE:
  /*
   * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31
   */
  int pow2plus1(int x) {
     /* exploit ability of shifts to compute powers of 2 */
     return (1 << x) + 1;
  }

  /*
   * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31
   */
  int pow2plus4(int x) {
     /* exploit ability of shifts to compute powers of 2 */
     int result = (1 << x);
     result += 4;
     return result;
  }

大概意思就是：

• 按照题目要求给出的允许符号完成，并且要在规定步数内。

• 运算中带入的整型常数数字最大是0xff。

• 可以分行多步完成。

• 不要使用全局变量偷鸡。

bitXor按位异或

/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */

这道题目要求我们通过~和&来完成两数的按位异或。

根据定义：

$A \oplus B\\=(\neg A \wedge B) \vee (A \wedge \neg B)\\=\neg(\neg((\neg A \wedge B) \vee (A \wedge \neg B)))\\=\neg(\neg(\neg A \wedge B) \wedge \neg(A \wedge \neg B))$

最后一步我们使用了德摩根律：$\neg(A \vee B) = \neg A \wedge \neg B$

这是一位的运算，推广到按位运算上也是一样的操作，因此：

int bitXor(int x, int y) {
    return ~(~(~x & y) & ~(x & ~y));
}

tmin求最小带符号整数

/*
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */

最小带符号整数应当是$-2^{31}$，二进制补码表示为1000 0000 0000 0000 0000 0000 0000 0000，16进制为0x80000000。

很容易的我们得出，直接将1左移31位即可实现。

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

isTmax判断最大带符号整数

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

如果输入参数是最大带符号整数$t_{max}=2^{31} - 1$，就应当返回1，否则返回0。

要完成这道题目，我们最好还是研究一下$t_{max}$这个数字有啥特殊之处，他的16进制表示为0x7fffffff，二进制表示为0111 1111 1111 1111 1111 1111 1111 1111。

我们注意到，这个数，如果我们对它进行加一，它就变成了$t_{min} = -2^{31}$，二进制为1000 0000 0000 0000 0000 0000 0000 0000，16进制为0x80000000，恰好为原数$t_{max}$的翻转（每一位都翻过来了）。这个性质很少见，但是还有一个例外，那就是-1也满足这个性质，他的二进制是1111 1111 1111 1111 1111 1111 1111 1111，16进制是0xffffffff，如果我们对-1加一，就得0x0，也刚好是翻转。

我们需要做的事情有两件：

• 判断参数满足性质（加一后是自身的翻转）
• 判断参数不是-1

判断两数是否相等，我们可以使用!(x ^ y)，只有两数每一位都相等，x ^ y两数异或的结果才可能是0，这个时候我们使用!判断此数是否是0即可，是0即返回1，否则返回0。

但是判断参数是否不是-1，我们无法使用!!(x ^ 0xffffffff)来实现，原因是存在限制最大计算常数只能是0xff，这个不合题意了。那我们直接判断x + 1是否不为0即可，也就是!!(x + 1)。

综上答案为：

int isTmax(int x) {
    return !(~x ^ (x + 1)) & !!(x + 1);
}

此外我们还可以利用的特殊性质包括但不限于：加一后乘二（或者说加一后加自己）是0，例外情况：0xffffffff。也就是!(x + 1 + x + 1) & !!(x + 1)。

P.S. 这里可能会遇到带符号整数溢出的情况，可能会发生结果和预期不符的情况，建议查看上方“准备”部分的填坑指南，添加上-fwrapv参数，然后再试一次。

allOddBits判定是否所有奇数位都是1

/*
 * 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
 */

题目要求我们判定是否所有奇数位都是1，满足则返回1，否则0。

这里我们要做的事情可不是简单的判断x是否和二进制1010 1010 1010 1010 1010 1010 1010 1010，16进制0xaaaaaaaa相等，这个数中间的0位是可以取1的。这里头的关系更像是判断一个包含的关系，也就是x作为位图是否包含0xaaaaaaaa中的所有位。

解决办法也比较简单，我们先进行x & 0xaaaaaaaa，如果x包含0xaaaaaaaa，那么显然x & 0xaaaaaaaa应当和0xaaaaaa相等。因此答案暂时就是!(x & 0xaaaaaaaa) ^ 0xaaaaaa。

但是按照题意，0xaaaaaaaa我们不能直接使用（常数大小限制在0xff），得造出来，其实这也简单，我们直接通过移位相加把0xaa变成0xaaaa，再同样的方法将0xaaaa变为0xaaaaaaaa。

代码如下：

int allOddBits(int x) {
    int t = 0xaa;
    t = t + (t << 8);
    t = t + (t << 16);
    return !((x & t) ^ t);
}

negate取相反数

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

这就是一个很著名的结论了，对于一个整型x，我们知道他的翻转~x应该会把他的每一位都翻过去，也就是0变1，1变0。

如果我们将x和~x相加，我们就会得到一个所有位都是1的二进制数，也就是1111 1111 1111 1111 1111 1111 1111 1111，16进制为0xffffffff，我们也称这个数叫做-1。

因此结论就是x + ~x = -1，稍加变化我们就得出了-x = ~x + 1。

代码如下：

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

isAsciiDigit判断ASCII码是否是数字

/* 
 * 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
 */

ASCII码如要表示'0'~'9'，那对应的数字应当在0x30~0x39的范围内，如果x在范围内则返回1，否则返回0。

0x30~0x39的范围内的数在形式上大致满足0x0000003?的形式，二进制满足0000 0000 0000 0000 0000 0000 0011 ????的模式。

我拿到这道题目首先想到的是两个问题（假设我们从右向左开始数数，最右位为第0位）：

• 确定第4位到第31位读出来的数等于3
• 确定第0到3位读出来的数，落在0~9的范围内。

完成第一个目标还算简单，首先我们把左侧的这个数通过右移取出来，也就是x >> 4，如果要我们判断他是否是3，我们只需要!((x >> 4) ^ 3)即可。

关键是完成第二个目标，也就是判断x的右侧4位二进制是否落在0~9的区间里，首先我们可以通过x & 15（也就是和1111取与）的方式取出最右侧4位二进制，在这里我们假设他是b。

这里我们将所有可能的情况列出，并绘制卡诺图。

得出的结论就是只要第3位是0或者第1第2位同时为0即可，任选其一即可。

表示成代码就是!(b & 8) | !(b & 6)，8的二进制是1000，如果b & 8为0，说明第3位是0。同理6的二进制是0110，如果b & 6为0，说明第1第2位同时是0。两个条件满足其一即可。

综上代码为：

int isAsciiDigit(int x) {
    int a = x >> 4;
    int b = x & 15;
    return (!(a ^ 3)) & (!(b & 8) | !(b & 6));
}

这里看到网上有更加简单的做法：

主要思路可以用逻辑运算表示，(x - 0x30 >= 0) && (0x39 - x) >=0，而-x在刚才的题目中的结论可以表示为~x + 1。

关于如何判断一个数t是否大于等于0，我们只需要检查的他的符号位就可以了，也就是看他的第31位是不是0，我们通过!(t & (1 << 31))即可完成，这里就不赘述了。

所以代码如下：

int isAsciiDigit(int x) {
  /* (x - 0x30 >= 0) && (0x39 - x) >=0 */
  int TMIN = 1 << 31;
  return !((x + ~0x30 + 1) & TMIN) & !((0x39 + ~x + 1) & TMIN);
}

但是这种做法是否存在溢出的问题，也是值得讨论的。如果看看下面的“isLessOrEqual判断小于或等于关系”，希望能给你一些启发。

conditional实现三元表达式

/*
 * conditional - same as x ? y : z 
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */

如果x为0我们就取z，否则就取y，这就是三元表达式的简单逻辑。

我们知道一个数和0xffffffff进行与运算还是自己，和0x0进行与运算就变成了0，利用这一点来展开。

这里是我自己的思路：

通过这样的方式，我们确定了g(x)的具体表达式，带入后得到代码：

int conditional(int x, int y, int z) {
    int a = ~(!x) + 1;
    int b = ~a;
    return (b & y) + (a & z);
}

当然啦，(b & y) + (a & z)也可写作(b & y) | (a & z)。

isLessOrEqual判断小于或等于关系

/*
 * isLessOrEqual - if x <= y  then return 1, else return 0 
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */

如果x <= y就返回1，否则返回0。

这道题目，看起来可以简单演变成判断y - x >= 0，然后顺利的演变成y + ~x + 1 >= 0，然后快进到判断符号位。

但是这里还是有例外，举个例子，极端情况下，我们将x取为$t_{min}=-2^{31}$，将y取为$t_{max}=2^{31}-1$。这个时候x为0x80000000，y为0x7fffffff，如果我们尝试进行y - x（也可以说成是y + ~x + 1），答案会是-1，而我们在实际运算时知道这个答案是$(2^{31}-1)+2^{31}$，是个正数，换句话说y - x发生了溢出导致了不准确，溢出的部分是$2^{31}$。

同理，我们将x, y颠倒，得出的结论也是错误的，事实上，如果$y-x\geq2^{31}$或者$y-x \lt -2^{31}$就会发生溢出错误。会发生正数变负数，负数变正数的尴尬情况。

解决方案自然就是特殊讨论，我们直接将异号的情况单独判断，如果x < 0 && y >= 0，直接返回1；反之x >= 0 && y < 0直接返回1，正负的探讨可以直接通过符号位来确定。通过同号比较，我们将y - x的范围削减到$-2^{31} + 1 \leq y-x \leq 2^{31} - 1$，满足了要求。

取出一个数t的符号位方法很简单，t >> 31 & 1即可，&1的原因是对于1在最左侧开头的数，我们执行算术右移，会把1填充进来，最后的结果是0xffffffff。如果我们要判断当前数字是否>= 0，直接使用!(t >> 31 & 1)即可，但是这么一想又何必&1呢，!(t >> 31)也不是不能用。

我们根据刚才的逻辑形成了这样的代码：

int isLessOrEqual(int x, int y) {
    int a = x >> 31;
    int b = y >> 31;
    return (!(!a & b)) & ((a & !b) | !(y + ~x + 1 >> 31));
}

根据这样的逻辑，如果x >= 0 && y < 0，那么!(!a & b)) == 0，后面的运算不管怎么样都是0（因为0&x=0必成立）。

如果不满足，则!(!a & b)) == 1，进入下一层判断，如果x < 0 && y >= 0，那么(a & !b) == 1，那么答案就是1（因为1&(1|x)=1必成立）。

如果还不满足，则(a & !b) == 1，最后的决定权交由y + ~x + 1 >= 0（因为1&(0|x)=x必成立）

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 
 */

这里题目要我们实现一个逻辑非，如果x != 0就返回0，否则返回1。

那么数字0他有什么特殊的性质呢？

在CMU的网课里，其实在幻灯片里面也有谈及，具体位置在P3的1:14:30时刻，提出了除了0以外的数字都满足(x | -x) >> 31 == -1，也就是(x | (~x + 1)) >> 31 == 0xffffffff。而只有0计算出来是0（(0|0) >> 31还是0）。

判断一个数是0x0还是0xffffffff，我们只需要和0x1进行与运算，把最右一位取出来取反即可。

利用这一点，我们完成如下代码：

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

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
 */

根据题意，例如：

5可以表示为二进制0000 0000 0000 0000 0000 0000 0000 0101，但是在符号为保留的情况下，我们可以直接表示为0101，也就是4位。

-5可以表示为二进制1111 1111 1111 1111 1111 1111 1111 1011，但是在符号位保留的情况下，可以直接表示为1011，还是4位。

我们大致总结出了如下的规律：

• 如果x < 0，则x二进制开头为1，我们需要寻找的是从左到右的第一个0的位置，然后加一来表示一位符号位填充。
• 如果x >= 0，则x二进制开头为0，我们需要寻找的是从左到右的第一个1的位置，然后加一来表示一位符号位填充。

换句话说，如果x < 0，我们对x全部翻转，变成~x。然后所有的数字都是0开头了，我们统一遵守：

从左到右的第一个1的位置，然后加一来表示一位符号位填充。

关于如何实现翻转的使用的是这个，可以仔细体会一下，其实原理和上方那个“conditional实现三元表达式”类似：

int sign = x >> 31;
int x = (sign & ~x) | (~sign & x);

关于寻找最右侧的1，我们采用二分来进行：

• 先判断32位的x的左半侧有没有1？有就先+16，然后将数字左半边移到右对齐；否则，说明没有16位，不移位，直接研究右半边。（接下来研究x最右侧16位就相当于研究原数的左半侧/右半侧）
• 先判断16位的x的左半侧8位有没有1？有就先+8，然后将数字左半边移到右对齐；否则，说明没有8位，不移位，直接研究右半边。（接下来研究x最右侧8位就相当于原数某一半的左半侧/右半侧）
• …以此类推
• 最后还要加上一位符号位

代码实现如下：

int howManyBits(int x) {
    int sign, b16, b8, b4, b2, b1;
    sign = x >> 31;
    x = (sign & ~x) | (~sign & x);
    b16 = !!(x >> 16) << 4;
    x = x >> b16;
    b8 = !!(x >> 8) << 3;
    x = x >> b8;
    b4 = !!(x >> 4) << 2;
    x = x >> b4;
    b2 = !!(x >> 2) << 1;
    x = x >> b2;
    b1 = !!(x >> 1);
    x = x >> b1;
    return b16 + b8 + b4 + b2 + b1 + x + 1;
}

浮点计算

关于浮点计算题的具体规则和约束如下：

FLOATING POINT CODING RULES

For the problems that require you to implement floating-point operations,
the coding rules are less strict.  You are allowed to use looping and
conditional control.  You are allowed to use both ints and unsigneds.
You can use arbitrary integer and unsigned constants. You can use any arithmetic,
logical, or comparison operations on int or unsigned data.

You are expressly forbidden to:
  1. Define or use any macros.
  2. Define any additional functions in this file.
  3. Call any functions.
  4. Use any form of casting.
  5. Use any data type other than int or unsigned.  This means that you
     cannot use arrays, structs, or unions.
  6. Use any floating point data types, operations, or constants.


NOTES:
  1. Use the dlc (data lab checker) compiler (described in the handout) to 
     check the legality of your solutions.
  2. Each function has a maximum number of operations (integer, logical,
     or comparison) that you are allowed to use for your implementation
     of the function.  The max operator count is checked by dlc.
     Note that assignment ('=') is not counted; you may use as many of
     these as you want without penalty.
  3. Use the btest test harness to check your functions for correctness.
  4. Use the BDD checker to formally verify your functions
  5. The maximum number of ops for each function is given in the
     header comment for each function. If there are any inconsistencies 
     between the maximum ops in the writeup and in this file, consider
     this file the authoritative source.

在浮点计算题中，我们几乎没有特别严苛的约束。if等语句也可放心使用，大常数也可以直接介入运算。

这里为了对照方便，我直接将维基百科上的表放这里以供实时参考。

类别	正负号	实际指数	有偏移指数	指数域	尾数域	数值
零	0	-127	0	0000 0000	000 0000 0000 0000 0000 0000	$0.0$
负零	1	-127	0	0000 0000	000 0000 0000 0000 0000 0000	$−0.0$
1	0	0	127	0111 1111	000 0000 0000 0000 0000 0000	$1.0$
-1	1	0	127	0111 1111	000 0000 0000 0000 0000 0000	$−1.0$
最小的非规约数	*	-126	0	0000 0000	000 0000 0000 0000 0000 0001	$±2^{−23} × 2^{−126} = ±2^{−149} ≈ ±1.4×10^{-45}$
中间大小的非规约数	*	-126	0	0000 0000	100 0000 0000 0000 0000 0000	$±2^{−1} × 2^{−126} = ±2^{−127} ≈ ±5.88×10^{-39}$
最大的非规约数	*	-126	0	0000 0000	111 1111 1111 1111 1111 1111	$±(1−2^{−23}) × 2^{−126} ≈ ±1.18×10^{-38}$
最小的规约数	*	-126	1	0000 0001	000 0000 0000 0000 0000 0000	$±2^{−126} ≈ ±1.18×10^{-38}$
最大的规约数	*	127	254	1111 1110	111 1111 1111 1111 1111 1111	$±(2−2^{−23}) × 2^{127} ≈ ±3.4×10^{38}$
正无穷	0	128	255	1111 1111	000 0000 0000 0000 0000 0000	$+∞$
负无穷	1	128	255	1111 1111	000 0000 0000 0000 0000 0000	$−∞$
NaN	*	128	255	1111 1111	非全0	$NaN$
* 符号位可以为0或1 .

floatScale2浮点数乘2

/* 
 * 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
 */

题目的意思大概是传入的32位uf整型，我们应该视作他是单精度float的编码方式，基于这样的编码方式，我们将它乘2，还是以float的编码形式输出。如果编码是NaN，就直接返回编码。

除开NaN，对于任意$∞$的两倍也还是无穷，所以，我们可以认为NaN和$∞$直接返回自己就好了。两者的共同点是两者的有偏移指数exp都是0xff。关于偏移指数的获取，可以通过uf >> 23 & 0xff获得。

此外如果是当前浮点数是规约数，那么要乘2，我们只需要将exp加一即可，表示指数加一。也就是uf + (1 << 23)。

如果是非规约数，即exp为0，我们要乘2就应该将尾数位左移一位，即使尾数位以1开头，也是同样的操作，将1移入exp偏移指数中，代表变为了规约数。鉴于规约数的exp部分全部是0并无影响，我们其实可以考虑直接将整个数字进行左移，但是挤掉的符号位还是要补回来的。所以我们的表达式就变成了(uf << 1) + (uf & (1 << 31))。

因此，我们得到：

unsigned floatScale2(unsigned uf) {
    int exp = uf >> 23 & 0xff;
    if (exp == 0xff) {
        return uf;
    }
    if (exp == 0) {
        return (uf << 1) + (uf & (1 << 31));
    }
    return uf + (1 << 23);
}

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
 */

题目的意思大概是传入的32位uf整型，我们应该视作他是单精度float的编码方式，基于这样的编码方式，我们将它转成整数。（NaN和$\infty$直接返回0x80000000u）

关于精度损失问题，由于取整，小数点后的数据都不能留下，为了简单考虑，我还是偷懒了，直接向0进行取整，也就是直接省去小数点后的数。

首先我们提取出符号位，也方便了后续的操作。即int sig = uf >> 31 & 1;。

对于规约数来说，如果E > 31的情况下，1.x * 2^E位数超过32位，必然存不下，应当返回0x80000000u。

对于E < 0的情况，也没有啥好说的，1.x * 2^E全是小数，化为整数就是0。

有趣的地方在0与31之间，小数点具体是停留在23位数字的中间，因此我们要掠去小数点后的数字；还是需要继续向右多画几个0补齐32位呢？有趣的是数据是以1.xxxxx的方式存储的，因此数据实际上有24位，为了得到24位的数据，我们干脆先取出23位，再在左侧加上一个1，也就是uf & 0x7fffff | 0x800000。

因此我们以23为边界继续讨论，如果E <= 23说明小数点还停留在23位数字的中间（含边界）。

如果E > 23说明，我们需要多补几个0，干脆直接把数字左移exp - 23位然后取出右侧31位，补上一个符号位。

至于浮点数转整型溢出这种奇葩情况，我头实在太大，题目貌似也没说，算了别考虑了…

结果如下：

int floatFloat2Int(unsigned uf) {
    int res;
    int sig = uf >> 31 & 1;
    int exp = (uf >> 23 & 0xff) - 0x7f;
    int val = uf & 0x7fffff | 0x800000;
    if (exp > 31) {
        return 0x80000000u;
    }
    if (exp < 0) {
        return 0;
    }
    if (exp <= 23) {
        res = val >> (23 - exp);
        return sig ? -res: res;
    }
    res = val << (exp - 23);
    return sig ? -res: res;
}

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
 */

给了一个整数x，要我们使用浮点编码表示2^x。如果太小，直接返回0，太大直接返回$+∞$。

我们知道最小的非规约数只能表示到$2^{-149}$，因此如果比-149还小直接返回0。

在非规约数的范围内，也就是$-149 \leq x \lt -126$范围内，对于最小的非规约数，当x = -149时，1在尾数的最右侧，其他数字全部是0，非规约数每次乘二只需要左移即可，因此返回1 << (x + 149)。

接下来进入了规约数的范围，范围是$-126 \leq x \lt 128$，对于最小的规约数，有$1.0*2^{-126}$，此时偏移指数为1，规约数的计算满足1.x * 2^E，每次乘二只需要有偏移指数加一即可。因此返回(x + 127) << 23。

对于超出了规约数的范围，直接返回$+∞$即可，$+∞$的编码为0x7f800000。

因此我们有：

unsigned floatPower2(int x) {
    if (x < -149) {
        return 0;
    }
    if (x < -126) {
        return 1 << (x + 149);
    }
    if (x < 128) {
        return (x + 127) << 23;
    }
    return 0x7f800000;
}