ICS （计算机系统导论）课程中，第一个大作业 datalab 要求我们使用位运算实现一些操作。它的某些操作允许我们使用一般 C 程序的控制结构和大部分算术、逻辑、位运算，要求我们实现一些较为复杂的功能，要求“使用的操作符数目不超过某上界”。根据作业要求，之所以这么要求，是因为不希望同学们设计出过于糟糕的效率低下的算法。这毫无问题。
问题是，在提交网站上有一个排名表，排名依据是“使用的总操作符数目”。简单思考一下，就会发现这是一个非常愚蠢的评判标准（赋值和控制结构是免费的）。本文接下来的内容，就将展示为什么这个标准非常愚蠢、背离原意。
DISCLAIMER：今年的 datalab 已经 overdue。本文通过一定的设计，没有使用任何 datalab 的题目，没有给读者以任何代码级别的提示。本文作者相信本文对于解决 datalab 毫无用处；如果读者敢于用本文提交的方法进行提交，说明读者本来就会至少一种（正常的）解决方法。但，如果你正在、即将或者未来有可能做 datalab，我仍然不建议你阅读文章，防止破坏自己发现这个 exploit 的游戏体验。
为什么 op count 很垃圾？
假设我们要实现这么一个功能：
int f(int x) {
return 1<<x;
}一般正常人都会写出一个 1 op 的代码，就像上文展示的这样；但实际上它是可以 0 op 的。
int f_but_worse(int x) {
switch(x) {
case 0: return 1;
case 1: return 2;
case 2: return 4;
// etc. etc. etc.
default: return 0;
}
}注意到上述代码并没有使用任何操作符。根据 datalab 的评判标准，这确实是 0 op 的。我们知道，
- 0 op 可以实现和常数比较。
- 0 op 可以实现
!操作符。（提示：else是免费的。）
习题。使用这一方法，实现 1 op 的 negpwr2。
可以发现，所有确定的函数都是 0 op 的，因为你只需要打一个巨大无比的表。但这显然不能提交上去。那我们就要问：
教练，有没有更刺激的？
当然可以。假设我们有一个数字
x : unsigned，我们要把它的高 5 位视作一个下标 \(i\)，低 27 位视作一个长度为 27 的 01 串
\(s\)，然后我们要获取 \(s[i]\) 。我们会有这样的函数：
unsigned g(unsigned x) {
unsigned i = x >> 27;
unsigned s = x & 0x07FFFFFF;
return (s >> i) & 1;
}这个是 4 op 的。但由于它只使用了两种操作，我们实际上可以利用循环，复用操作，把它变成 2 op。
unsigned g_but_worse(unsigned x) {
// register files
unsigned t = 0;
unsigned shr0, shr1, shr2;
unsigned and0, and1, and2;
unsigned ret, hlt = 0;
unsigned i, s;
// clock
while(true) {
// ALU
and0 = and1 & and2;
shr0 = shr1 >> shr2;
// instruction memory
switch(t) {
case 0:
shr1 = x;
shr2 = 27;
and1 = x;
and2 = 0x07FFFFFF;
t = 1;
break;
case 1:
i = shr0;
s = and0;
shr1 = s;
shr2 = i;
t = 2;
break;
case 2:
and1 = shr0;
and2 = 1;
t = 3;
break;
case 3:
ret = and0;
hlt = 1;
break;
}
if(hlt) {
break;
}
}
return ret;
}由于已经上过了处理器架构，上文给出的注释是具有提示性的。
教练，有没有更刺激的？
上文只展示了一个简短的例子。
事实上，使用这种方法，我们可以把 C
中所有的控制结构都“编译”成上文这种指令集。你可以自己思考一下怎么处理
if 和 while。
习题。如果 switch
不可用，找一种方法来照样放 instruction
memory。（提示，你会需要很多变量。）
通过精心选取我们所使用的操作符种类，我们可以降低我们所需要的操作符数量。例如，
- 减法可以判断相等。
- 常数个减法可以完成加法。
- 常数乘 32 个加法可以完成左移。
- 常数乘 32 个加法和 &1 可以完成乘法。
- 右移和减法（各一次）可以完成无符号小于比较。
- 除法加查表可以实现右移；乘法和左移同理。
- 除法和减法可以实现取模。
- 常数次取模可以判断相等。
等等，等等。请读者自行证明以下结论：
命题。任何一段只使用了常数内存、符合CSAPP“浮点代码规范”的
C 代码都可以翻译成一段功能相同的 2 op 代码。其中，“浮点代码规范”是说没有
struct、数组、指针等高级东西，只有代数、逻辑、位操作符。
此处建议读者自行找出应该使用哪两个操作符。
如果读者已经自行实现了 float_i2f 和
float_f2i
，它们适用这里的条件。但由于评测机的限制（譬如，每个循环至多进入 70
次；例如，形式化验证工具只能运行 60
秒），其中一个并不能跑过去，需要额外再加一个运算符。
如果你真想去实现这两个函数，作为对照，我自己的版本它们加起来接近一千行。我手写了其中的至少四百行。
习题（编译原理）。写一个把上述代码编译成 2 op 的编译器。
教练，有没有更刺激的？
float_abs，优化的鼎盛。注意到这个问题不仅要求绝对值，还要对
NaN 返回本身。（这本身就有点蠢。）它有着很平凡的 2 op
的实现，但有办法可以让它 1 op。
再说下去就违反学术诚信原则了，因此我给出一些提示：这个已知两种解法，一种是使用某位运算，然后运算次数和整数位数（32）相关；另一种使用某种算术运算，运算次数和 32 无关。
教练，可是……这有啥用？
呃，并没有。
那你为什么要研究这个？
呃……
那你为什么要写这个代码呢？
呃……这么说吧，如果你看到一个很垃圾的规则，你是不是会想找出一个奇怪的 corner case 来 hack 掉它？
不想啊，你脑子有问题吧。
爬。
这个东西近似于行为艺术。我想通过这两段非常长的代码，来展示一个似乎很有道理的评判标准（op count）可以完全背离它的初衷（降低代码复杂性）。我的本意是通过排行榜上那个 bug 一样的数字来让大家停止浪费时间刷榜，但好像自己也落入到自己的批判的射程里面了（x）。
Anyway，我认为这种 exploit 式的优化，是对认认真真优化操作次数的一种 parody。由于不影响成绩，对我这种 exploit 的批判，完全可以打在“认真优化”上。我只不过是通过 exploit，来放大了这种效应。它和飞天面条之于宗教的关系有一些（勉强的）相似之处。