[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 Programmers 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 3exclusive OR (^) 2 and 4and (&)
5or (|)
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.
Lets 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 Unsignednon-negative numbers (>=0)
Minimum value: 0
Maximum value: 2w-1
Signednegative, zero, and positive numbers
Minimum value: -2w-1 (2s 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 twos-complement B20 Binary to ones-complement B2S Binary to sign-magnitude
J. E. Jones

OSU CSE 2421
Binary to Decimal
Ones complement = B2O
BINARY B2O
0000 0
0001 1
Most significant digit (left-most bit) represents
the sign bit 0010
if sign bit = 1, then its 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 its 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
Ones 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 (thats 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 doesnt 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 < 1uFalse 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 2s 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 2s 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 patterninvert the B2U bit pattern and add 1 Twos 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