随便写写
datalab 上压 ops 是一件比较毒瘤，在某些人眼里十分无聊的事情，不过我本人倒是乐在其中。前前后后重复"登顶-被超"的流程大概三四次，而几乎每次(除了最后一次)我所做的只是把之前所想到的优化但懒得写的部分写了出来，而也能比第二少 10ops 左右。正如某树洞所说，这个过程就如同一次次挑战人类极限(或许也不是人类？)。回顾一下，整个过程确实挺有趣的。
本人所写的代码会以附件形式在本文文末给出。这样做是为了降低直接通过搜索引擎搜索到的可能。希望正在看本文的你已经做过 datalab 了。
掩码显然是 datalab int 部分不可缺少的部分。利用掩码以及 (a&mask)|(b&!mask) 这样的语句可以实现逻辑判定的功能。那么构造掩码的方法就很重要了。算数右移是把双刃剑，有的时候会给你高位带来不必要的 1，有的时候这个 1 又是可以利用的。使用 1<<31>>31 可以直接构造一个全 1 的掩码，同理使用 x>>31 可以根据 x 的符号构造掩码。
当然，我们发现上边的式子需要的 ops 太多了。实际上我们可以做一些奇怪的优化，把式子变成 (mask&(a-b))+b，在某些题目中公式化简后有奇效。
对于左右移，除了通常想到的逻辑右移和算数右移的差异外，还有一个很有趣的点，是移动位数过大时会发生什么。形如 a>>k 的式子，当 k 不在 [0,32) 时，在 C 语言中属于 UB，尽管在通常情况下，其等价于 a>>(k%32)。这同样也是把双刃剑。在 rotateRight 中，需要用到 x<<(31-k)<<1 以计算 x<<(32-k) 的低 32 位(尽管最终并不会比直接构造 32-k 计算消耗的 ops 多)。在较少 ops 的方案中，有不少是把某些奇怪的 x 作为移动位数的，例如 counter1To5 中所有小于 5ops 的做法。结合这个对 32 取模的性质可以构造出更好玩的东西。在 satAdd 中，就用了 (x>>mask)==(mask?(x<0?-1:0):x)，其中 mask 是全 1 或 全 0 的掩码。
在最终实现里头，整数部分有不少方案看起来过于 trick。想出这种方案对人类是不小的挑战。我们当然可以让机器替代一些思考的过程，使用机(chao)器(suan)暴力求解。
在最初的设计方案里头，我意识到大部分的任务中只需要很少的中间变量(即大多数的中间计算结果只会被用一次)。这是特点能利用好能起到不少剪枝效果。因此我设计了一个 stack machine。这个 machine 中有三种指令：向栈中添加常数、将栈顶存到存储或从存储取到栈顶、数值运算指令。这个模型显然足够抽象 int 部分的计算模型了。之后我们指定几个测试数据，使用 dfs 枚举每一条指令，同时模拟其中的几组数据的运算，如果能完全匹配则是一种解。我们考虑一下这种方案的优缺点。这种方案可以很好地对存储量进行约束，同时可以通过简单的栈深度剪枝来保证搜到的都是有效解(结束后每个变量都被用到)。但这种方法在其他的剪枝方案上不具有优势，以至于最终效率并不好。由于栈语言的特点，这个方法并不能有效减少常数运算(例如会算 1+1 这种没有什么意义的东西)，同时也不能优化掉可交换运算的。对于这种情况，我使用了一直比较 trick 的方案，强制要求第一组数据的可交换运算必须满足 a<=b，但这仍有两个缺点。一是对于特点输入，值相等的情况并不能有效剪枝，同时最终运算的指令可能会在比较靠后的地方，导致搜了不少无效分支才触发剪枝条件(而这次剪枝也只会中断当前子树的搜索，造成剪枝的数据可能由很早的指令产生，因而会有特别多的分支在同一个地方多次触发剪枝)。还有就是这个 stack machine 的指令数不能和 ops 建立直接的关系(相当于使用数字，赋值，变量都要算 ops)。
不过，即使是这样，也足够搜出来不少解了。这种搜索方法，搜索时间于常数集合大小关系指数相关，而我个人认为不太会出现奇怪的常数。我大多数情况下只使用了几个常数。单线程下半小时内就能搜出 counter1To5 的两种 4ops 解法。
当然，直接单线程显然不好，这样根本没必要开超算。所以我立刻大力 fork 改了个多进程出来。由于我不想写成广搜形式，因此最初采用了十分谔谔的做法。我直接把搜索树第一层的所有分支拆出来，之后平均分给每个进程。然而，在 stack machine 中，第一层的有效操作只有加载常数，因此很多进程根本没有任务，我的这个程序在 36 核的机子上跑出了 8 进程！不过这也足够在 5 分钟内跑出 counter1To5 所有 4ops 解了。
这种问题还是要改的。最终我借助 csdn 上学到的申必方法，糊了个三脚猫多进程。考虑到多进程通信开销的问题，我最终设置了一个 deep，表示在这个深度上的搜素节点要做检验进程数的操作，如果不足就开一个进程执行任务。效果似乎还不错，利用率能到 95% 以上。
剪枝问题怎么解决呢。最终我又不得不写了一个一开始就被我抛弃的方案：基于表达式计算的机器。每一行指令都是一个可计算的单运算符表达式。使用到的数字可以是常数，也可以是之前某条语句的计算结果。这种方法可以很好地过滤常数计算，处理交换重复，也可以完全一一对应 ops。同时借助稍微麻烦一点的引用计数，也可以解决无效方案以及变量使用数的问题。RISC 和 CISC 之争，CISC 大获全胜。
利用一些人类智慧，例如猜测某些大概率用到的中间变量并作为输入给出，可以搜出来一些操作数比较多的方案。最终使用这一套工具，我跑出了 sm2tc 和 satAdd 的最优解。通过观察这些题的搜索结果，给了我一些解决其他问题的思路。在发现榜上出现了 counter1To5 3ops 解法后，我增大了常数集合，也很快就搜出来了解。
那能不能让常数集合大小不影响搜索效率
当然可以！我们发现，除了移位运算，其他所有的运算都可以简单地在 O(32) 内化成 SAT 问题。移位运算大概可以在 O(32^2) 内转化。那么我们在搜索的过程中，只需要搜索每个运算，以及是使用变量还是常数即可，剩下的问题交给 SAT Solver 求解即可。当然，代码肯定会比较复杂，而且由于求解和转换本身的效率因素，以及大多数奇怪的常数很难被用到，这种搜索方案不一定比直接大力枚举常数更好。当然，复杂度上界大概也是更劣的(至少和选择的常数无关了，不是吗)。感兴趣的读者可以自己试试，欢迎交流。
浮点类比整数类放宽了不少。而开放了switch的使用，更是减少了等于比较符号的使用。而对于浮点阶码这种本身范围就很小的数，我们可以直接暴力枚举所有情况来做所有的大于小于之类的比较。
浮点中还有一个小 trick。当你要使用一个负常数的时候，你会发现负号也会占一个 op。然而我们只需要手动算一下 hex (即补码)替代直接使用负数即可。
另外地，IEEE 浮点数的设计有个很有趣的一点，最大的非正规数多一点点后的正规数，和直接给原数字的 binary 表示加一是一样的。用这个特点，我们不需要单独处理翻倍以及折半时正规数和非正规数转换的问题。省了不少事。
那再考虑，不少任务中，使用了两次 & 运算以取出阶码和尾数。能不能利用 while 循环合并成一个 op？
当然可以。我们考虑引入一个 step。最外层是一个 while 循环，内部判断 step，决定是计算阶码还是位数，之后把需要计算的数字加载到一个固定的地方。加载后，再执行 & 操作。计算完成后，再根据 step 判定应该把变量赋给谁，最后改 step。当然，使用这种方法我们还可以简单地只用减法实现加法，左移等操作。
等会，这个 step，他不就是 pc 吗？没错，这个 step 可以随意跳转，而这个计算操作可以是有很多种，我们已经用 k ops 造了一个图灵机，其中 k 是可以执行的运算种数。那借助这个，我们又可以进一步乱搞了。
我们考虑按位计算。显然我们可以用 32 次循环以及一个 & 运算完成一个数字的二进制拆分(0 和非 0)，并把他们放入不同的变量内。之后大多数的运算都可以拆成一堆按位的 switch/if 嵌套。如果需要返回一个数字，我们可以先构造一个 0xff 之类的数，之后根据每一位的值，& 一个数字就可以实现该位的置 0 或置 1。借助这些操作，已经可以将所有浮点部分的任务做到 1op 了。
然而没完。当你发现 btest 所有数据都过了后，driver.pl 根本过不去。总共会有三种地方可能卡到这种解法：bddchecker 最多运行一分钟，一个 while 循环最多进入 70 次，内存超限。由于 cbit 是一个 32bit 的程序，所以最多只能拿到 4G 的内存，复杂做法很容易就炸了。SAT 求解器确实很难避免这种情况。因此我总共做了三种操作，主要思想还是约简赋值和分支数量，当然事先要尽量保证原始算法足够精简。一是削全加器，注意到有不少地方可以保证一定不会进位，或者某一个加数一定是 0，这种情况我们就可以阉掉一部分的全加器。二是使用倍增，我在移位操作部分使用了倍增，减少了不少的赋值数。三是妥协，float_f2i 在用了这两种优化后仍然不能过，不得不把取负的地方删掉，最终多了一个 op。
这篇文章主要记录了我在做 dalalab 时的一些有趣的想法和做法，并没有针对具体的 task 写。要感谢的人有不少，我也懒得列了。希望读完本文的各位也能有点想法。
压 ops 的行为本身或许除了好玩外也没有什么其他意义，不过这中间的探索还是很有意思的。
以下我在做 datalab 中使用到的几乎所有的文件。
日期： 2021-10-01