【组成原理-指令】扩展操作码的树形解法

2023-12-05 03:12
文章标签 原理 指令 扩展 组成 树形 解法 操作码

本文主要是介绍【组成原理-指令】扩展操作码的树形解法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

仿照哈夫曼树（或前缀编码，Prefix-free）的解法，目前先不解释具体怎么画了，直接放例题，大家自己慢慢品味吧。

【例 1】某指令系统指令长 16 位，操作码字段为 4 位，地址码字段为 4 位，采用扩展操作码技术，形成三地址指令 15 条、二地址指令 15 条、一地址指令 15 条、零地址指令 16 条。

【解】指令格式如下：

OPA1A2A3
4 位4 位4 位4 位

画出对应的树：
【三地址】OP=0000~1110（15条）
OP=1111
【二地址】A1=0000~1110（15条）
A1=1111
【一地址】A2=0000~1110（15条）
A2=1111
【零地址】A3=0000~1111（16条）

沿着树的边一直走到叶子结点，可以得到如下格式的指令：

指令操作码地址码1地址码2地址码3
15 条三地址指令0000A1A2A3
.0001A1A2A3
.…………
.1110A1A2A3
15 条二地址指令11110000A2A3
.11110001A2A3
.…………
.11111110A2A3
15 条一地址指令111111110000A3
.111111110001A3
.…………
.111111111110A3
16 条零地址指令1111111111110000
.1111111111110001
.…………
.1111111111111111

【例 2】某指令系统指令长 16 位，操作码字段为 4 位，地址码字段为 4 位，采用扩展操作码技术，形成三地址指令 15 条、二地址指令 12 条、一地址指令 63 条、零地址指令 16 条。

【解】指令格式如下：

OPA1A2A3
4 位4 位4 位4 位

画出对应的树：
【三地址】OP=0000~1110（15条）
OP=1111
【二地址】A1=0000~1011（12条）
A1=1100
A1=1101
A1=1110
A1=1111
【一地址】A2=0000~1111（16条）
【一地址】A2=0000~1110（15条）
A2=1111
【零地址】A3=0000~1111（16条）

沿着树的边一直走到叶子结点，可以得到如下格式的指令：

指令操作码地址码1地址码2地址码3
15 条三地址指令0000A1A2A3
.0001A1A2A3
.…………
.1110A1A2A3
12 条二地址指令11110000A2A3
.11110001A2A3
.…………
.11111011A2A3
63 条一地址指令111111000000A3
.111111000001A3
.…………
.111111001111A3
.111111010000A3
.111111010001A3
.…………
.111111111110A3
16 条零地址指令1111111111110000
.1111111111110001
.…………
.1111111111111111

【例 3】某指令系统指令长 16 位，地址码字段为 6 位，采用扩展操作码技术，形成二地址指令 12 条、一地址指令 96 条、零地址指令 50 条。

【解】指令格式如下：

OPA1A2
4 位6 位6 位

画出对应的树：
【二地址】OP=0000~1011（12条）
OP=1100
OP=1101
OP=1110
OP=1111
【一地址】A1=000000~111111（64条）
【一地址】A1=000000~011111（32条）
A1=100000
【零地址】A2=000000~110001（50条）

【例 4】某指令系统指令长 12 位，操作码字段为 3 位，地址码字段为 3 位，采用扩展操作码技术，形成二地址指令 4 条、一地址指令 8 条、零地址指令 150 条。

【解】指令格式如下：

OPA1A2A3
3 位3 位3 位3 位

画出对应的树：
【二地址】OP=000~011（4条）
OP=100
OP=101
OP=110
OP=111
【一地址】A1=000~111（8条）
A1=000~111（8种）
A1=000
A1=001
A1=010
【零地址】A2=000~111（8条）
【零地址】A2=000~101（6条）

【例 5】某指令系统指令长 16 位，地址码字段为 6 位，采用扩展操作码技术，如果已定义了 12 条二地址指令，则最多还可定义多少条一地址指令？

【解】指令格式如下：

OPA1A2
4 位6 位6 位

画出对应的树：
【二地址】OP=0000~1011（12条）
OP=1100
OP=1101
OP=1110
OP=1111
【一地址】A1=000000~111111（64条）

所以最多还可定义 4 × 2 6 = 256 4 \times 2^6 = 256 4×26=256 条一地址指令。

【例 6】某指令系统指令长 32 位，地址码字段为 12 位，采用扩展操作码技术，如果已定义了 250 条二地址指令，则最多还可定义多少条一地址指令？

【解】指令格式如下：

OPA1A2
8 位12 位12 位

