Transcript ללא כותרת שקופית

Goal: Representing Numbers in Binary
Base 10 (decimal) - Numbers are represented
using 10 numerals: 0, 1, 2, 3 … 9
Base 2 (binary) - Numbers are represented using 2
numerals: 0, 1
Base 10 - Each position represents a power of 10:
101 = 1*102 + 0*101 + 1*100 = 100 + 1
110 = 1*102 + 1*101 + 0*100 = 100 + 10
Base 2 - Each position represents a power of 2:
101b = 1*22 + 0*21 + 1*20 = 100b + 1b = 4 + 1
110b = 1*22 + 1*21 + 0*20 = 100b + 10b = 4+2
Computer
Structure - Computer Arithmetic
1/15
Numbers in base 10 are called decimal numbers,
they are composed of 10 numerals ( ‫) ספרות‬.
d3d2d1d0 = d3*103 + d2*102 + d1*101 + d0*100
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.
b3b2b1b0 = b3*23 + b2*22 + b1*21 + b0*20
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 = 2n+1 - 1 = 216 -1
Computer
Structure - Computer Arithmetic
Converting from Binary to Decimal
Easy: Multiply each numeral by its exponent.
1001b = 1*23 + 1*20 = 1*8 + 1*1 = 9d
0111b = 0*23 + 1*22 + 1*21 + 1*20
= 100b + 10b + 1b
=4+2+1
=7
110110b = 1*25 + 1*24 + 0*23 + 1*22 + 1*21
= 100000b + 10000b + 100b + 10b
= 32 + 16 + 4 + 2
= 54
Computer
Structure - Computer Arithmetic
2/15
Given a string that holds a 32 digit binary number
called binary[32];
 unsigned decimal = 0;
unsigned power = ~0; //all bits are now ones
for(i=31;i>=0;i--){
decimal += binary[i]*power;
power = power >> 1;
}
The powers of 2:
20 = 1
21 = 2
22 = 4
23 = 8
24 = 16
25 = 32
26 = 64
27 = 128
28 = 256
29 = 512 210 = 1024 = 1K
211 = 2048
212 = 4096 213 = 8192
216 = 65536
220 = 1048576 = 1M
Computer
Structure - Computer Arithmetic
Converting From Decimal to Binary
In C++ it looks like this:
int res;
int decimal;
int power;
for(n=31;n>=0;n--){
power = pow(2,n);
res = decimal/power;
decimal = decimal - res*power;
cout << res;
}
Computer
Structure - Computer Arithmetic
3/15
A Base Conversion Example
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
4/22 = 1 ; 4 - 4 = 0
0/21 = 0 ; 0 - 0 = 0
0/20 = 0 ; 0 - 0 = 0
500d = 111110100b
Computer
Structure - Computer Arithmetic
4/15
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 (2 bytes)
100d = 26 + 25 + 22 =
0000000001100100
An int is represented by 32 bits (4 bytes)
65545d = 216 + 23 + 20 =
00000000000000010000000000001001
A char is represented by 8 bits (1 byte)
‘a’ = 48d = 25 + 24 = 00110000
Computer
Structure - Computer Arithmetic
5/15
Signed and Unsigned Numbers
How do we distinguish (‫ )להבדיל‬between them?
Solution: Use 1 bit to represents the sign. The
name of this scheme is called:
sign and magnitude (.)‫גודל‬
10001111b = -15
00001111b = +15 (8 bit numbers)
There are several problems with this scheme:
where do we put the sign?
an extra step is needed to calculate the sign bit
• Add the magnitudes.
• Calculate the sign.
there is both a positive and negative zero
10000000b = -0
00000000b = +0
Computer
Structure - Computer Arithmetic
6/15
Two's Complement
New Solution: Leading 0s means positive and
leading 1s means negative.
01111111b > 0
10000000b < 0 (8 bit numbers)
The largest positive number is:
2,147,483,647d (231 -1) = 01111…11111b
The smallest negative number is:
-2,147,483,648d (-231) = 10000…00000b
It is followed by -2,147,483,647d (1000…0001b) up
to -1 (1111…1111b).
The sum of a number and its inverse (‫ )נגדי‬is -1.
Computer
Structure - Computer Arithmetic
7/15
Negative Decimal to Binary
Translate the number to binary.
Flip the bits (1 -> 0, 0 -> 1)
Add 1

-100d = -01100100 = 10011011 + 1 = 10011100
11111111b = 00000000 + 1 = -1d
-128d = -10000000 = 01111111 + 1 = 10000000
11000101b = 00111010 + 1 = 00111011 = -59d
In a short:
-25,000d = -0110000110101000 =
1001111001010111 + 1 = 10011110011000b
Computer
Structure - Computer Arithmetic
8/15
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:
10011100b = 27 + 24 + 23 + 22 = 156d
11111111b = 27 + … + 20 = 28 - 1 = 255d
Problem: How do we compare signed and
unsigned numbers?
Solution: Add instructions to compare unsigned
numbers.
sltu $t0,$s0,$s1
sltiu $t0,$s0,100
Computer
Structure - Computer Arithmetic
9/15
Hexadecimal Numbers
Numbers 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 0xe = 1110 0xf = 1111
Computer
Structure - Computer Arithmetic
10/15
Binary <-> Hexadecimal
Using the previous table it is easy to represent 32
bit binary numbers in a short form:
0100 1010 0010 1101 1000 1100 0111 1001 =
4
a
2
d
8
c
7
9 =
0x4a2d8c79.
0x12390ab4 =
0001 0010 0011 1001 0000 1010 1011 0100
1
2
3
9
0
a
b
4
0xffffffff =
1111 1111 1111 1111 1111 1111 1111 1111
Every 2 Hex digits is a byte
Computer
Structure - Computer Arithmetic
11/15
Conversion from decimal to hexadecimal is similar
to converting decimal to binary.
int res;
int decimal;
int power;
for(n=7;n>=0;n--){
power = pow(16,n);
res = decimal/power;
decimal = decimal - res*power;
if(res>9)
cout << (char)((res -10) + 'a');
else
cout << res;
}
Computer
Structure - Computer Arithmetic
Addition
Lets add 6 to 7:
00…00111 = 7d
00…00110 = 6d
00…01101 = 13d
Lets add 11 to 5:
00…01011 = 11d
00…00101 = 5d
00…10000 = 16d
(0)
(0)
(1)
(1)
(0)
(Carries)
0
0
0
1
1
1
0
0
0
1
1
0
(0) 0
(0) 0
(0) 1
(1) 1
(1) 0
(0) 1
 Instructions that end with an i (addi, subi, andi)
perform an operation between a register and an immediate:
addi $t0,$t1,20 # $t0 =$t1 + 20
Computer
Structure - Computer Arithmetic
12/15
Subtraction
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 #$zero is always
Computer
Structure - Computer Arithmetic
0
13/15

Overflow occurs
when the result of a operation can't be
Overflow
(‫)גלישה‬
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
A+B
A- B
A- B
A
>=0
<0
>=0
<0
B
>=0
<0
<0
>=0
Result
<0
>=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?
Computer Structure - Computer Arithmetic
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
not $t2,$t0
# $t2=~9=-10 (8 bits)
MIPS provides a NOR (Not OR) instruction as well:
nor $t2,$t0,$t1 # $t2=~(10|9)=4
Computer
Structure - Computer Arithmetic
14/15
Shift Instructions
 shift operations move the 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,8 # $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
Computer
Structure - Computer Arithmetic
15/15