[SOLVED] CS代考程序代写 scheme OSU CSE 2421

OSU CSE 2421
Slide decks 1 through 21 will be covered on the mid-term.
This slide deck, 22, through the end of the semester will be covered on the final. Recall that the only items from the midterm that will be addressed on the final are those that – AS A CLASS – folks crashed and burned on.
J.E.Jones

OSU CSE 2421
Required Reading: Computer Systems: A Programmer’s Perspective, 3rd Edition
• Chapter 4, Sections 4.2 through 4.2.2
• Chapter 2, Sections 2.3 through 2.3.8
• Chapter 8, Section 8.2 through 8.2.4
J.E.Jones

OSU CSE 2421
Addition:
456 289 745
Carry In OperandA Operand B
1 4 2 7
5 6 8 9 4 5
SumOut Carry Out
0
1 1
102
101
100
1 0
Did you know this is what you were really doing?
J. E. Jones

OSU CSE 2421
 http://www.tutorialspoint.com/computer_logical_organization/logic_gates.htm
 In general, I consider this a topic for ECE 2060
 For Systems, just know what kind of gates there are and, given 2 input, what the analogous output will be.
J. E. Jones

OSU CSE 2421
1 and 3exclusive OR (^) 2 and 4and (&)
5or (|)
01100 carry* 0110 a 0111 b
* Always start with a carry-in of 0
01101 a+b
Did it work?
What is a?
What is b?
What is a+b?
What if 8 bits instead of 4?
J. E. Jones

OSU CSE 2421
 We will not worry about the intermediate outputs generated by the hardware; we will only be concerned with:
 The three input bits: 1) CARRY IN, 2) A, and 3) B.
 And the two output bits: 4) SUM OUT, and 5)
CARRY OUT.
 Let’s look at the bit by bit addition of the two 4-bit operands on the preceding slide: 0110 and 0111.
J. E. Jones

OSU CSE 2421
CarryIn 1
1 0 0
OperandA 0
1 1 0
OperandB 0
1 1 1
Sum Out 1 CarryOut 0
1 01 1 1 0
 Notes:
23 22 21 20
◦ For addition, carry into the least significant pair of bits is always 0.
◦ Carry out from each pair of bits is propagated to carry in for the next most significant pair of bits.
◦ For unsigned addition, if carry out from the most significant pair of bits is 0, there is no overflow.
J. E. Jones

OSU CSE 2421
 Different encoding scheme than float
 Total number of distinct bit patterns (values): 2w
◦ where w is the bit width (number of bits) of the digital representation
 The left-most bit is the sign bit if using a signed data type  Unsignednon-negative numbers (>=0)
◦ Minimum value: 0
◦ Maximum value: 2w-1
 Signednegative, zero, and positive numbers
◦ Minimum value: -2w-1 (2’s complement – see below)  (Reminder: exponent before negative sign)
◦ Maximum value: 2w-1-1
J. E. Jones

OSU CSE 2421
 We can use hexadecimal values to represent 4 binary bits. This typically makes them easier to read
0000 0 0001 1 0010 2 0011 3 0100 4 0101 5 0110 6 0111 7 1000 8 1001 9 1010 A 1011 B 1100 C 1101 D 1110 E 1111 F
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 -8 9 -7 10 -6 11 -5 12 -4 13 -3 14 -2 15 -1
 Note that the binary value 1010 can represent: A
10 -6
The only difference is how we wish to interpret those 4 bits.
BINARY HEX B2U B2T
J. E. Jones

OSU CSE 2421
 B2U – Binary to unsigned
 B2T – Binary to two’s-complement  B20 – Binary to ones’-complement  B2S – Binary to sign-magnitude
J. E. Jones

OSU CSE 2421
 Binary to Decimal
 One’s complement = B2O
BINARY B2O
0000 0
0001 1
◦ Most significant digit (left-most bit) represents
the sign bit 0010
◦ if sign bit = 1, then it’s a negative number and to get the magnitude of that number, invert all bits
2 0011 3
0100 4
0101 5
0110 6
0111 7
 1010 changes to 0101
 0101= 5, so final value is -5
 We can represent any integer value we want if we use enough bits.
1000 -7
◦ For some number of bits w, we can represent all integer values between -2w-1-1 and 2w-1-1.
1001 -6
1010 -5
1011 -4
1100 -3
1101 -2
1110 -1
1111 -0
◦ If w=4, then all integers between -7 and 7
◦ If w=10, then all integers between -511 and 511
 Note this decoding scheme has two different binary representations for 0 (all 0s AND all 1s no matter what w equals),
J. E. Jones

OSU CSE 2421
 Binary to Decimal
 Sign Magnitude = B2S
