Transcript Power Point version

Representing Numbers Using Bases
• Numbers in base 10 are called decimal numbers,
they are composed of 10 numerals ( ‫) ספרות‬.
9786 = 9*1000 + 7*100 + 8*10 + 6*1
= 9*103 + 7*102 + 8*101 + 6*100
• Numbers in base 2 are called binary numbers, they
are composed of the numerals 0 and 1.
110101 = 1*32 + 1*16 + 0*8 + 1*4 + 0*2 + 1*1
= 1*25 + 1*24 + 0*23 + 1*22 + 0*21 + 1*20
• 1111 1111 1111 1111 = 32768 + 16384 + 8192 +
4096 + 2048 + 1024 + 512 + 256 + 128 + 64 + 32 +
16 + 8 + 4 + 2 + 1 = 215 + 214 + … + 21 + 20 =
S 2n = 216 -1
1
Converting Between Bases
• From base 2 to base 10 is easy: just multiply each
numeral by its exponent. 1001b = 1*8 + 1*1 = 9d
• From base 10 to base 2 is slightly more
complicated: In a loop from 31 to 0 (in the case of a
32 bit word) perform the following:
– Divide the decimal number by 2n and write the
result in the nth position.
– Replace the number with the number minus the
result multiplied by 2n
– Decrement n by 1.
2
A Base Conversion Example
In C++ it looks like this:
for(n=31;n>=0;n--){
res = decimal/(int)pow(2,n);
decimal = decimal - res*(int)pow(2,n);
cout << res;
}
500/29 = 0 ; 500 - 0 = 500
4/23 = 0 ; 4 - 0 = 4
500/28 = 1 ; 500 - 256 = 244
244/27 = 1 ; 244 - 128 = 116
116/26 = 1 ; 116 - 64 = 52
52/25 = 1 ; 52 - 32 = 20
20/24 = 1 ; 20 -
16 =
4/22 = 1 ; 4 - 4 = 0
0/21 = 0 ; 0 - 0 = 0
0/20 = 0 ; 0 - 0 = 0
500d = 111110100b
4
3
Representation (‫ )יצוג‬of Numbers
• int, long, short, char - positive numbers are
stored as a binary number where the MSB
(Most Significant Bit) is 0
A short is represented by 16 bits
100d = 26 + 25 + 22 =
0000000001100100
An int is represented by 32 bits
65545d = 216 + 23 + 20 =
00000000000000010000000000001001
A char is represented by 8 bits
‘a’ = 48d = 25 + 24 = 00110000
4
Signed and Unsigned Numbers
• In order to calculate both positive and negative
numbers we must be able to distinguish (‫)להבדיל‬
between them.
• The most obvious solution is to add a bit that
represents the sign. The name of this scheme is
called: sign and magnitude (‫)גודל‬.
• There were several problems with this scheme:
– where do we put the sign?
– an extra step is needed to calculate the sign bit
– there is both a positive and negative zero
Thus a new representation was chosen
5
Two's Complement
• In the representation chosen leading 0s means
positive and leading 1s means negative.
• The positive half of the numbers from 0 to
2,147,483,647d (231 -1) uses the same
representation as before.
• The smallest negative number is -2,147,483,648
(-231) and is represented by 10000…00000b
• It is followed by -2,147,483,647 (1000…0001b) up
to -1 (1111…1111b).
• There is a negative number (-231) with no positive
partner, beware when programming.
• The sum of a number and
its inverse (‫ )נגדי‬is -1.
6
Negative Integers
• Negative integers are represented using the two'scomplement (‫ )משלים לשניים‬method. The number is
represented in binary, the bits are flipped and 1 is
added. Thus the MSB is always 1
• Thus in a char:
-100d = -01100100 = 10011011 + 1 = 10011100
11111111 = 00000000 + 1 = -1d
-128d = -10000000 = 01111111 + 1 = 10000000
11000101 = 00111010 + 1 = 00111011 = -59d
• In a short:
-25,000d = -0110000110101000 =
1001111001010111 + 1 = 10011110011000
7
Unsigned Integers
• Are stored as binary numbers. The MSB (sign bit)
can be 1 or 0, the number is still positive.
Thus in a char:
10011100 = 27 + 24 + 23 + 22 = 156
11111111 = 27 + … + 20 = 28 - 1 = 255
• A problem arises when we have to compare
numbers. How do we know if the number is an
unsigned large number or a negative number. The
solution is to add instructions which handle
unsigned numbers.
sltu $t0,$s0,$s1
sltiu $t0,$s0,100
8
Hexadecimal Numbers
• Number in base 16 are called hexadecimal
numbers, they are composed of 16 numerals
(0-9,a-f).
9786hex = 9*163 + 7*162 + 8*161 + 6*160 =
= 9*4096 + 7*256 + 8*16 + 6*1 = 38790d
0xabcdef = 10*165 + 11*164 + 12*163 + 13*162 +
14*161 + 15*160 = 11259375d
• The conversion from binary to hex is very easy,
each hex digit is 4 binary digits:
0x0 = 0000 0x1 = 0001 0x2 = 0010 0x3 = 0011
0x4 = 0100 0x5 = 0101 0x6 = 0110 0x7 = 0111
0x8 = 1000 0x9 = 1001 0xa = 1010 0xb = 1011
0xc = 1100 0xd = 1101 9 0xe = 1110 0xf = 1111
Binary to Hexadecimal
• Using the previous table it is easy to represent 32
bit binary numbers in a short form:
0100 1100 0010 1101 1000 1100 0111 1001 =
4
a
2
d
8
c
7
9 =
0x4a2d8c79.
• Conversion from decimal to hexadecimal is similar
to converting decimal to binary.
for(n=7;n>=0;n--){
res = decimal/(int)pow(16,n);
decimal = decimal - res*(int)pow(16,n);
if(res>9) cout << (char)((res -10) + 'a');
else
cout << res;
}
10
Addition and Subtraction
• Lets add 6 to 7:
(0)
(0)
(1)
(1)
(0)
(Carries)
00…00111 = 7d
0
0
0
1
1
1
00…00110 = 6d
0
0
0
1
1
0
(0) 0 (0) 0 (0) 1 (1) 1 (1) 0 (0) 1
00…01101 = 13d
• Subtraction uses addition, the operand is simply
negated before being added:
7 - 6 = 7 + (-6) =
00…00111 = 7d
11…11010 = -6d
00…00001 = 1d
• The pseudoinstruction neg $t0,$t1 #$t0=-$t1
is implemented by: sub $t0,$zero,$t1
11
Overflow (‫)גלישה‬
• Overflow occurs when the result of a operation can't be
represented by the hardware. This can happen when we
add two numbers of the same sign or subtract two large
numbers of opposing signs.
• Overflow is detected by the following table:
Operation
A
B
Result
A+B
>=0 >=0
<0
A+B
<0
<0
>=0
A- B
>=0
<0
<0
A- B
<0 >=0
>=0
• How is overflow detected in unsigned numbers? It isn't.
The instructions add, addi, sub cause exceptions
when overflow occurs. The instructions addu, addiu,
subu ignore overflow. Guess what instructions MIPS C
compilers use?
12
Logical Operations
• All processors provide logical instructions that
operate on the bits of the operands.
• and, andi, or, ori, xor and xori perform
the AND, OR and XOR (eXlusive OR) operations.
• If $t0 contains 10 and $t1 contains 9 then:
and $t2,$t0,$t1 # $t2=10&9=8
or $t2,$t0,$t1 # $t2=10|9=11
xor $t2,$t0,$t1 # $t2=10&9=3
• MIPS provides a NOR (Not OR) instruction as well:
nor $t2,$t0,$t1 # $t2=~(10|9)=4
1100 NOR 1001 = 0100
• The logical NOT is a pseduinstruction in MIPS.
13
Shift Instructions
• In order to access bits or fields of bits the logical
operations and the shift operations are used.
• They move all bits in a word to the left or right, filling
the emptied bits with 0s. The instructions are shift left
logical (sll) , and shift right logical (srl).
These 2 instructions use the shamt field of the R-type
instruction.
• sll $t0,$t1,6 # $t0 = $t1<<8;
0000 0000 0000 1101 -> 0000 1101 0000 0000
srl $t2,$t0,3 # $t2 = $t0>>3;
0000 1101 0000 0000 -> 0000 0001 1010 0000
• The instructions sllv and slrv contain the shift
amount in a register.
sllv $t0,$t1,$t2 # $t0=$t1>>$t2
14
The Basic Building Blocks
1. AND gate (c = a . b)
a
c
b
2. OR gate (c = a + b)
a
c
b
3. Inverter (c = a)
a
4. Multiplexor
(if d = = 0, c = a;
else c = b)
c
d
a
0
c
b
1
15
a
b
c=a. b
0
0
0
0
1
0
1
0
0
1
1
1
a
b
c=a+b
0
0
0
0
1
1
1
0
1
1
1
1
a
c=a
0
1
1
0
d
c
0
a
1
b
Building an ALU
• The arithmetic logic unit or ALU is the device that
performs arithmetic and logical operations in the
computer. We will build it out of 4 basic building
blocks. The AND gate, Or gate, Inverter and
Multiplexor.
Operation
• We have now
a 1-bit logical
unit for
a
AND and OR:
0
Result
1
b
16
1-bit Full Adder
• 1-bit addition has 3 inputs (a, b, CarryIn) and 2
outputs (Sum, CarryOut).
• The CarryOut is set if at least 2 out of a, b, and CarryIn
are 1.
• The Sum is set when exactly one input is 1 or all three
are 1. CarryIn
CarryIn
a
a
Sum
b
b
CarryOut
17
CarryOut
1-bit ALU
• We now have a 1-bit ALU that can perform AND,
Operation
OR and addition.
CarryIn
• By connecting 32 of
these 1-bit ALUs we can a
0
build a 32-bit ALU. The
CarryOut of the N 1-bit ALU
1
Result
is connected to the CarryIn
of the N+11-bit ALU. This
2
b
adder is called a ripple
carry or ripple adder. A single
CarryOut
carry out in the least significant
bit (LSB) can cause a carry out of the MSB.
18
32-bit ALU
CarryIn
a0
b0
Operation
CarryIn
ALU0
Result0
CarryOut
• Subtraction is performed by
adding the negative value.
Thus we have to add an
inverter to our ALU.
Binvert
a1
b1
CarryIn
CarryIn
ALU1
Operation
Result1
CarryOut
a
0
a2
b2
CarryIn
ALU2
Result2
1
CarryOut
0
b
2
1
a31
b31
CarryIn
ALU31
Result31
19
CarryOut
Result
Adding the slt instruction
• slt produces 1 if rs < rt.
Thus slt will set all but the
LSB to 0 with the LSB
being dependent on the
result. We add a new input
to the multiplexor called
Less, this will be the output
of slt. To set the LSB we
perform rs-rt. If the result is
negative we must set the
output. Thus the sign bit is
the correct output. But it
isn't the output of slt, so a
new output is added to the
1-bit ALU of the MSB, Set.
Binvert
Operation
CarryIn
a
0
1
Result
b
0
2
1
Less
3
a.
CarryOut
Binvert
Operation
CarryIn
a
0
1
Result
b
0
2
1
Less
3
Set
20
b.
Overflow
detection
Overflow
The New ALU
Binvert
CarryIn
a0
b0
CarryIn
ALU0
Less
CarryOut
a1
b1
0
CarryIn
ALU1
Less
CarryOut
a2
b2
0
CarryIn
ALU2
Less
CarryOut
Operation
Result0
Result1
Result2
CarryIn
a31
b31
0
CarryIn
ALU31
Less
Result31
Set
Overflow
21
• As we can see all
the Less inputs are
hardwired to zero
except the LSB
Less input which is
wired to the Set
output of the MSB
1-bit ALU.
Comparison in the ALU
• In order to
implement the
bne and beq
instructions we
must compare
between two
numbers. a is
equal to b if a-b=0
The output line
Zero is set to 1 if
all the Results are
0, which happens
if a == b.
Bnegate
Operation
a0
b0
CarryIn
ALU0
Less
CarryOut
Result0
a1
b1
0
CarryIn
ALU1
Less
CarryOut
Result1
a2
b2
0
CarryIn
ALU2
Less
CarryOut
Result2
a31
b31
0
CarryIn
ALU31
Less
22
Zero
Result31
Set
Overflow
ALU Summary
• Our ALU can perform AND, OR, Addition,
Subtraction, Set on less then (slt), and Equality
tests. The universal symbol of the ALU is shown
here:
ALU operation
a
ALU
b
CarryOut
23
Zero
Result
Overflow