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 2030? 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.
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
23 22 21 20 CarryIn 1 1 0 0
OperandA 0 1 1 0 OperandB 0 1 1 1
Sum 1 1 0 1 CarryOut 0 1 1 0
Notes:
◦ 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 (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
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 < 1uFalse
◦ Unsigned relational operator
◦ -1 is stored as 0xFFFFFFFF (4-byte integer)
Interpreted as an unsigned value, this is the largest integer that fits in 32 bits!
NOTE: For integers, w = 32 on stdlinux
J. 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 bit
pattern is assigned to y:
◦ 27 = 0000 0000 0001 1011 ◦ -27 = 1111 1111 1110 0101
J. 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 1111 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 2421
HEX UNSIGNED – B2U
TWO'S COMP – B2T
orig trunc orig
trunc 0
2
1
3
7
orig
0 0 2 2
0 0(0000)(000) 0
22
(0010) (010) 2
91
(1001) (001) 9
-7 1 -5 3 -1 -1
B3
(1011) (011) 11
F7
(1111) (111) 15
trunc
J. E. Jones
OSU 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 < -8
1000 1000 1 0000 Neg OF -8 5 -3 -3
When we only have w bits, extra bits drop into the “bit bucket”.
1000 1011 1 0011 Neg OF -8 -8 -16 0
1000 0101 1101 ok 2577
0010 0101 0111 ok 5 5 10 -6
0101 0101 0 1010 Pos OF
J. 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
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 2421
GIVEN HEX binary
base 10 0
64 -128 -125 -3
-1
base 10 0 -64 -128 125
3
NEGATION
binary* HEX
0x00 0000 0000 0x40 0100 0000 0x80 1000 0000 0x83 1000 0011
0000 0000 0x00
0xFD 1111 1101 0xFF 1111 1111
0000 0011 0x03
when w=8, -2w-1
J. E. Jones
1
0000 0001 0x01
*binary = invert the bits and add 1
1100 0000 0xC0 1000 0000 0x80
0111 1101 0x7D
OSU CSE 2421
#include
int n = 0;
printf(“neg of %d is %d “,n,-n);
n = 64;
printf(“\nneg of %d is %d “,n,-n); n = -64;
printf(“\nneg of %d is %d “,n,-n); n = INT_MIN;
printf(“\nneg of %d is %d “,n,-n);
/* INT_MIN is defined in limits.h */
unsigned int a = 0;
printf(“\n\n0 – 1 unsigned is %u “,a-1); printf(“\n unsigned max is %u “, UINT_MAX); a = 5;
printf(“\nneg of unsigned %d is %u”,a, -a); }
Output?
J. E. Jones
OSU CSE 2421
#include
}
int n = 0;
printf(“neg of %d is %d “,n,-n);
n = 64;
printf(“\nneg of %d is %d “,n,-n);
n = -64;
printf(“\nneg of %d is %d “,n,-n);
n = INT_MIN;
printf(“\nneg of %d is %d “,n,-n);
unsigned int a = 0;
printf(“\n\n0 – 1 unsigned is %u “,a-1); printf(“\n unsigned max is %u “, UINT_MAX); a = 5;
printf(“\nneg of unsigned %d is %u”,a, -a);
/*negation of 0 is 0*/
/*negation of 64 is -64*/
/*negation of -64 is 64*/
/*negation of -2147483648 is -2147483648 */
/*0 – 1 unsigned is 4294967295 */ /*unsigned max is 4294967295*/
/*negation of unsigned 5 is 4294967291 */
J. E. Jones
J. E. Jones
OSU CSE 2421
OSU CSE 2421
#include
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\n", y[i], y[i],y[i], y[i]); }
}
/*OUTPUT ROUND TO NEAREST*/
y= 23.6700
y= 23.5000
y= 23.3500
y= 23.0000
y= 0.0000
y= -23.0000 -23.00 y= -23.3500 -23.35 y= -23.5000 -23.50 y= -23.6700 -23.67
23.7 24 23.5 24 23.4 23 23.0 23
23.67 23.50 23.35 23.00
0.00
0.0 0 -23.0 -23 -23.4 -23 -23.5 -24 -23.7 -24
J. E. Jones