BINARY B2S 0000 0 0001 1 0010 2 0011 3 0100 4 0101 5 0110 6 0111 7 1000 -0 1001 -1 1010 -2 1011 -3 1100 -4 1101 -5 1110 -6 1111 -7
◦ Most significant digit (left-most bit) represents the sign bit
◦ if sign bit = 1, then it’s a negative number and to get the magnitude of that number, use the
remaining w-1 bits
 1010 means value is negative/magnitude is 010  010 = 2, so final value is -2
 We can represent any integer value we want if we use enough bits.
◦ For some number of bits w, we can represent all integer values between -2w-1-1 and 2w-1-1.
◦ If w=4, then all integers between -7 and 7
◦ If w=10, then all integers between -511 and 511
 Note this decoding scheme has two different binary representations for 0 (all 0s AND msb = 1, then rest of the bits all 0s no matter what w equals),
J. E. Jones

OSU CSE 2421
 One’s complement – bit complement of B2U for negatives
CODE B2U 0000 0 0001 1 0010 2 0011 3 0100 4 0101 5 0110 6 0111 7 1000 8 1001 9 1010 10 1011 11 1100 12 1101 13 1110 14 1111 15
B2T B2O B2S 0 0 0
1 1 1
2 2 2
 Signed Magnitude – left most bit for sign, B2U for the remaining w-1 bits
3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 -8 -7 -0 -7 -6 -1 -6 -5 -2 -5 -4 -3 -4 -3 -4 -3 -2 -5 -2 -1 -6 -1 -0 -7
 Both include negative values
 Min/max = -(2w-1-1) to 2w-1-1
 Positive and negative zero
 Difficulties with arithmetic operations (that’s why these encodings are not used for integers anymore)
J. E. Jones

OSU CSE 2421
 Casting – signed to unsigned, unsigned to signed…
CODE B2U B2T 0000 0 0 0001 1 1 0010 2 2 0011 3 3 0100 4 4 0101 5 5 0110 6 6 0111 7 7 1000 8 -8 1001 9 -7 1010 10 -6 1011 11 -5 1100 12 -4 1101 13 -3 1110 14 -2 1111 15 -1
 Changes the meaning or interpretation of the value, but not the bit representation
 if(x>=0) && (x<=3)  if((unsigned)x<=3)J. E. Jones OSU CSE 2421  When an operation is performed where one operand is signed and the other is unsigned, C implicitly casts the signed operand to unsigned (remember the type conversion hierarchy), then performs the operations Arithmetic operations in the machine are not affected, since bit representation doesn’t change Relational operators could be affected (Force unsigned immediate value with suffixed ‘u’ in C)J. E. Jones OSU CSE 2421  0 == 0u True Unsigned relational operator -1 < 1 True◦ Signed relational operator -1 < 1uFalse 0xffffffff < 0x00000001 ◦ Unsigned relational operator◦ -1 is stored as 0xFFFFFFFF (4-byte integer)◦ 1isstoredas0x00000001 Interpreted as an unsigned value, this is the largest integer that fits in 32 bits! NOTE: For integers, w = 32 on stdlinuxJ. E. Jones OSU CSE 2421  Sign Extension◦ For unsigned fill to left with zero◦ For signed repeat sign bit (MSB, or most significant bit) charx=-27; short y;/*w=8inC */ /*w = 16 on stdlinux for short */◦ 27 = 0001 1011◦ -27 = 1110 0101/* invert +1 to get 2’s complement */ y = (short)x; x is sign-extended to 16 bits (on stdlinux), and this sign-extended bitpattern is assigned to y:◦ 27 = 0000 0000 0001 1011 ◦ -27 = 1111 1111 1110 0101J. E. Jones OSU CSE 2421  Drops the high order w-k bits when truncating a w-bit number to a k-bit number short y = -27; /*w = 16 on stdlinux*/ ◦ 27 = 0000 0000 0001 1011◦ -27 = 1111 111 1110 0101 /*invert + 1 to get 2’s complement*/ char x = (char)y; /*w = 8 for char in C*/ x = (char)y;◦ -27 = 1110 0101 /* truncate high-order w – k, or 16 – 8, bits */J. E. Jones OSU CSE 2421  When the high order w-k bits are dropped when truncating a w-bit number to a k-bit number, does the value change?J. E. Jones OSU CSE 2421  When the high order w-k bits are dropped when truncating a w-bit number to a k-bit number, does the value change? Answer:◦ Unsigned: If all truncated bits are 0, value is preserved. ◦ Signed: If the most significant bit (msb) in the truncated number is the same as each of the truncated bits, value is preserved.J. E. Jones OSU CSE 2421HEX UNSIGNED – B2UTWO’S COMP – B2Torig trunc origtrunc 02137orig0 0 2 20 0(0000)(000) 022(0010) (010) 291(1001) (001) 9-7 1 -5 3 -1 -1B3(1011) (011) 11F7(1111) (111) 15truncJ. E. JonesOSU CSE 2421  Unsigned Overflow when x+y > 2w – 1
 Example:
 Unsigned 4-bit BTU