画出对应的树：
【二地址】OP=0000,0000~1111,1001（250条）
OP=1111,1010
OP=1111,1011
OP=1111,1100
OP=1111,1101
OP=1111,1110
OP=1111,1111
【一地址】A1=000000,000000~111111,111111（2^12条）

所以最多还可定义 6 × 2 12 = 24 K 6 \times 2^{12} = 24K 6×212=24K 条一地址指令。

【例 7】（2022 年统考真题）设计某指令系统时，假设采用 16 位定长指令字格式，操作码使用扩展编码方式，地址码为 6 位，包含零地址、一地址和二地址 3 种格式的指令。若二地址指令有 12 条，一地址指令有 254 条，则零地址指令的条数最多为（ ）。

A. 0

B. 2

C. 64

D. 128

【解】指令格式如下：

OPA1A2
4 位6 位6 位

画出对应的树：
【二地址】OP=0000~1011（12条）
OP=1100
OP=1101
OP=1110
OP=1111
【一地址】A1=000000~111111（64条）
【一地址】A1=000000~111101（62条）
A1=111110
A1=111111
【零地址】A2=000000~111111（64条）

所以最多还可定义 2 × 2 6 = 128 2 \times 2^6 = 128 2×26=128 条零地址指令，本题选 D。

【例 8】（2017 年统考真题）某计算机按字节编址，指令字长固定且只有两种指令格式，其中三地址指令 29 条，二地址指令 107 条，每个地址字段为 6 位，则指令字长至少应该是（ ）

A. 24 位

B. 26 位

C. 28 位

D. 32 位

【解】三地址指令条数满足 29 < 2 5 = 32 29 < 2^5 = 32 29<25=32，因此推断操作码字段 OP 至少为 5 位，指令格式可能如下：

OPA1A2A3
5 位6 位6 位6 位

画出对应的树：
【三地址】OP=00000~11100（29条）
OP=11101
OP=11110
OP=11111
【二地址】A1=000000~111111（64条）
【二地址】A1=000000~010100（21条）

所以指令字长至少有 5 + 3 × 6 = 23 5 + 3 \times 6 = 23 5+3×6=23 位，又因为计算机按字节编址，所以取成 24 位即 3 字节，本题选 A。

这篇关于【组成原理-指令】扩展操作码的树形解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/455928。

相关文章

这15个Vue指令，让你的项目开发爽到爆

这15个Vue指令，让你的项目开发爽到爆

1. V-Hotkey 仓库地址: github.com/Dafrok/v-ho… Demo: 戳这里 https://dafrok.github.io/v-hotkey 安装: npm install --save v-hotkey 这个指令可以给组件绑定一个或多个快捷键。你想要通过按下 Escape 键后隐藏某个组件，按住 Control 和回车键再显示它吗？小菜一碟： <template
阅读更多...
深入探索协同过滤：从原理到推荐模块案例

深入探索协同过滤：从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤（UserCF）2. 基于物品的协同过滤（ItemCF）3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代，推荐系统成为连接用户与内容的桥梁。本文聚焦于
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
hdu1011（背包树形DP）

hdu1011（背包树形DP）

没有完全理解这题， m个人，攻打一个map，map的入口是1，在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下： #include<iostream>#include<algorithm
阅读更多...
hdu4407(容斥原理)

hdu4407(容斥原理)

题意：给一串数字1,2，......n，两个操作:1、修改第k个数字，2、查询区间[l,r]中与n互质的数之和。 解题思路：咱一看，像线段树，但是如果用线段树做，那么每个区间一定要记录所有的素因子，这样会超内存。然后我就做不来了。后来看了题解，原来是用容斥原理来做的。还记得这道题目吗？求区间[1,r]中与p互质的数的个数，如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
科研绘图系列：R语言扩展物种堆积图（Extended Stacked Barplot）

科研绘图系列：R语言扩展物种堆积图（Extended Stacked Barplot）

介绍 R语言的扩展物种堆积图是一种数据可视化工具，它不仅展示了物种的堆积结果，还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异，为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl
阅读更多...
Spring框架5 - 容器的扩展功能 (ApplicationContext)

Spring框架5 - 容器的扩展功能 (ApplicationContext)

private static ApplicationContext applicationContext;static {applicationContext = new ClassPathXmlApplicationContext("bean.xml");} BeanFactory的功能扩展类ApplicationContext进行深度的分析。ApplicationConext与 BeanF
阅读更多...
hdu4407容斥原理

hdu4407容斥原理

题意： 有一个元素为 1~n 的数列{An}，有2种操作（1000次）： 1、求某段区间 [a,b] 中与 p 互质的数的和。 2、将数列中某个位置元素的值改变。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.Inpu
阅读更多...
hdu4059容斥原理

hdu4059容斥原理

求1-n中与n互质的数的4次方之和 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWrit
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2