Transcript Representing Numbers - UCL Computer Science

Representing Numbers
B261 Systems Architecture
Previously
• Computer Architecture
– Common misconceptions
– Performance
• Instruction Set (MIPS)
– How data is moved inside a computer
– How instructions are executed
Outline
• Numbers
– Limitations of computer arithmetic
• How numbers are represented
internally
– Representing positive integers
– Representing negative integers
• Addition
• Bit-wise operations
Binary Representation
• Computers internally represent numbers in binary form
– The sequence of binary digits
» dn-1 dn-2 ... d1 d0 two
– At its simplest, this represents the decimal number which
is the sum of terms 2i for each di = 1.
» Eg, 10111two = 16ten+4ten+2ten+1ten = 23ten
» d0 is called the ‘least significant bit’ LSB
» dn-1 is called the ‘most significant bit’ MSB
– But we will need to use different meanings for the bits in
order to represent negative or floating-point numbers.
Range of Positive Numbers
and Word Lengths
• For an n-bit word length
• 2n different numbers can be represented
* including zero.
• 0,1,2,..., ((2n) -1)
(if only want +ve numbers)
• A 3-bit word length would support
• 0,1,2,3,4,5,6,7
• MIPS has a 32-bit word length
• 232 different numbers can be represented
• 0,1,2,..., ((232)-1)
(= 4,294,967,295).
Negative Numbers
• The range afforded by the word length must
simultaneously support both positive and negative
numbers, equally.
• Two requirements:
– There must be a way, within one word, to tell if it
represents a positive or negative number, and its value.
– A positive number x, and its complement (-x) must
clearly add to zero
» x + (-x) = 0.
Two’s Complement
• Example of n=3 bit word:
• 000 = 0
• 001 = 1
• 010 = 2
• 011 = 3
• 100 = -4
• 101 = -3
• 110 = -2
• 111 = -1
For positive numbers the
MSB (‘sign bit’) is always 0
For negative numbers the
MSB (‘sign bit’) is always 1
Two’s complement
• In general for a n-bit word
– There will be positive numbers (and zero)
» 0,1,2, … , ((2n-1) - 1)
– Negative numbers
» -(2n-1), … , -1
– The highest positive number is ((2n-1) - 1)
– The lowest negative numbers is -(2n-1 )
– Note the slight imbalance of positive and
negative.
Conversion
• For an n-bit word, suppose that dn-1 is
the sign bit.
– Then the decimal value is:
» (-dn-1)* (2n-1) + the usual conversion of the
remainder of the word.
– Eg, n=3, then
» 101 = (-1 * 4) + 0 + 1 = -4 + 1 = -3
» 011 = (0 * 4) + 2 + 1 = 0 + 3 = 3
Negating a Number
• There is a simple two-step process for
negation (eg, turn 3 = 011 into -3 = 101):
• invert every bit (e.g. replace 011 by 100)
• add 1 (e.g. 100+1 = 101).
• Example, 4-bit word 1101
• 1101 = -8 + 4 + 0 + 1 = -3
» 3 = 0011
» Invert bits: 1100
» add 1: 1101 = -3 as required.
Sign Extension
• Turning an n-bit representation into one
with more bits
– Eg, in 3 bits the number -3 is 101
– In 4 bits the number -3 is 1101
• Replicate the sign bit from the smaller
word into all extra slots of larger word
– For 5-bit word from 3 bits: 11101 = -3
– For 5-bit word from 4 bits: 11101 = -3
Integer Types
• Some languages (e.g. C++) support two
types of int: signed and unsigned.
• Signed integers have their MSB treated as
a sign bit
– so negative numbers can be represented
• Unsigned integers have their MSB treated
without such an interpretation (no
negative numbers).
Signed/Unsigned Int
• Suppose we had a 4-bit word, then
• int x;
» x could have range 0 to 7 positive
» and -8 to -1 negative
• unsigned int x;
» x has range 0 to 15 only.
Addition
• Addition is carried out in the same way
as decimal arithmetic:
» 0101
» 0001 +
» 0110
• Subtractions involve negating the
relevant number:
» 0101 - 0011 =
» 0101 + 1101 = 0010
Overflow
• Since there are only a fixed set of bits
available for arithmetic things can go
wrong:
• Consider n=4, and 0110 + 0101 (6+5).
» 0110
» 0101 +
» 1011
• But 1011 = -8 + 2 + 1 = -5 !
Overflow Examples
• Consider (6 - (-5))
• 0110 - 1011
» = 0110 + 0101
» = 1011
» = -8 + 3
» = -5
• -6 - 3
» = 1010 + 1101
» = 0111
»=7
Overflow Situations
•A+B
– where A>0, B>0, A+B too big, result negative
•A+B
– where A<0, B<0, A+B too small, result positive
•A-B
– where A>0, B<0, A-B too big, result negative
•A-B
– where A<0, B>0, A-B too small, result positive.
Bit Operations
• Shifts
– shift a word x bits to the right or left:
» 0110 shift left by 1 is 1100
» 0110 shift right by 1 is 0011
– In C++ shifts are expressed using <<,>>
» unsigned int y = x<<5, z = x>>3;
» means y is the value of x shifted 5 to left, and z is x
shifted 3 to the right.
– One application is multiplication/division by
powers of 2.
AND/OR
• AND is a bitwise operation on two words,
where for each corresponding bit a and b:
– a AND b = 1 only when a=1 and b=1, otherwise 0.
• OR is a bitwise operation, such that
– a OR b = 0 only if both a=0 and b=0, otherwise 1.
• For example:
– 1011 AND 0010 = 0010
– 1011 OR 0010 = 1011
New MIPS Operations
• add unsigned
– addu $1,$2,$3
» operands treated as unsigned ints.
• subtract unsigned
– subu $1,$2,$3
» operands treated as unsigned ints
• add immediate unsigned
– addiu $1,$2,10
» operands treated as unsigned ints
Exceptions
• Where the signed versions (add, addi,
etc) are used
– if there is overflow
» then an ‘exception’ is raised by the hardware
» control passes to a special procedure to
‘handle’ the exception, and then returns to the
next instruction after the one that raised the
exception.
More MIPS
• Load upper immediate
– lui $1,100
» $1 = 216 * 100
» (100, shifted left by 16 = upper half of the word).
• and, or, and immediate (andi), or
immediate (ori), shift left logical (sll), shift
right logical (srl)
– all of form $1,$2,$3 or $1,$2,10 (for immediate).
Summary
• Basic number representation (integers)
• Representation of negatives
• Basic arithmetic (+ and -)
• Logical operations
• Next time - building an ALU.