Microsoft PowerPoint – 17_Int_Representation_and_Basic_Operations
O
SU
C
SE
2
42
1
J.E.Jones
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
O
SU
C
SE
2
42
1
J. E. Jones
Addition: 456
289
745
Did you know this is what you were really doing?
102 101 100
Carry In 1 1 0
Operand A 4 5 6
Operand B 2 8 9
Sum Out 7 4 5
Carry Out 0 1 1
O
SU
C
SE
2
42
1
J. E. Jones
http://www.tutorialspoint.com/computer_logical_organization/logic_gates.htm
In general, I consider this a topic for ECE 2020/2060
For Systems, just know what kind of gates there are and, given 2 input,
what the analogous output will be.
O
SU
C
SE
2
42
1
J. E. Jones
1 and 3 exclusive OR (^)
2 and 4 and (&)
5 or (|)
01100 carry*
0110 a
0111 b
01101 a+b
* Always start
with a carry-in
of 0
Did it work?
What is a?
What is b?
What is a+b?
What if 8 bits instead of 4?
O
SU
C
SE
2
42
1
J. E. Jones
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.
O
SU
C
SE
2
42
1
J. E. Jones
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.
23 22 21 20
Carry In 1 1 0 0
Operand A 0 1 1 0
Operand B 1 1 1 1
Sum Out 0 1 0 1
Carry Out 1 1 1 0
O
SU
C
SE
2
42
1
J. E. Jones
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
O
SU
C
SE
2
42
1
J. E. Jones
We can use hexadecimal values to represent 4
binary bits. This typically makes them easier to
read
Note that the binary value 1010 can represent:
A
10
-6
The only difference is how we wish to interpret
those 4 bits.
BINARY
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
B2U
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
B2T
0
1
2
3
4
5
6
7
-8
-7
-6
-5
-4
-3
-2
-1
HEX
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
O
SU
C
SE
2
42
1
J. E. Jones
B2U – Binary to unsigned
B2T – Binary to two’s-complement
B2O – Binary to ones’-complement
B2S – Binary to sign-magnitude
O
SU
C
SE
2
42
1
J. E. Jones
Binary to Decimal
One’s complement = B2O
◦ 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, invert all bits
1010 changes to 0101
0101= 5, so final value is -5
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 all 1s no matter
what w equals),
BINARY
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
B2O
0
1
2
3
4
5
6
7
-7
-6
-5
-4
-3
-2
-1
-0
O
SU
C
SE
2
42
1
J. E. Jones
Binary to Decimal
Sign Magnitude = B2S
◦ 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),
BINARY
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
B2S
0
1
2
3
4
5
6
7
-0
-1
-2
-3
-4
-5
-6
-7
O
SU
C
SE
2
42
1
J. E. Jones
One’s complement – bit
complement of B2U for negatives
Signed Magnitude – left most bit
for sign, B2U for the remaining
w-1 bits
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)
CODE
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
B2U
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
B2T
0
1
2
3
4
5
6
7
-8
-7
-6
-5
-4
-3
-2
-1
B2O
0
1
2
3
4
5
6
7
-7
-6
-5
-4
-3
-2
-1
-0
B2S
0
1
2
3
4
5
6
7
-0
-1
-2
-3
-4
-5
-6
-7
O
SU
C
SE
2
42
1
J. E. Jones
Casting – signed to unsigned,
unsigned to signed…
Changes the meaning or
interpretation of the value, but
not the bit representation
if(x>=0) && (x<=3) if((unsigned)x<=3) CODE 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 B2U 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 B2T 0 1 2 3 4 5 6 7 -8 -7 -6 -5 -4 -3 -2 -1 O SU C SE 2 42 1 J. E. Jones 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) O SU C SE 2 42 1 J. E. Jones 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) ◦ 1 is stored as 0x00000001 Interpreted as an unsigned value, this is the largest integer that fits in 32 bits! NOTE: For integers, w = 32 on stdlinux O SU C SE 2 42 1 J. E. Jones Sign Extension ◦ For unsigned fill to left with zero ◦ For signed repeat sign bit (MSB, or most significant bit) char x = -27; /*w = 8 in C */ short y; /*w = 16 on stdlinux for short */ ◦ 27 = 0001 1011 ◦ -27 = 1110 0101 /* invert +1 to get 2’s complement */ ◦ ?? = 1110 0101 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 ◦ ??= 0000 0000 1110 0101 O SU C SE 2 42 1 J. E. Jones 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 */ O SU C SE 2 42 1 J. E. Jones When the high order w-k bits are dropped when truncating a w-bit number to a k-bit number, does the value change? O SU C SE 2 42 1 J. E. Jones 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. O SU C SE 2 42 1 J. E. Jones HEX UNSIGNED – B2U TWO'S COMP – B2T orig trunc orig trunc orig trunc 0 (0000) 0 (000) 0 0 0 0 2 (0010) 2 (010) 2 2 2 2 9 (1001) 1 (001) 9 1 -7 1 B (1011) 3 (011) 11 3 -5 3 F (1111) 7 (111) 15 7 -1 -1 O SU C SE 2 42 1 J. E. Jones Unsigned Overflow when x+y > 2w – 1
Example:
Unsigned 4-bit BTU
• The processor only needs
to check carry-out from
most significant bits
• Overflow > 15
x y x+y result
8
1000
5
0101
13
1101
13
ok
8
1000
7
0111
15
1111
15
ok
12
1100
5
0101
17
10001
1
OF
When we only have w bits, extra bits drop
into the “bit bucket”. So, this 1 is gone and
we have overflow
O
SU
C
SE
2
42
1
J. E. Jones
Signed
Negative overflow when x+y < -2w-1
Positive overflow when x+y > 2w-1-1
• Result incorrect if
carry-in != carry out
of top bit (msb)
Example:
Signed 4-bit B2T
• Positive overflow > 7
• Negative overflow < -8
x y x+y result
-8
1000
-5
1011
-13
1 0011
3
Neg OF
-8
1000
-8
1000
-16
1 0000
0
Neg OF
-8
1000
5
0101
-3
1101
-3
ok
2
0010
5
0101
7
0111
7
ok
5
0101
5
0101
10
0 1010
-6
Pos OF
When we only have w bits, extra bits drop
into the “bit bucket”.
O
SU
C
SE
2
42
1
J. E. Jones
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 ]
O
SU
C
SE
2
42
1
J. E. Jones
GIVEN NEGATION
HEX binary base 10 base 10 binary* HEX
0x00 0000 0000 0 0 0000 0000 0x00
0x40 0100 0000 64 -64 1100 0000 0xC0
0x80 1000 0000 -128 -128 1000 0000 0x80
0x83 1000 0011 -125 125 0111 1101 0x7D
0xFD 1111 1101 -3 3 0000 0011 0x03
0xFF 1111 1111 -1 1 0000 0001 0x01
*binary = invert the bits and add 1
when w=8, -2w-1
O
SU
C
SE
2
42
1
J. E. Jones
#include
#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; /* INT_MIN is defined in limits.h */
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 %i is %u”,a, -a); }
Output?
O
SU
C
SE
2
42
1
J. E. Jones
#include
#include
int n = 0;
printf(“neg of %d is %d “,n,-n); /*negation of 0 is 0*/
n = 64;
printf(“\nneg of %d is %d “,n,-n); /*negation of 64 is -64*/
n = -64;
printf(“\nneg of %d is %d “,n,-n); /*negation of -64 is 64*/
n = INT_MIN;
printf(“\nneg of %d is %d “,n,-n); /*negation of -2147483648 is -2147483648 */
unsigned int a = 0;
printf(“\n\n0 – 1 unsigned is %u “,a-1); /*0 – 1 unsigned is 4294967295 */
0x00000000-0x1=0xffffffff
printf(“\n unsigned max is %u “, UINT_MAX); /*unsigned max is 4294967295*/
a = 5;
printf(“\nneg of unsigned %d is %u”,a, -a); /*negation of unsigned 5 is 4294967291 */
}
O
SU
C
SE
2
42
1
J. E. Jones
O
SU
C
SE
2
42
1
J. E. Jones
#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\n", y[i], y[i],y[i], y[i]);
}
}
/*OUTPUT ROUND TO NEAREST*/
y = 23.6700 23.67 23.7 24
y = 23.5000 23.50 23.5 24
y = 23.3500 23.35 23.4 23
y = 23.0000 23.00 23.0 23
y = 0.0000 0.00 0.0 0
y = -23.0000 -23.00 -23.0 -23
y = -23.3500 -23.35 -23.4 -23
y = -23.5000 -23.50 -23.5 -24
y = -23.6700 -23.67 -23.7 -24