CS2421 Autumn 2013
CSE 2421
Integer Representation and Basic Operations
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
Remedial Math Review
456
289
745
Did you know this is what you were really doing?
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
Do you know how logic gates work?
http://www.tutorialspoint.com/computer_logical_organization/logic_gates.htm
Bit operations
4
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?
carry
0000 0110 a
0000 0111 b
0000 1101 a+b
4
Integer Addition
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.
Example 4 bit addition
Notes:
For addition, carry in to 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.
Carry In 1 1 0 0
Operand A 0 1 1 0
Operand B 0 1 1 1
Sum 1 1 0 1
Carry Out 0 1 1 0
Integer Representation
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-neg numbers (>=0)
Minimum value: 0
Maximum value: 2w-1
Signed neg, zero, and pos numbers
Minimum value: -2w-1 (2’s complement – see below)
(Reminder: exponent before negative sign)
Maximum value: 2w-1-1
7
Other encoding schemes… binary coded decimal (BCD), signed magnitude, one’s complement
7
Acronyms for Decoding Schemes
B2U – Binary to unsigned
B2T – Binary to two’s-complement
B20 – Binary to ones’-complement
B2S – Binary to sign-magnitude
2/25/2020
8
Integer Decoding
Binary to Decimal
Unsigned = simple binary = B2U
All digits represent a positive power of 2
NO NEGATIVE NUMBERS
0101 = 0*23+1*22+0*21+1*20 = 5
1111 = 1*23+1*22+1*21+1*20 = 15
1110 = 1*23+1*22+1*21+0*20 = 14
1001 = 1*23+0*22+0*21+1*20 = 9
Binary to Hexadecimal
Unsigned = simple binary = B2U
All digits represent a positive power of 2
NO NEGATIVE NUMBERS
0101 = 0*23+1*22+0*21+1*20 = 5
1111 = 1*23+1*22+1*21+1*20 = F
1110 = 1*23+1*22+1*21+0*20 = E
1001 = 1*23+0*22+0*21+1*20 = 9
Memorize how to “pattern match” binary values to decimal and hexadecimal values to make things easier for yourself
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
HEX
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
Integer Decoding
Binary to Decimal
Signed = two’s complement = B2T
Most significant digit (left-most bit) represents the sign bit
Remainder of digits represent positive powers of 2
ANY POSITIVE NUMBER: SAME AS B2U
1111 = -1*23+1*22+1*21+1*20 = -8 + 7 = -1
1110 = -1*23+1*22+1*21+0*20 = -8 + 6 = -2
1001 = -1*23+0*22+0*21+1*20 = -8 + 1 = -7
Another way, if sign bit = 1, then it’s a negative number and to get the magnitude of that number, invert all bits and add 1, make sign negative
1010 changes to 0101+1 = 0110
0110 = 6, so final value is -6
Note: hexadecimal values do not change. The values for 1000 through 1111 are 8 through F.
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
B2O & B2S
One’s complement – bit complement of B2U for negatives
Signed Magnitude – left most bit for sign, B2U for the remaining bits
Both include neg 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
11
Signed vs Unsigned
Casting – signed to unsigned, unsigned to signed…
Changes the meaning or interpretation of the value, but not the bit representation
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
limits.h http://en.wikibooks.org/wiki/C_Programming/C_Reference/limits.h
12
Signed vs Unsigned (cont)
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)
-2147483648 is the maximum negative number for signed 32 bits i.e -2^(32-1)
Note that +0 and −0 return TRUE when tested for zero, FALSE when tested for non-zero.
13
Signed vs. Unsigned
0 == 0u True
Unsigned relational operator
-1 < 1 True
Signed relational operator
-1 < 1u False
Unsigned relational operator
-1 is stored as 0xFFFFFFFF (4 byte int)
Interpreted as an unsigned value, this is the largest integer that fits in 32 bits!
NOTE: For integers, w = 32 on stdlinux
Sign Extend
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 */
y = (short)x;
x is sign-extended to 16 bits (on stdlinux), and this sign-extended bit pattern is assigned to y:
-27 = 1111 1111 1110 0101
15
15
Truncation
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 */
16
16
Truncation – loss of information
When the high order w-k bits are dropped when truncating a w-bit number to a k-bit number, does the value change?
17
17
Truncation – loss of information
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 of the 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.
18
18
Truncation
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
19
Integer Addition
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
With signed… have to worry about the sign changing as well as carry-out
Unsigned CF = carry-out = 1 (overflow for unsigned values)
Signed OF = have overflow when carry-in != carry-out
also… P+P=N or N+N=P (also a sign of overflow)
20
Integer Addition
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
With signed… have to worry about the sign changing as well as carry-out
Unsigned CF = carry-out = 1 (overflow for unsigned values)
Signed OF = have overflow when carry-in != carry-out
also… P+P=N or N+N=P (also a sign of overflow)
21
B2T integer negation
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 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 ]
Wednesday 2/26/2020
22
B2T integer negation
GIVEN NEGATION
HEX binary base 10 base 10 binary* HEX
0x00 0b 0000 0000 0 0 0b 0000 0000 0x00
0x40 0b 0100 0000 64 -64 0b 1100 0000 0xC0
0x80 0b 1000 0000 -128 -128 0b 1000 0000 0x80
0x83 0b 1000 0011 -125 125 0b 0111 1101 0x7D
0xFD 0b 1111 1101 -3 3 0b 0000 0011 0x03
0xFF 0b 1111 1111 -1 1 0b 0000 0001 0x01
*binary = invert the bits and add 1
What if unsigned? What happens if negate or have 0 and subtract one?
23
Sign/Unsign+Negation example
#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 %d is %u”,a, -a); }
Output?
signvsuns.c
24
Sign/Unsign+Negation example
#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 */
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 */
}
signvsuns.c
25
Rounding
We’ve talked about truncation… use graph example (just x axis)
-inf ——— -24 ———- -23 ———– -1 ———- 0 ———- 1 ——— 23 ——– 24 ——– +inf
Especially difference between round down and round towards zero
26
Rounding – our system
#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
But what about intermediate results??? Later…
27