位运算模拟《三体1》人列计算机

又第114514遍看完了《三体》，于是想到了这个猎奇思路：我们可以通过模拟计算机的加法处理来得到答案

第一步：实现1位二进制数的加法 - 半加器与全加器
我们先计算两个1位二进制数相加，不考虑来自低位的进位。
输入：A (被加数)， B (加数)
输出：S (和)， C (进位)

其真值表如下：

A	B	S	C
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

观察真值表，我们发现：

S (和) 只有在 A 和 B 不相同时 才为1。这正好是 异或门（XOR） 的逻辑。

S = A ^ B;

C (进位) 只有在 A 和 B 相同时为1 时才为1。这正好是 与门（AND） 的逻辑。

C = A & B;

所以，一个半加器可以由一个异或门和一个与门构成

在半加器的基础上，我们构建能处理进位的全加器。

全加器计算两个1位二进制数以及一个来自低位的进位值。
输入：A (被加数)， B (加数)， Cin (来自低位的进位)
输出：S (和)， Cout (向高位的进位)

其逻辑是：

先计算 A 和 B 的和，得到 S1。
再用 S1 和 Cin 相加，得到最终的和 S。
在两次相加的过程中，任何一个步骤产生进位，最终都要向高位进位。
经过逻辑推导，全加器的电路可以用两个半加器和一个或门构成：

S = A ^ B ^ Cin
Cout = (A & B) | (Cin & (A ^ B))

第二步：实现多位二进制数的加法 - 行波进位加法器

有了全加器这个“乐高积木”，我们就可以搭建一个多位数的加法器了。

最直接的方法是将多个全加器串联起来，将低一位全加器的 Cout 连接到高一位全加器的 Cin。

例如，一个4位加法器：

最低位（第0位）的 Cin 通常接 0（因为没有更低的位了）。
第0位的 A0 和 B0 相加，产生 S0 和 C0（作为第1位的 Cin）。
第1位的 A1、B1 和 C0 相加，产生 S1 和 C1（作为第2位的 Cin）。
... 以此类推。
最高位的 Cout 就是最终的总进位。
这样，进位信号像波浪一样从低位传递到高位，所以这种结构被称为“行波进位加法器”。

代码实现
我们可以先通过将输入转化为二进制（除二取余，逆序排列）
处理后将二进制答案转为十进制输出（每位按权重叠加）

string t2(int a){//转二进制
    string s;
    while(a){
        s=char(a%2+'0')+s;
        a/=2;
    }
    return s;
}
int t10(string s){//转十进制
    int a=0,x=1;
    for(int i=s.size()-1;i>=0;i--){
        a+=(s[i]-'0')*x;
        x*=2;
    }
    return a;
}

由于两个字符串的长度可能不同，我们需要补前导零

int a,b;
cin>>a>>b;
string s1=t2(a),s2=t2(b),a1,b1;
int n=s1.size(),m=s2.size();
if(n>=m){
    for(int i=1;i<=n-m;i++){
            s2='0'+s2;
    }
}else{
    for(int i=1;i<=m-n;i++){
        s1='0'+s1;
    }
}

为了方便处理，我们可以将字符串倒序排列

for(int i=max(n,m)-1;i>=0;i--){
    a1+=s1[i];
    b1+=s2[i];
}

模拟全加器

bool x,y;
char cn='0',sum;
string ans;
for(int i=0;i<max(n,m);i++){
    x=a1[i]-'0',y=b1[i]-'0';
    sum=(x^y^(cn-'0'))+'0';
    cn=((x&y)|((cn-'0')&(x^y)))+'0';
    ans+=sum;
}
if(cn=='1'){
    ans+=cn;
}

此时的答案是反的，我们要将其取反，并转十进制

string ans1;
for(int i=ans.size()-1;i>=0;i--){
    ans1+=ans[i];
}
cout<<t10(ans1);

完整代码

#include <bits/stdc++.h>
using namespace std;
string t2(int a){
    string s;
    while(a){
        s=char(a%2+'0')+s;
        a/=2;
    }
    return s;
}
int t10(string s){
    int a=0,x=1;
    for(int i=s.size()-1;i>=0;i--){
        a+=(s[i]-'0')*x;
        x*=2;
    }
    return a;
}
int main(){
    int a,b;
    cin>>a>>b;
    string s1=t2(a),s2=t2(b),a1,b1;
    int n=s1.size(),m=s2.size();
    if(n>=m){
        for(int i=1;i<=n-m;i++){
            s2='0'+s2;
        }
    }else{
        for(int i=1;i<=m-n;i++){
            s1='0'+s1;
        }
    }
    for(int i=max(n,m)-1;i>=0;i--){
        a1+=s1[i];
        b1+=s2[i];
    }
    bool x,y;
    char cn='0',sum;
    string ans;
    for(int i=0;i<max(n,m);i++){
        x=a1[i]-'0',y=b1[i]-'0';
        sum=(x^y^(cn-'0'))+'0';
        cn=((x&y)|((cn-'0')&(x^y)))+'0';
        ans+=sum;
    }
    if(cn=='1'){
        ans+=cn;
    }
    string ans1;
    for(int i=ans.size()-1;i>=0;i--){
        ans1+=ans[i];
    }
    cout<<t10(ans1);
    
    return 0;
}

如果你有耐心看完，那就点个赞吧