深入理解计算机系统_复习_清华_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
深入理解计算机系统_复习_清华
上传于||文档简介
&&计​算​机​组​成​原​理​,​清​华​大​学​复​习​p​p​t
大小：786.73KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢 上传我的文档
 下载
 收藏
工程师，工作经验5年以上，很多方案类资料自己整理
 下载此文档
正在努力加载中...
深入理解计算机系统(第二版) 家庭作业答案
下载积分：3000
内容提示：深入理解计算机系统(第二版) 家庭作业答案
文档格式：DOCX|
浏览次数：119|
上传日期： 04:30:58|
文档星级：
该用户还上传了这些文档
深入理解计算机系统(第二版) 家庭作业答案
官方公共微信　　这个系列已经很久没更新了，记得上一篇博文已经是三月份了，实在是抱歉。最近业余时间没有以前充裕了，因此更新一篇博文已经变成了一种奢侈。记得以前刚开始写的时候，最多的时候LZ一天写过3篇博文，现在想想，往事如梦。
　　好了，好不容易写一次，就不多说废话了，本文主要介绍一下硬件以及HCL语言的内容。
从疑问开始
　　首先，在介绍本文的内容之前，我们先来思考一个看似简单，却实际比较&高深&的问题。众所周知，计算机归根结底是在和0、1打交道，那么到底0和1是如何被计算机记住的呢？
　　怎么样，这个问题是不是有点像数学界的1+1为什么等于2？是否瞬间感觉自己很高大上？
　　请稳住，其实这个问题的答案比1+1=2要简单多了。答案就是计算机通过电压来记录0和1。在学习物理的时候大家肯定都听说过电压这个东西，它的单位一般是伏特（V）。比如我们常用的电压一般是220V。计算机当中使用1V来代表1，使用0V代表0。
　　解答了这个问题，接下来我们就可以继续我们的设计之路了。
设计的基础
　　要谈设计，就要知道设计的基础。刚才其实我们了解了最基本的基础，就是0和1如何表示，不过这只是最根本的立足之本，我们还需要一些基本的元素。就像你要画一个物体一样，首先是点，然后才能点动成线，进而线动成面，最终面动成体。
　　刚才的0和1只不过是点而已，接下来，我们要用点变换成线。这个东西就叫做逻辑门。
　　逻辑门是数字电路的基本计算元素，也可以看做是物理结构与逻辑结构的映射，它们实际上是由晶体管组成的。逻辑门接受信号的输入，并根据信号产生一定的输出，而输出则是输入的布尔函数，也就是说，输出只能是0或者1。下图是and门（&与&门）、or门（&或&门）和not门（&非&门）的标准符号，你可以看做它们代表了一组线路的组成方式。
　　and：& & & & & & & &or：& & & & & & & & not：
　　可以看出，and和or都是2个输入，而not为1个输入。前面我们提到了HCL硬件设计语言，上面的三个图分别用HCL表示则是，a&&b、a||b以及!a。
　　举个例子，比如对于and门来说，它接受2个输入，如果2个输入都是高位电压，则输出的为高位电压，也就是输出为1。否则的话，都是输出低位电压，也就是输出为0。这些就是建立在刚才1V为1，0V为0的基础之上的。
　　现在我们已经掌握了基础，那么在基础之上，我们就可以玩点花样了。比如刚才所提到的逻辑门，它们只能接受1位的输入和1位的输出，比如我们可以计算0&&1为0。那如果我们希望计算更加复杂的表达式该如何做呢，比如1=？（注意，这里是位&与&运算，而不是逻辑运算）。
　　答案就是组合电路。道理很简单，一个逻辑门可以计算1位，如果我们弄来32个逻辑门，不就可以计算32位了吗？那么像上面那个1的运算，我们就可以采取5个逻辑门去计算。当然，实际上并不是这样的，这个后续我们会更加详细的介绍。
　　不过电路往往是复杂的，不能随便乱接，否则电死了谁负责？因此组合的电路需要遵循以下两个原则。
　　1、两个逻辑门的输出不能连接到一起，否则它们可能会使线上的信号矛盾，因此可能会得到一个不合法的电压或故障。比如1个0V和1个1V接到一起，会不会出来个0.5V，又或者类似于正负极相接，直接短路了呢。
　　2、组合的电路必须是无环的。也就是说输出不能再当做输入，否则会使这个函数产生歧义。这个道理很简单，比如数学上来说，如果c=a+b。我们这里可以把c看做输出，a和b看做输入。如果a又等于c了，那么是不是b就等于0了呢？当然不是，因为a此时其实是a+b，第二轮的c又会等于a+2b，同理，第三轮的c又会等于a+3b。那么到底c=a+b还是c=a+2b还是c=a+3b？（这里有点绕，请各位猿友仔细品味）
　　遵循以上原则，我们就可以随意组装电路了。比如在书中的这个电路。
　　它代表着输出是a和b是否相等，如果用HCL来描述电路，就是(a && b) || (!a && !b)。我们不难看出来，这个表达式就是编程语言当中的a == b。
　　接下来这个图是另外一个书中的例子，它被翻译为多路复用器。其实之所以叫这个，就是因为其中的控制位s是可以复用的。如下图。
　　在这个例子当中还不是特别明显，但是之后有更明显的例子说明&复用&的含义。以上这个电路如果用HCL表达，则是(a && s) || (b && !s)。这个电路的含义是如果s为1，则结果为a，否则结果为b。
　　在书中对HCL表达式与C语言的表达式做了区分，有以下三点。
　　1、逻辑门是持续输出的，但C语言表达式是执行到的时候才会求值。这个区别可以把逻辑门当成一个电路来看，电路是不能断电的，电流会一直存在。
　　2、C语言中输入可以是任意整数，而HCL只能是1和0。这点比较好理解。
　　3、对于a && b这个符号来说，C语言中的规定是如果前者为假，则后者不会再计算。而HCL当中没有这种说法。
　　以上所提到的，哪怕是高级设计，也依然是针对1位进行操作的。那么如何才能真正操作多个位呢，比如平时常用的32位或者64位。
　　道理很简单，就是多个1位操作一起进行，例如下面这个图。
　　这个图当中每个位相等的判断都是上面所提到的两个not门，两个and门和一个or门组成的组合电路。它们并列的一起进行，最终再通过一个and门，就完成了判断两个32位的数字是否相等的操作。也就是表达式A == B，值得注意的是，这里的A和B都是32位的。
　　还有一种类似于C语言中switch语句的表达式，就是如下形式。
　　它代表的意思就是如果s为1，则输出A，否则输出B，同样，这里的A和B都是32位的。那么使用电路如何表达呢？其实就是上次的复用电路的32位版本。如下图。
　　可以看到，s的not值是被复用的，否则的话，这里需要32个not门。值得一提的是，HCL中条件选择表达式中的条件是不需要互斥的，只是按照优先顺序依次选取，这与C语言中的switch是不同的。
　　最后一种HCL表达式，是集合的形式。它表示需要拿一个输入信号与某些值做匹配。比如下图当中的S1和S0。
　　其中如果S1为code == 2 || code == 3，S0为code == 1 || code == 0。那么HCL可以用另外一种方式表达，即code in {2,3}和code in {1,0}。可以看出，HCL表达式其实就是一种硬件表述方式。
存储器和时钟
　　上面我们介绍的都是组合电路，它们的作用是根据输入来产生一个值。但是刚才也说过，组合电路是一直持续输出的，因此它无法保持一个状态不变。但我们的计算机是需要存储数据的，因此就需要能保存状态的存储设备。存储设备则是由一个时钟控制，时钟就像一个开关一样，它控制着存储设备什么时候更新设备里的值。
　　常用的存储设备一般有两种。
　　1、时钟寄存器：存储单个位或者单个字。时钟信号来控制寄存器是否要加载输入的值。
　　2、随即访问存储器：存储多个字。用地址来选择该读、写哪个字。
　　时钟寄存器的典型应用是PC、条件码寄存器以及程序状态。它们都有明确的输入，这意味着它们的值其实是某几个值的一个函数，比如条件码寄存器的输入主要就是逻辑计算单元的值，因此条件码寄存器的值就可以看做是逻辑计算单元的函数。
　　时钟寄存器一般是根据时钟信号来更新状态的，而时钟信号就像一个表一样，比如每到12点，寄存器的值就更新一下。就像下面的图示一样，当时钟变化时，值就会变化为y。
　　随即访问存储器最典型的例子就是我们的寄存器文件（也就是8个程序寄存器）和随即访问存储器（也就是我们常说的内存）。它们没有明确的输入值，因此不存在函数关系。不论是寄存器文件还是随即访问存储器，都有读和写两种操作，而对于时钟寄存器来说，是无所谓读和写的，因为它只会根据输入的变化改变输出的值，是可以直接连接到电路上去的。
　　寄存器文件一般有两个读端口和一个写端口。每个端口都附带一个地址来标识操作的是哪个寄存器，而对于写端口，还有一个输入数据，对于读端口，则还有一个输出数据。具体的图示如下。
　　可以看到在寄存器文件的写端口处，有一个时钟（clock）控制着写的操作。当时钟变化时，输入数据的值将会更新到对应的寄存器当中。而对于读数据，则类似于组合电路，根据输入的地址值（src），寄存器文件会输出相应的数据。
　　对于随即访问存储器来说，与寄存器文件非常相似。不同的是，随即访问存储器只有一个地址输入，而不是三个，只有一个数据输出而不是两个。具体的图示如下。
　　当地址（address）输入，并且输入数据（data in）输入时，如果写（write）输入为1并且时钟（clock）变化时，存储器中地址为输入地址值的值将会变化，值就是输入数据（data in）的值。同样的，如果地址（address）输入，并且写（write）输入为0，则输出数据（data out）会输出地址为输入地址值的值。这里还有一点特殊的是，当读数据的时候，如果地址超出了范围，error信号将会输出为1。回忆一下刚才的HCL语言，error其实就可以看做是一个组合电路的输出，等于(address in & max address ) || (address in & 0)，即当输入的地址值不在合法范围内时，它的输出为1。
　　回忆一下本章的内容，其实就是结合HCL语言在讲硬件的组成。而这些硬件，就是Y86处理器需要使用的。比如组合电路，存储器。到本章最后的时候，已经非常接近我们的编程领域了，可以看到有寄存器和内存的出现。但要注意的是，这里的寄存器文件并不等于寄存器，随即访问存储器也不等于内存，LZ只是想让各位猿友更形象的去理解它。
　　下一章，就是带着大家一起做一个顺序实现的Y86处理器，这是一个非常低级但却最基础的处理器。如果你慢慢的进入了这个世界，你会觉得这是一件非常有意思的事情。就LZ本身来讲，读这本书的时候，最大的感受就是，每一章刚开始读的时候都非常枯燥无味，但每当读了几节以后，就有种豁然开朗的感觉，这种感觉相信你一定也非常喜欢。
　　最后LZ再说明一下，本系列博文都是LZ在自己理解的基础上写的，因此尽管核心内容与原著相似，但语言描述上差异甚大，如果各位猿友看着不习惯的话，不妨去看看原著，或许会有不一样的收获。
阅读(...) 评论()深入理解计算机系统 lab1 ——datalab 解答 （95个ops） - 推酷
深入理解计算机系统 lab1 ——datalab 解答 （95个ops）
* CS:APP Data Lab
* &Please put your name and userid here&
* bits.c - Source file with your solutions to the Lab.
This is the file you will hand in to your instructor.
* WARNING: Do not include the &stdio.h& it confuses the dlc
* compiler. You can still use printf for debugging without including
* &stdio.h&, although you might get a compiler warning. In general,
* it's not good practice to ignore compiler warnings, but in this
* case it's OK.
* Instructions to Students:
* STEP 1: Read the following instructions carefully.
You will provide your solution to the Data Lab by
editing the collection of functions in this source file.
INTEGER CODING RULES:
Replace the &return& statement in each function with one
or more lines of C code that implements the function. Your code
must conform to the following style:
int Funct(arg1, arg2, ...) {
/* brief description of how your implementation works */
int var1 = Expr1;
int varM = ExprM;
varJ = ExprJ;
varN = ExprN;
return ExprR;
Each &Expr& is an expression using ONLY the following:
1. Integer constants 0 through 255 (0xFF), inclusive. You are
not allowed to use big constants such as 0xffffffff.
2. Function arguments and local variables (no global variables).
3. Unary integer operations ! ~
4. Binary integer operations & ^ | + && &&
Some of the problems restrict the set of allowed operators even further.
Each &Expr& may consist of multiple operators. You are not restricted to
one operator per line.
You are expressly forbidden to:
1. Use any control constructs such as if, do, while, for, switch, etc.
2. Define or use any macros.
3. Define any additional functions in this file.
4. Call any functions.
5. Use any other operations, such as &&, ||, -, or ?:
6. Use any form of casting.
7. Use any data type other than int.
This implies that you
cannot use arrays, structs, or unions.
You may assume that your machine:
1. Uses 2s complement, 32-bit representations of integers.
2. Performs right shifts arithmetically.
3. Has unpredictable behavior when shifting an integer by more
than the word size.
EXAMPLES OF ACCEPTABLE CODING STYLE:
* pow2plus1 - returns 2^x + 1, where 0 &= x &= 31
int pow2plus1(int x) {
/* exploit ability of shifts to compute powers of 2 */
return (1 && x) + 1;
* pow2plus4 - returns 2^x + 4, where 0 &= x &= 31
int pow2plus4(int x) {
/* exploit ability of shifts to compute powers of 2 */
int result = (1 && x);
result += 4;
FLOATING POINT CODING RULES
For the problems that require you to implent floating-point operations,
the coding rules are less strict.
You are allowed to use looping and
conditional control.
You are allowed to use both ints and unsigneds.
You can use arbitrary integer and unsigned constants.
You are expressly forbidden to:
1. Define or use any macros.
2. Define any additional functions in this file.
3. Call any functions.
4. Use any form of casting.
5. Use any data type other than int or unsigned.
This means that you
cannot use arrays, structs, or unions.
6. Use any floating point data types, operations, or constants.
1. Use the dlc (data lab checker) compiler (described in the handout) to
check the legality of your solutions.
2. Each function has a maximum number of operators (! ~ & ^ | + && &&)
that you are allowed to use for your implementation of the function.
The max operator count is checked by dlc. Note that '=' is not
you may use as many of these as you want without penalty.
3. Use the btest test harness to check your functions for correctness.
4. Use the BDD checker to formally verify your functions
5. The maximum number of ops for each function is given in the
header comment for each function. If there are any inconsistencies
between the maximum ops in the writeup and in this file, consider
this file the authoritative source.
* STEP 2: Modify the following functions according the coding rules.
IMPORTANT. TO AVOID GRADING SURPRISES:
1. Use the dlc compiler to check that your solutions conform
to the coding rules.
2. Use the BDD checker to formally verify that your solutions produce
the correct answers.
* bitNor - ~(x|y) using only ~ and &
Example: bitNor(0x6, 0x5) = 0xFFFFFFF8
Legal ops: ~ &
Max ops: 8
int bitNor(int x, int y) {
/* DeMorgan's Theorem
~ (x | y) &=& ~ x & ~ y */
* fitsShort - return 1 if x can be represented as a
16-bit, two's complement integer.
Examples: fitsShort(33000) = 0, fitsShort(-32768) = 1
Legal ops: ! ~ & ^ | + && &&
Max ops: 8
int fitsShort(int x) {
int y = x && 15;
!( (y && 16) ^ y);
* addOK - Determine if can compute x+y without overflow
Example: addOK(0xx) = 0,
addOK(0xx) = 1,
Legal ops: ! ~ & ^ | + && &&
Max ops: 20
int addOK(int x, int y) {
int ans = x +
!( ( ( x ^ ans ) & ( y ^ ans ) )
&& 0x1F );
* allOddBits - return 1 if all odd-numbered bits in word set to 1
Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
Legal ops: ! ~ & ^ | + && &&
Max ops: 12
int allOddBits(int x) {
int y = x && 16; x &=
y = x && 8; x &=
! ( (x & 0xAA) ^ 0xAA) ;
* byteSwap - swaps the nth byte and the mth byte
Examples: byteSwap(0x, 3) = 0x
byteSwap(0xDEADBEEF, 0, 2) = 0xDEEFBEAD
You may assume that 0 &= n &= 3, 0 &= m &= 3
Legal ops: ! ~ & ^ | + && &&
Max ops: 25
int byteSwap(int x, int n, int m) {
int n_shift =
int m_shift =
int x_n = x & (0xFF &&
n_shift );
int x_m = x & (0xFF &&
m_shift );
return (x ^ x_n ^ x_m) | (((x_n && n_shift) & 0xFF) && m_shift) | (((x_m && m_shift) & 0xFF) && n_shift);
int n_shift =
int m_shift =
int x_n = ( x &&
n_shift ) & 0xFF;
int x_m = ( x &&
m_shift ) & 0xFF;
( x ^ ( x_n && n_shift) ^ ( x_m && m_shift ) ) | ( x_n && m_shift) | (x_m && n_shift);
int n_shift =
int m_shift =
int p = ( ( x && m_shift ) ^ ( x && n_shift) ) & 0xFF;
return x ^ ( ( p && m_shift ) | ( p
&& n_shift ) );
* sign - return 1 if positive, 0 if zero, and -1 if negative
Examples: sign(130) = 1
sign(-23) = -1
Legal ops: ! ~ & ^ | + && &&
Max ops: 10
int sign(int x) {
return (x && 0x1F) | !!x;
* getByte - Extract byte n from word x
Bytes numbered from 0 (LSB) to 3 (MSB)
Examples: getByte(0x) = 0x56
Legal ops: ! ~ & ^ | + && &&
Max ops: 6
int getByte(int x, int n) {
return (x && ( n && 3) ) & 0xFF;
* rempwr2 - Compute x%(2^n), for 0 &= n &= 30
Negative arguments should yield negative remainders
Examples: rempwr2(15,2) = 3, rempwr2(-35,3) = -3
Legal ops: ! ~ & ^ | + && &&
Max ops: 20
int rempwr2(int x, int n) {
int p = (~0) &&
int ans = x & (~p);
return ans +
( ( ( x & (~ans + 1) ) && 0x1F ) & p );
ans +( (x && 0x1F)
~ ( ( !! ans ) && n ) + 1 ));
* isPositive - return 1 if x & 0, return 0 otherwise
Example: isPositive(-1) = 0.
Legal ops: ! ~ & ^ | + && &&
Max ops: 8
int isPositive(int x) {
return !((x && 0x1F) | !x);
* isLess - if x & y
then return 1, else return 0
Example: isLess(4,5) = 1.
Legal ops: ! ~ & ^ | + && &&
Max ops: 24
int isLess(int x, int y) {
int not_y = ~y;
( ( ( ( x +
not_y + 1 ) & ( x ^ not_y ) ) | ( x & not_y ) )&& 0x1F ) & 1;
* trueThreeFourths - multiplies by 3/4 roun 9 isLess
ding toward 0,
avoiding errors due to overflow
Examples: trueThreeFourths(11) = 8
trueThreeFourths(-9) = -6
trueThreeFourths() =
(no overflow)
Legal ops: ! ~ & ^ | + && &&
Max ops: 20
int trueThreeFourths(int x)
int y = x & 0x3;
x = x && 2;
return ( x&& 1 )+ x + ( ( y + y + y + ( (x && 0x1F) & 0x3 )) && 2 );
* isNonZero - Check whether x is nonzero using
the legal operators except !
Examples: isNonZero(3) = 1, isNonZero(0) = 0
Legal ops: ~ & ^ | + && &&
Max ops: 10
int isNonZero(int x) {
((( ~ x +1 ) | x) && 0x1F) & 1;
* satAdd - adds two numbers but when positive overflow occurs, returns
maximum possible value, and when negative overflow occurs,
it returns minimum positive value.
Examples: satAdd(0xx) = 0x7fffffff
satAdd(0xxffffffff) = 0x
Legal ops: ! ~ & ^ | + && &&
Max ops: 30
int satAdd(int x, int y) {
int ans = x +
int ALL = (( x ^ ans) & (y ^ ans)) && 0x1F;
int x_sign = x && 0x1F;
return (ans | ALL) ^ ( ( (ALL & 1) && 0x1F ) ^ ( x_sign & ALL ) );
int ans = x +
int overFlow = (( x ^ ans) & (y ^ ans)) && 0x1F;
return ( ans && ( overFlow & 0x1F ) ) + ( overFlow && 0x1F ) ;
* float_abs - Return bit-level equivalent of absolute value of f for
floating point argument f.
Both the argument and result are passed as unsigned int's, but
they are to be interpreted as the bit-level representations of
single-precision floating point values.
When argument is NaN, return argument..
Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
Max ops: 10
unsigned float_abs(unsigned uf) {
unsigned ALL = 0x7FFFFFFF;
unsigned minNaN = 0x7F800001;
unsigned temp = uf & ALL;
if (temp &= minNaN)
* float_twice - Return bit-level equivalent of expression 2*f for
floating point argument f.
Both the argument and result are passed as unsigned int's, but
they are to be interpreted as the bit-level representation of
single-precision floating point values.
When argument is NaN, return argument
Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
Max ops: 30
unsigned float_twice(unsigned uf) {
unsigned temp = uf & 0x7F800000;
unsigned sign = uf & 0x;
if (temp) {
temp != 0x7F800000 ) {
uf = uf + 0x ;
if (temp == 0x7F000000) uf = (uf & 0xFF800000);
uf = ( uf && 1) |
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致1664人阅读
编程练习（2）
CSAPP深入理解计算机系统实验datalab解析&&&&&&&
&&&&&&& 看完这一本《CSAPP深入理解计算机系统》自然应该将配套的实验好好做做，这是巩固知识提升运用能力的一个非常好的方法，第一个实验就是这个datalab，要求我们对位运算有很深的理解和掌握，在做这个实验的过程中，遇到了很多难题，基本上都能通过查阅资料和自我分析解决，下面我将我的答案贴出来，以便以后再做此实验的同仁能够参考一下，所有函数都通过检测，并且大部分函数都包含我自己的理解所以我都加上了注释，有网址的地方是借鉴和参考的原网址，在原内容的基础上我又增加了自己的思考与修改。由于CMU的这门计算机导论课程一直在更新，所以很多最新的内容在网络上比较乱，大家在这篇日志可以看到对该实验的最新解析。下面提供几篇可供参考的关于该实验的日志：
&& 这篇文章的实验内容比较新，少部分不同，美中不足的是注释不多。
这篇文章介绍了几个需要考虑的细节问题。
&&&&&&& && 这个博客讲解比较详细，注释丰富，但实验内容不全。
这篇文章有很多其他函数的实现，可以继续深入学习。
* CS:APP Data Lab
* &Please put your name and userid here&
* bits.c - Source file with your solutions to the Lab.
This is the file you will hand in to your instructor.
* WARNING: Do not include the &stdio.h& it confuses the dlc
* compiler. You can still use printf for debugging without including
* &stdio.h&, although you might get a compiler warning. In general,
* it's not good practice to ignore compiler warnings, but in this
* case it's OK.
* Instructions to Students:
* STEP 1: Read the following instructions carefully.
You will provide your solution to the Data Lab by
editing the collection of functions in this source file.
INTEGER CODING RULES:
Replace the &return& statement in each function with one
or more lines of C code that implements the function. Your code
must conform to the following style:
int Funct(arg1, arg2, ...) {
/* brief description of how your implementation works */
int var1 = Expr1;
int varM = ExprM;
varJ = ExprJ;
varN = ExprN;
return ExprR;
Each &Expr& is an expression using ONLY the following:
1. Integer constants 0 through 255 (0xFF), inclusive. You are
not allowed to use big constants such as 0xffffffff.
2. Function arguments and local variables (no global variables).
3. Unary integer operations ! ~
4. Binary integer operations & ^ | + && &&
Some of the problems restrict the set of allowed operators even further.
Each &Expr& may consist of multiple operators. You are not restricted to
one operator per line.
You are expressly forbidden to:
1. Use any control constructs such as if, do, while, for, switch, etc.
2. Define or use any macros.
3. Define any additional functions in this file.
4. Call any functions.
5. Use any other operations, such as &&, ||, -, or ?:
6. Use any form of casting.
7. Use any data type other than int.
This implies that you
cannot use arrays, structs, or unions.
You may assume that your machine:
1. Uses 2s complement, 32-bit representations of integers.
2. Performs right shifts arithmetically.
3. Has unpredictable behavior when shifting an integer by more
than the word size.
EXAMPLES OF ACCEPTABLE CODING STYLE:
* pow2plus1 - returns 2^x + 1, where 0 &= x &= 31
int pow2plus1(int x) {
/* exploit ability of shifts to compute powers of 2 */
return (1 && x) + 1;
* pow2plus4 - returns 2^x + 4, where 0 &= x &= 31
int pow2plus4(int x) {
/* exploit ability of shifts to compute powers of 2 */
int result = (1 && x);
result += 4;
FLOATING POINT CODING RULES
For the problems that require you to implent floating-point operations,
the coding rules are less strict.
You are allowed to use looping and
conditional control.
You are allowed to use both ints and unsigneds.
You can use arbitrary integer and unsigned constants.
You are expressly forbidden to:
1. Define or use any macros.
2. Define any additional functions in this file.
3. Call any functions.
4. Use any form of casting.
5. Use any data type other than int or unsigned.
This means that you
cannot use arrays, structs, or unions.
6. Use any floating point data types, operations, or constants.
1. Use the dlc (data lab checker) compiler (described in the handout) to
check the legality of your solutions.
2. Each function has a maximum number of operators (! ~ & ^ | + && &&)
that you are allowed to use for your implementation of the function.
The max operator count is checked by dlc. Note that '=' is not
you may use as many of these as you want without penalty.
3. Use the btest test harness to check your functions for correctness.
4. Use the BDD checker to formally verify your functions
5. The maximum number of ops for each function is given in the
header comment for each function. If there are any inconsistencies
between the maximum ops in the writeup and in this file, consider
this file the authoritative source.
* STEP 2: Modify the following functions according the coding rules.
IMPORTANT. TO AVOID GRADING SURPRISES:
1. Use the dlc compiler to check that your solutions conform
to the coding rules.
2. Use the BDD checker to formally verify that your solutions produce
the correct answers.
* bitAnd - x&y using only ~ and |
Example: bitAnd(6, 5) = 4
Legal ops: ~ |
Max ops: 8
int bitAnd(int x, int y) {
return ~(~x|~y);
* getByte - Extract byte n from word x
Bytes numbered from 0 (LSB) to 3 (MSB)
Examples: getByte(0x) = 0x56
Legal ops: ! ~ & ^ | + && &&
Max ops: 6
int getByte(int x, int n) {
return x&&(n&&3)&0
* logicalShift - shift x to the right by n, using a logical shift
Can assume that 0 &= n &= 31
Examples: logicalShift(0x) = 0x
Legal ops: ! ~ & ^ | + && &&
Max ops: 20
int logicalShift(int x, int n) {
return (x&&n)&(~((0x1&&31)&&n&&1));
* bitCount - returns count of number of 1's in word
Examples: bitCount(5) = 2, bitCount(7) = 3
Legal ops: ! ~ & ^ | + && &&
Max ops: 40
**参考《CSAPP深入理解计算机系统》例3.50解答
int bitCount(int x) {
int tmp=((0x01&&8|0x01)&&8|0x01)&&8|0x01;
int val=x&
val+=tmp&(x&&1);
val+=tmp&(x&&2);
val+=tmp&(x&&3);
val+=tmp&(x&&4);
val+=tmp&(x&&5);
val+=tmp&(x&&6);
val+=tmp&(x&&7);
val=val+(val&&16);
val=val+(val&&8);
return val&0
* bang - Compute !x without using !
Examples: bang(3) = 0, bang(0) = 1
Legal ops: ~ & ^ | + && &&
Max ops: 12
**If x!=0，x+(~x+1)＝2^32，the highest bit of x and (~x+1)cannot be both 0(至少有一个为1再加上进位就可以继续进位，否则不会变成2^32).
int bang(int x) {
return (~((x|(~x+1))&&31))&0x1;
* tmin - return minimum two's complement integer
Legal ops: ! ~ & ^ | + && &&
Max ops: 4
int tmin(void) {
return 0x1&&31;
* fitsBits - return 1 if x can be represented as an
n-bit, two's complement integer.
1 &= n &= 32
Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
Legal ops: ! ~ & ^ | + && &&
Max ops: 15
/* if all negative numbers(e.g x) are changed into ~x, all the numbers those
* can be represented as an n-bit, two's complement integer will be in range
* of 0~2^(n-1). If it was arithmatically shifted (n-1) bits to right, it'll
/post//427784
int fitsBits(int x, int n) {
int isPositive=!(x&&31);
int shift=n+~0;
//shift=n-1;
return (isPositive&!(x&&shift))|(!isPositive&!((~x)&&shift));
* divpwr2 - Compute x/(2^n), for 0 &= n &= 30
Round toward zero
Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
Legal ops: ! ~ & ^ | + && &&
Max ops: 15
int divpwr2(int x, int n) {
int sign=x&&31;
int bias=sign & ((1&&n) + (~0));
return (x+bias)&&n;
* negate - return -x
Example: negate(1) = -1.
Legal ops: ! ~ & ^ | + && &&
Max ops: 5
int negate(int x) {
return ~x+1;
* isPositive - return 1 if x & 0, return 0 otherwise
Example: isPositive(-1) = 0.
Legal ops: ! ~ & ^ | + && &&
Max ops: 8
int isPositive(int x) {
return !((x&&31)|(!x));
* isLessOrEqual - if x &= y
then return 1, else return 0
Example: isLessOrEqual(4,5) = 1.
Legal ops: ! ~ & ^ | + && &&
Max ops: 24
/* Because the substraction of two numbers with different signs may cause
* overflow, we should only judge whether x is negative then return
* 1(true). Otherwise we'll judge whether (x-y) is a non-positive
((x+(~y)+1-1)&&31,which includes the situation of x-y=0)
* number and return 1(true).
reference:/post//427885
int isLessOrEqual(int x, int y) {
int signx=x&&31;
int signy=y&&31;
int IsSameSign=(!(signx^signy));
return (IsSameSign & ((x+(~y))&&31)) | ((!IsSameSign) & signx);
* ilog2 - return floor(log base 2 of x), where x & 0
Example: ilog2(16) = 4
Legal ops: ! ~ & ^ | + && &&
Max ops: 90
/* ilog2 is equivlance of finding the index of first 1 from left, the method is as following:
* check whether x's left half bits are all 0's, if so then throw them away,
* else right shift to reject the right half(remember the 16 bits thrown from
* right), to repeat it until only one &1& remaining and return the remembered
* number of x having been eliminated.
/post//428134
int ilog2(int x) {
int shift1,shift2,shift3,shift4,shift5;
//The value of 2^n has the form:0……010……0,so we can cut it short and increment the count variable with the corresponding number.
int sign = !!(x && 16); // whether x's left 16 bits aren't all 0's
shift1 = sign && 4;
x = x && shift1; // if so, right shift 16 bits
sign = !!(x && 8); // whether x's left 8 bits aren't all 0's
shift2 = sign && 3;
x = x && shift2; // if so, right shift 8 bits
sign = !!(x && 4); // whether x's left 4 bits aren't all 0's
shift3 = sign && 2;
x = x && shift3; // if so, right shift 4 bits
sign = !!(x && 2); // whether x's left 2 bits aren't all 0's
shift4 = sign && 1;
x = x && shift4; // if so, right shift 2 bits
sign = !!(x && 1); // whether x's left 1 bits aren't all 0's
shift5 = // if so, count will be added 1
// return all the shifts whose sum means the index of first &1& from left
return shift1+shift2+shift3+shift4+shift5;
* float_neg - Return bit-level equivalent of expression -f for
floating point argument f.
Both the argument and result are passed as unsigned int's, but
they are to be interpreted as the bit-level representations of
single-precision floating point values.
When argument is NaN, return argument.
Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
Max ops: 10
unsigned float_neg(unsigned uf) {
unsigned result= uf ^ 0x;//change the signed bit of uf
unsigned tmp=uf & 0x7//change the signed bit of uf to 0
if( tmp & 0x7f800000 ) //When argument is NaN(exponent bits are all 1 and mantissa bits arenot all 0), return argument.
//IEEE754 standard:1 bit signed bit,8 bits exponent,23 bits mantissa.
* float_i2f - Return bit-level equivalent of expression (float) x
Result is returned as unsigned int, but
it is to be interpreted as the bit-level representation of a
single-precision floating point values.
Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
Max ops: 30
unsigned float_i2f(int x) {//Rounding is important!
unsigned sign=0,shiftleft=0,flag=0,
unsigned absx=x;
if( x==0 ) return 0;
if( x&0 ){
while(1){//Shift until the highest bit equal to 1 in order to normalize the floating-point number
shiftleft++;
if( tmp&0x )
if( (absx & 0x01ff) & 0x0100 ) flag=1;//***Rounding 1
if( (absx & 0x03ff) == 0x0300 ) flag=1;//***Rounding 2
return sign+(absx&&9)+((159-shiftleft)&&23)+
* float_twice - Return bit-level equivalent of expression 2*f for
floating point argument f.
Both the argument and result are passed as unsigned int's, but
they are to be interpreted as the bit-level representation of
single-precision floating point values.
When argument is NaN, return argument
Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
Max ops: 30
unsigned float_twice(unsigned uf) {
/* Computer 2*f. If f is a NaN, then return f. */
unsigned exponent = uf & 0x7F800000;
unsigned sign = uf & 0x;
if (exponent) {
exponent != 0x7F800000 ) {
//if exponent bits are all 1 and mantissa bits arenot all 0,the number is NaN.
uf = uf + 0x;
//Increment exponent by 1,effectively multiplying by 2.
uf = ( uf && 1) |
//shift one bit to left
运行结果如下：
Score&& &Rating&& &Errors&& &Function
&1&& &&&&&&& 1&& &&&&&&&&&& 0&& &&&&&&&&& bitAnd
&2&& &&&&&&&&2&& &&&&&&&&&& 0&& &&&&&&&&& getByte
&3&& &&&&&&&&3&& &&&&&&&&&& 0&& &&&&&&&&& logicalShift
&4&& &&&&&&&&4&& &&&&&&&&&& 0&& &&&&&&&&& bitCount
&4&& &&&&&&&&4&& &&&&&&&&&& 0&& &&&&&&&&& bang
&1&& &&&&&&&&1&& &&&&&&&&&&&0&& &&&&&&&&& tmin
&2&& &&&&&&&&2&& &&&&&&&&&&&0&&&&&&&&&& & fitsBits
&2&&&&&&&&& &2&& &&&&&&&&&&&0&&&&&&&&&&&& divpwr2
&2&& &&&&&&&&2&& &&&&&&&&&&&0&&&&&&&&&&&& negate
&3&& &&&&&&&&3&& &&&&&&&&&&&0&&&&&&&&&&&& isPositive
&3&& &&&&&&&&3&&&&&&&&&&&& &0&&&&&&&&&&&& isLessOrEqual
&4&& &&&&&&&&4&& &&&&&&&&&&&0&&&&&&&&&&&& ilog2
&2&& &&&&&&&&2&& &&&&&&&&&&&0&& &&&&&&&&& float_neg
&4&&&&&&&&& &4&& &&&&&&&&&&&0&& &&&&&&&&& float_i2f
&4&& &&&&&&&&4&& &&&&&&&&&&&0&& &&&&&&&&& float_twice
Total points: 41/41
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：3629次
排名：千里之外