简单计算机模拟器题解

问题描述

我们需要为一个简单的8位计算机实现一个解释器，该计算机具有：

• 32字节内存（地址0-31）
• 8位累加器(AC)
• 5位程序计数器(PC)
• 8种用1字节操作码编码的机器指令

解题思路

该解决方案实现了一个冯·诺依曼架构的解释器，其工作流程为：

1. 从输入读取内存内容
2. 初始化PC和AC为0
3. 顺序执行指令直到遇到HLT指令
4. 以二进制形式输出最终的累加器值

核心组件

1. 内存表示：32字节数组MM同时存储代码和数据
2. 指令解码：
   • 高3位确定指令类型
   • 低5位表示操作数地址（当适用时）
3. 执行循环：
   • 获取PC处的指令
   • 递增PC（JMP指令除外）
   • 执行指令
   • 重复直到遇到HLT

标程

#include <memory.h>
#include <stdio.h>

#define BYTEL 8    // 每个字节的位数
#define BYTEN 32   // 内存字节数

// 指令解码宏
#define INST (MM[PC] >> 5)      // 提取高3位指令码
#define ADDR (MM[PC] & 0x1F)    // 提取低5位地址
#define PCPP (PC = ++PC & 0x1F) // PC递增并在31处回绕

typedef unsigned char byte;

// 指令枚举
enum INSTRUCTION {
    STA, LDA, BEQ, NOP, DEC, INC, JMP, HLT
};

byte MM[BYTEN];  // 32字节内存
byte AC;         // 累加器
byte PC;         // 程序计数器

char bs[BYTEN][BYTEL + 1];  // 存储输入的内存二进制字符串

// 执行函数
void EXCU(void) {
    int x;
    
    while (1) {
        switch (INST) {
            case STA:  // 存储累加器值到内存
                MM[ADDR] = AC;
                PCPP;
                break;
                
            case LDA:  // 从内存加载值到累加器
                AC = MM[ADDR];
                PCPP;
                break;
                
            case BEQ:  // 若累加器为0则跳转
                AC ? PCPP : (PC = ADDR);
                break;
                
            case NOP:  // 空操作
                PCPP;
                break;
                
            case DEC:  // 累加器减1
                AC--;
                PCPP;
                break;
                
            case INC:  // 累加器加1
                AC++;
                PCPP;
                break;
                
            case JMP:  // 无条件跳转
                PC = ADDR;
                break;
                
            case HLT:  // 停机并输出结果
                for (x = BYTEL - 1; x >= 0; x--)
                    printf("%d", (AC >> x) & 1);
                putchar('\n');
                return;
                
            default: return;
        }
    }
}

int main() {
    int i, j;
    
    while (~scanf("%s", *bs)) {  // 读取内存内容
        for (i = 1; i < BYTEN; i++)
            scanf("%s", bs[i]);
        
        memset(MM, 0, sizeof(MM));
        // 将二进制字符串转换为字节
        for (i = 0; i < BYTEN; i++)
            for (j = 0; j < BYTEL; j++)
                MM[i] = (MM[i] << 1) | (bs[i][j] - '0');
            
        PC = 0;  // 初始化PC
        AC = 0;  // 初始化AC
        EXCU();  // 开始执行
    }
    
    return 0;
}

关键点解析

1. 指令解码：使用位操作提取指令码和地址
2. PC处理：执行完指令后自动递增PC（JMP指令除外）
3. 二进制转换：将输入的二进制字符串转换为实际字节值
4. 输出格式：按从高位到低位的顺序输出累加器的二进制值

复杂度分析

• 时间复杂度：O(n)，其中n是执行的指令数量
• 空间复杂度：O(1)，固定使用32字节内存空间

该解决方案高效地模拟了简单计算机的行为，正确处理了所有指令类型和内存访问。