为了方便，以下位运算中均省略\(\and\)
将\(a_{2}\)的每一位拆开，对于第\(i\)位，将该位乘\(a_{1}\)的结果放到\(a_{A_{i}}\)上
具体的，将该位单独取出放在最低位，并倍增使其余位与其相同
\({\rm SET\ 3\ 2}\ |\ {\rm LSH}\ 3\ 63-i\ |\ {\rm RSH}\ 3\ 63\)
\(\forall t\in [0,5],{\rm SET\ 4\ 3}\ |\ {\rm LSH}\ 3\ 2^{t}\ |\ {\rm XOR}\ 3\ 3\ 4\)
\({\rm SET}\ 4\ 1\ |\ {\rm LSH}\ 4\ i\ |\ {\rm AND}\ A_{i}\ 3\ 4\)
（\(t_{A_{i}}=16\)）
此时答案为\(\sum_{i=0}^{63}a_{A_{i}}\)，并考虑全加器\(a+b+c=(a\oplus b\oplus c)+2(ab\oplus ac\oplus bc)\)
换言之，不断找到\(3\)个\(t\)最小的\(A_{i}\)，设为\(a_{x},a_{y}\)和\(a_{z}\)，并将得到的两个数放到\(a_{x}\)和\(a_{y}\)上
\({\rm XOR}\ 1\ x\ y\ |\ {\rm AND}\ y\ x\ y\ |\ {\rm XOR}\ x\ 1\ z\ |\ {\rm AND}\ 1\ 1\ z\ |\ {\rm XOR}\ y\ 1\ y\ |\ {\rm LSH}\ y\ 1\)
（\(\max(t_{x},t_{y})=44\)）
此时答案为\(a_{x}+a_{y}\)，考虑超前进位加法器：
设\(\begin{cases}a_{x}=\overline{x_{63}...x_{0}}\\a_{y}=\overline{y_{63}...y_{0}}\\a_{x}+a_{y}=\overline{z_{63}...z_{0}}\end{cases},d_{i}\)为（低位向）第\(i\)位的进位，则\(\begin{cases}z_{i}=x_{i}\oplus y_{i}\oplus d_{i}\\d_{i+1}=x_{i}y_{i}\oplus x_{i}d_{i}\oplus y_{i}d_{i}\end{cases}\)
记\(\begin{cases}u_{i}=x_{i}y_{i}\\v_{i}=x_{i}\oplus y_{i}\end{cases}\)，则\(d_{i+1}=u_{i}\oplus v_{i}d_{i}\)，迭代展开后即\(d_{i+1}=\bigoplus_{j=0}^{i}\left(u_{j}\bigcap_{k=j+1}^{i}v_{k}\right)\)
可以倍增实现，即枚举\(t\in [0,5]\)，并修改\(\forall i\in [0,64),\begin{cases}u'_{i}=u_{i}\oplus v_{i}u_{i-2^{t}}\\v'_{i}=v_{i}v_{i-2^{t}}\end{cases}\)
最终\(d_{i+1}=u_{i}\)，实现中可以直接以\(\overline{u_{63}...u_{0}}\)和\(\overline{v_{63}...v_{0}}\)为整体计算
\({\rm AND}\ 1\ x\ y\ |\ {\rm XOR}\ 2\ x\ y\)
\(\forall t\in [0,5],{\rm SET}\ 3\ 1\ |\ {\rm LSH}\ 1\ 2^{t}\ |\ {\rm AND}\ 1\ 1\ 2\ |\ {\rm XOR}\ 1\ 1\ 3\ |\ {\rm SET}\ 3\ 2\ |\ {\rm LSH\ }2\ 2^{t}\ |\ {\rm AND}\ 2\ 2\ 3\)
\({\rm LSH}\ 1\ 1\ |\ {\rm XOR}\ 2\ x\ y\ |\ {\rm XOR}\ 1\ 1\ 2\)
（\(t_{1}=65\)）
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=405;
int t[N];ull a[N];
set<pair<int,int> >S;
void SET(int i,int j){
a[i]=a[j],t[i]=t[j]+1;
printf("SET %d %d\n",i,j);
}
void XOR(int i,int j,int k){
a[i]=(a[j]^a[k]),t[i]=max(t[j],t[k])+1;
printf("XOR %d %d %d\n",i,j,k);
}
void AND(int i,int j,int k){
a[i]=(a[j]&a[k]),t[i]=max(t[j],t[k])+1;
printf("AND %d %d %d\n",i,j,k);
}
void LSH(int i,int x){
a[i]<<=x,t[i]++;
printf("LSH %d %d\n",i,x);
}
void RSH(int i,int x){
a[i]>>=x,t[i]++;
printf("RSH %d %d\n",i,x);
}
int main(){
for(int i=0;i<64;i++){
SET(3,2),LSH(3,63-i),RSH(3,63);
for(int t=0;t<6;t++)SET(4,3),LSH(3,(1<<t)),XOR(3,3,4);
SET(4,1),LSH(4,i),AND(i+5,3,4);
S.insert(make_pair(t[i+5],i+5));
}
while (S.size()>2){
int x=(*S.begin()).second;S.erase(S.begin());
int y=(*S.begin()).second;S.erase(S.begin());
int z=(*S.begin()).second;S.erase(S.begin());
XOR(1,x,y),AND(y,x,y),XOR(x,1,z),AND(1,1,z),XOR(y,1,y),LSH(y,1);
S.insert(make_pair(t[x],x)),S.insert(make_pair(t[y],y));
}
int x=(*S.begin()).second;S.erase(S.begin());
int y=(*S.begin()).second;S.erase(S.begin());
AND(1,x,y),XOR(2,x,y);
for(int t=0;t<6;t++){
SET(3,1),LSH(1,(1<<t)),AND(1,1,2),XOR(1,1,3);
SET(3,2),LSH(2,(1<<t)),AND(2,2,3);
}
LSH(1,1),XOR(2,x,y),XOR(1,1,2);
return 0;
}