task1
相当于要把第一位取反。可以先把寄存器(1)取反，放到寄存器(2)。然后对寄存器(2)，先左移(63)位，再右移(63)位。利用自然溢出，就相当于只保留了最低位。
需要(3)次操作。
task2
考虑三个寄存器(x), (y), (z)。当我们说，对(x), (y), (z)进行“计算”时，表示的其实是对这三个寄存器里对应的值操作。
我们要求出(x+y)（也就是编号为(x)的寄存器和编号为(y)的寄存器里对应的值相加）。
先考虑不进位的加法，也就是异或。先令(z:=xoperatorname{xor}y)。然后再考虑进位的部分，它等于((xoperatorname{and}y)ll 1)。令(y:=(xoperatorname{and}y)ll 1)。我们惊喜地发现，问题就转化为了(y)和(z)的加法！并且，每次(y)一定会左移(1)位，那么至多(64)次之后，(y)就会变成(0)，此时加法就完成了！
每轮操作，根据当前轮数的奇偶性不同，考虑是用(x+y)还是(z+y)。相当于每隔一轮，(x), (z)这两个编号的含义会交换一下。这样的好处是避免了每一轮结束时我强行set x z，这样就多一次操作了。因为总轮数(64)是一个偶数，你会发现，最终答案一定存储在(z)的位置。
因为每轮需要用到xor, and, shl共三次操作，所以总共用到(3 imes64=192)次操作。实际可能更多或更少（例如最后一次左移可以不做）。
task3
依次考虑每一位（每次左移(1)位，再(operatorname{and} 1)。这个(1)可以提前预处理好，方法是not t t, shr t 63）。对当前位，得到的是一个(0)或(1)的数字。调用task2里的加法，让答案加上这个数字即可。每次加法不需要加(64)位，因为答案数字很小，只需要加到当前可能的最高位即可。
大约需要(1100)次操作。
另外，这个task也有一些奇妙方法，可以压到(300)次操作以内。具体见黄队的博客。
task4
考虑(xoperatorname{xor}y)的最高位，也就是(x), (y)第一个不同的位。如果我们能只保留这一位上的数字，不妨记为(z)。那么用(zoperatorname{and}x)，如果结果不为(0)，则(x>y)，否则(xleq y)。
于是问题转化为如何只保留一个数的最高位。
考虑如下的操作：
x|=(x>>1);
x|=(x>>2);
x|=(x>>4);
x|=(x>>8);
x|=(x>>16);
x|=(x>>32);
这样(6)次操作后，实现的效果是：(x)的最高位以下，全都是(1)。原理其实就是倍增法：先把最高位的下一位变成(1)，再用这两位一起去把下两位变成(1)，以此类推。另外，虽然看上去是(6)步操作，但实际实现时，每步操作需要(3)条指令，所以这个过程共需要(18)条指令。
用这个方法，我们可以先把(z)的最高位以下全都变成(1)。然后，我们用三次操作，令(z:=zoperatorname{xor}(zgg1))。这样就相当于只保留了(z)的最高位。拿新的(z)去和(x) (operatorname{and})。
最后判断结果是否为(0)，可以再用一次倍增法，把最高位的(1)（如果有的话）推向最低位，然后左移(63)位再右移(63)位，就能只保留最低位的值。
共需要(43)次操作。
task5
我们还是依次考虑每一位。维护一个当前答案。如果当前位是(1)，就令：( ext{ans}:= ext{ans} imes2+1)。
这相当于要实现一个三目运算符：如果条件为真，就令( ext{ans})等于(x)，否则令( ext{ans})等于(y)（这里(x), (y)，是一般性的表述。在这里就等于( ext{ans} imes2+1)和( ext{ans})）。然而我们没有( exttt{if})语句，如何实现三目运算符呢？
考虑如果条件为真，就构造一个全(1)的数（也就是(2^{64}-1)），这可以用task4里的倍增法来实现；条件不为真时，这个数自然为全(0)。然后用构造出的这个（全(1)或全(0)的）数，去(operatorname{and} x)。再将其取反，去(operatorname{and}y)。发现这两个结果，必有一个是(0)，另一个是我们想要的值，所以将它们(operatorname{or})起来，赋给( ext{ans})即可。
本task里，这个“条件为真”，就相当于当前位上的数是否是(1)。所以具体来说就是把当前位上的数，用倍增法铺满所有位即可。
这只是一个大致的思路，朴素实现的话操作次数比较多（(1600sim 1800)左右），需要做一些优化，例如：
- 从小到大考虑所有二进制位，对于第(i)位，( ext{ans})的位数一定小于等于(i)。所以不需要铺满所有(64)个二进制位，只需要把前(i)位铺满即可。
- 发现三目运算要选择的两个数(x), (y)，只有一个二进制位不同。所以不需要把条件取反再(operatorname{and})。直接先(operatorname{and})一遍较大的那个数（( ext{ans} imes2+1)），然后把两者(operatorname{or})起来即可。
task6
可以选择“冒泡排序”或者“选择排序”。核心是要实现：if(x>y) swap(x,y);。
可以用task4实现比较。再用倍增法把比较的结果铺满所有位，记这个结果为(t)（(tin{0,2^{64-1}})）。
有了比较结果之后，剩下的又相当于一个三目运算符。不过朴素实现还是操作数量太大（(7)次）。考虑“交换”操作的特性。可以用(operatorname{xor})来实现。先搞一个(z=xoperatorname{xor}y)。那么如果需要交换，就相当于让两个数都异或上(z)。所以可以令(z:=zoperatorname{and}t)。然后再把(x), (y)分别(operatorname{xor}z)即可。共需要(4)次操作。
我实现下来，总共是(2268)次操作。常数大一些应该也不会超过(2400)。
制造答案的代码
//problem:ZR889
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T>inline void ckmax(T& x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T& x,T y){x=(y<x?y:x);}
int get_highbit(ull x){
int ans=0;
while(x)ans++,x>>=1;
return ans;
}
int add(int xpos=1,int ypos=2,int anspos=3,int highbit=64) {
//不需要a[anspos]=0
//不还原a[xpos],a[ypos]
int x=xpos;
int y=ypos;
int z=anspos;
int cnt=0;
for(int i=1;i<=highbit;++i){
cout<<"xor "<<z<<" "<<x<<" "<<y<<endl;++cnt;
cout<<"and "<<y<<" "<<x<<" "<<y<<endl;++cnt;
swap(x,z);
if(i<highbit){
cout<<"shl "<<y<<" "<<1<<endl;++cnt;
}
}
if(x!=anspos){
cout<<"set "<<anspos<<" "<<x<<endl;++cnt;
}
// if(highbit!=64){
// cout<<"shl "<<anspos<<" "<<64-highbit<<endl;++cnt;
// cout<<"shr "<<anspos<<" "<<64-highbit<<endl;++cnt;
// }
return cnt;
}
int popcnt(int pos=1,int anspos=2){
//默认a[anspos]=0
//不还原a[pos]
int cnt=0;
int t1=40;
cout<<"not "<<t1<<" "<<t1<<endl;++cnt;
cout<<"shr "<<t1<<" "<<63<<endl;++cnt;
int v=39;
int s1=38;
int s2=anspos;
for(int i=1;i<=64;++i){
cout<<"and "<<v<<" "<<pos<<" "<<t1<<endl;++cnt;
//cout<<"set "<<s1<<" "<<anspos<<endl;++cnt;
cnt+=add(s1,v,s2,get_highbit(i));
swap(s1,s2);
if(i<64){
cout<<"shr "<<pos<<" "<<1<<endl;++cnt;
}
}
if(s1!=anspos){
cout<<"set "<<anspos<<" "<<s1<<endl;++cnt;
}
return cnt;
}
int push_highbit(int pos,int highbit=64){
//anspos=pos
//把最高位以下全部搞成1
int cnt=0;
int t=20;
for(int i=1;i<highbit;i<<=1){
cout<<"set "<<t<<" "<<pos<<endl;++cnt;
cout<<"shr "<<t<<" "<<i<<endl;++cnt;
cout<<"or "<<pos<<" "<<pos<<" "<<t<<endl;++cnt;
}
return cnt;
}
int compare(int xpos=1,int ypos=2,int anspos=3){
//不需要a[anspos]=0
//不会改变a[xpos],a[ypos]
int cnt=0;
int t1=40;
int t2=39;
cout<<"xor "<<t1<<" "<<xpos<<" "<<ypos<<endl;++cnt;
cnt+=push_highbit(t1);
cout<<"set "<<t2<<" "<<t1<<endl;++cnt;
cout<<"shr "<<t2<<" "<<1<<endl;++cnt;
cout<<"xor "<<t1<<" "<<t1<<" "<<t2<<endl;++cnt;//现在t1只有最高位是1了
cout<<"and "<<anspos<<" "<<t1<<" "<<xpos<<endl;++cnt;
cnt+=push_highbit(anspos);
//task6里可以注释掉:
cout<<"shl "<<anspos<<" "<<63<<endl;++cnt;
cout<<"shr "<<anspos<<" "<<63<<endl;++cnt;
return cnt;
}
int pow_of_popcount(int pos=1,int anspos=2){
//默认a[anspos]=0
int cnt=0;
int flagpos=40;
//cout<<"shl "<<flagpos<<" "<<64<<endl;++cnt;
cout<<"not "<<flagpos<<" "<<flagpos<<endl;++cnt;
cout<<"shr "<<flagpos<<" "<<63<<endl;++cnt;
int t1=39;
int t2=38;
int t3=37;
cout<<"set "<<t1<<" "<<flagpos<<endl;++cnt;
for(int i=1;i<=64;++i){
if(i!=1){
cout<<"set "<<t2<<" "<<anspos<<endl;++cnt;
cout<<"shl "<<t2<<" "<<1<<endl;++cnt;
}
cout<<"or "<<t2<<" "<<t2<<" "<<t1<<endl;++cnt;//t2=anspos<<1|1
cout<<"and "<<t3<<" "<<pos<<" "<<flagpos<<endl;++cnt;
cnt+=push_highbit(t3,i);
cout<<"and "<<t2<<" "<<t2<<" "<<t3<<endl;++cnt;
cout<<"or "<<anspos<<" "<<anspos<<" "<<t2<<endl;++cnt;
if(i<64){
cout<<"shl "<<flagpos<<" "<<1<<endl;++cnt;
}
}
return cnt;
}
int push_lowbit(int pos){
int cnt=0;
int t=20;
for(int i=1;i<=32;i<<=1){
cout<<"set "<<t<<" "<<pos<<endl;++cnt;
cout<<"shl "<<t<<" "<<i<<endl;++cnt;
cout<<"or "<<pos<<" "<<pos<<" "<<t<<endl;++cnt;
}
return cnt;
}
int bubble_sort(){
int cnt=0;
int t1=10;
int t2=11;
for(int i=1;i<9;++i){
for(int j=i+1;j<=9;++j){
cnt+=compare(i,j,t1);
cnt+=push_lowbit(t1);
cout<<"xor "<<t2<<" "<<j<<" "<<i<<endl;++cnt;
cout<<"and "<<t2<<" "<<t2<<" "<<t1<<endl;++cnt;
cout<<"xor "<<i<<" "<<i<<" "<<t2<<endl;++cnt;
cout<<"xor "<<j<<" "<<j<<" "<<t2<<endl;++cnt;
// cout<<"and "<<t2<<" "<<t1<<" "<<j<<endl;++cnt;
// cout<<"and "<<t3<<" "<<t1<<" "<<i<<endl;++cnt;
// cout<<"not "<<t1<<" "<<t1<<endl;++cnt;
// cout<<"and "<<t4<<" "<<t1<<" "<<j<<endl;++cnt;
// cout<<"and "<<t5<<" "<<t1<<" "<<i<<endl;++cnt;
//
// cout<<"or "<<j<<" "<<t3<<" "<<t4<<endl;++cnt;
// cout<<"or "<<i<<" "<<t2<<" "<<t5<<endl;++cnt;
}
}
return cnt;
}
void task1(){
freopen("calculate1.ans","w",stdout);
cout<<"not "<<2<<" "<<1<<endl;
cout<<"shl "<<2<<" "<<63<<endl;
cout<<"shr "<<2<<" "<<63<<endl;
cerr<<"cnt "<<3<<endl;
}
void task2(){
freopen("calculate2.ans","w",stdout);
int cnt=add();
cerr<<"cnt "<<cnt<<endl;
}
void task3(){
freopen("calculate3.ans","w",stdout);
int cnt=popcnt();
cerr<<"cnt "<<cnt<<endl;
}
void task4(){
freopen("calculate4.ans","w",stdout);
int cnt=compare();
cerr<<"cnt "<<cnt<<endl;
}
void task5(){
freopen("calculate5.ans","w",stdout);
int cnt=pow_of_popcount();
cerr<<"cnt "<<cnt<<endl;
}
void task6(){
freopen("calculate6.ans","w",stdout);
int cnt=bubble_sort();
cerr<<"cnt "<<cnt<<endl;
}
int main() {
//...
return 0;
}