• The processor only needs
x y x+y
to check carry-out from
12 5 17 1 1100 0101 10001 OF
most significant bits • Overflow > 15
When we only have w bits, extra bits drop into the “bit bucket”. So this 1 is gone and we have overflow
result 8 5 13 13 1000 0101 1101 ok 8 7 15 15 1000 0111 1111 ok
J. E. Jones

OSU CSE 2421
 Signed
 Negative overflow when x+y < -2w-1 Positive overflow when x+y > 2w-1-1
• Result incorrect if
x y x+y
-8 -5 -13 3
carry-in != carry out of top bit (msb)
result
 Example:
 Signed 4-bit B2T
• Positive overflow > 7
• Negative overflow < -81000 1000 1 0000 Neg OF -8 5 -3 -3When we only have w bits, extra bits drop into the “bit bucket”.1000 1011 1 0011 Neg OF -8 -8 -16 01000 0101 1101 ok 25770010 0101 0111 ok 5 5 10 -60101 0101 0 1010 Pos OFJ. E. Jones OSU CSE 2421  How to determine a negative value in B2T?◦ Reminder: B2U = B2T (for positive values)◦ To get B2T representation of negative value of a B2U bit patterninvert the B2U bit pattern and add 1 Two’s complement (B2T) negation (for a w bit representation):◦ -2w-1 is its own additive inverse Additive inverse is the value added to a given value to get 0.◦ To get additive inverse of other values, use integer negation (invert the bits, and add 1) [this also works for -2w-1 ]J. E. Jones OSU CSE 2421GIVEN HEX binarybase 10 064 -128 -125 -3-1base 10 0 -64 -128 1253NEGATIONbinary* HEX0x00 0000 0000 0x40 0100 0000 0x80 1000 0000 0x83 1000 00110000 0000 0x000xFD 1111 1101 0xFF 1111 11110000 0011 0x03when w=8, -2w-1J. E. Jones10000 0001 0x01*binary = invert the bits and add 11100 0000 0xC0 1000 0000 0x800111 1101 0x7DOSU CSE 2421 #include #include void main() {
int n = 0;
printf(“neg of %d is %d “,n,-n);
n = 64;
printf(“
neg of %d is %d “,n,-n); n = -64;
printf(“
neg of %d is %d “,n,-n); n = INT_MIN;
printf(“
neg of %d is %d “,n,-n);
/* INT_MIN is defined in limits.h */
unsigned int a = 0;
printf(“

0 – 1 unsigned is %u “,a-1); printf(“
unsigned max is %u “, UINT_MAX); a = 5;
printf(“
neg of unsigned %d is %u”,a, -a); }
Output?
J. E. Jones

OSU CSE 2421
#include #include void main() {
}
int n = 0;
printf(“neg of %d is %d “,n,-n);
n = 64;
printf(“
neg of %d is %d “,n,-n);
n = -64;
printf(“
neg of %d is %d “,n,-n);
n = INT_MIN;
printf(“
neg of %d is %d “,n,-n); unsigned int a = 0;
printf(“

0 – 1 unsigned is %u “,a-1);
/*negation of 0 is 0*/
/*negation of 64 is -64*/
/*negation of -64 is 64*/
/*negation of -2147483648 is -2147483648 */
0x00000000-0x1=0xffffffff
/*0 – 1 unsigned is 4294967295 */ /*unsigned max is 4294967295*/ /*negation of unsigned 5 is 4294967291 */
printf(“
unsigned max is %u “, UINT_MAX); a = 5;
printf(“
neg of unsigned %d is %u”,a, -a);
J. E. Jones

J. E. Jones
OSU CSE 2421

OSU CSE 2421
#include void main(){
float y[9]={23.67, 23.50, 23.35, 23.00, 0, -23, -23.35, -23.5, -23.67}; int i;
for (i=0;i<9;i++) {printf(“y = %.4f %.2f %.1f %.0f
“, y[i], y[i],y[i], y[i]); }}/*OUTPUT ROUND TO NEAREST*/y= 23.6700y= 23.5000y= 23.3500y= 23.0000y= 0.0000y= -23.0000 -23.00 y= -23.3500 -23.35 y= -23.5000 -23.50 y= -23.6700 -23.6723.7 24 23.5 24 23.4 23 23.0 2323.67 23.50 23.35 23.000.000.0 0 -23.0 -23 -23.4 -23 -23.5 -24 -23.7 -24J. E. Jones