Transcript Binary Numbers - La Salle University

Binary Numbers
Material on Data Representation can be found in
Chapter 2 of Computer Architecture (Nicholas Carter)
CSC 370 (Blum)
1
Why Binary?
• Maximal distinction among values 
minimal corruption from noise.
• Imagine taking the same physical attribute
of a circuit, e.g. a voltage lying between 0
and 5 volts, to represent a number.
• The overall range can be divided into any
number of regions.
CSC 370 (Blum)
2
Don’t sweat the small stuff
• For decimal numbers, fluctuations must be less
than 0.25 volts.
• For binary numbers, fluctuations must be less
than 1.25 volts.
5 volts
0 volts
Decimal
CSC 370 (Blum)
Binary
3
Range actually split in three
High
Forbidden
range
Low
CSC 370 (Blum)
4
It doesn’t matter ….
• Two of the standard voltages coming from a
computer’s power supply are ideally
supposed to be 5.00 volts and 12.00 volts
• Measurements often reveal values that are
slightly off – e.g. 5.14 volts or 12.22 volts
or some such value.
• So what, who cares.
CSC 370 (Blum)
5
How to represent big integers
• Use positional weighting, same as with
decimal numbers
• 205 = 2102 + 0101 + 5100
• 11001101 = 127 + 126 + 025 + 024
+ 123 + 122 + 021 + 120
= 128 + 64 + 8 + 4 + 1
= 205
CSC 370 (Blum)
6
Converting 205 to Binary
• 205/2 = 102 with a remainder of 1, place the
1 in the least significant digit position
1
• Repeat 102/2 = 51, remainder 0
0
CSC 370 (Blum)
1
7
Iterate
• 51/2 = 25, remainder 1
1
0
1
1
0
1
1
0
1
• 25/2 = 12, remainder 1
1
• 12/2 = 6, remainder 0
0
CSC 370 (Blum)
1
8
Iterate
• 6/2 = 3, remainder 0
0
0
1
1
0
1
1
1
0
1
1
1
0
1
• 3/2 = 1, remainder 1
1
0
0
• 1/2 = 0, remainder 1
1
CSC 370 (Blum)
1
0
0
9
Recap
1
1
0
0
1
1
0
1
127 + 126 + 025 + 024
+ 123 + 122 + 021 + 120
205
CSC 370 (Blum)
10
Finite representation
• Typically we just think computers do binary math.
• But an important distinction between binary math
in the abstract and what computers do is that
computers are finite.
• There are only so many flip-flops or logic gates in
the computer.
• When we declare a variable, we set aside a certain
number of flip-flops (bits of memory) to hold the
value of the variable. And this limits the values
the variable can have.
CSC 370 (Blum)
11
Same number, different
representation
•
•
•
•
•
•
5 using 8 bits
0000 0101
5 using 16 bits
0000 0000 0000 0101
5 using 32 bits
0000 0000 0000 0000 0000 0000 0000 0101
CSC 370 (Blum)
12
Adding Binary Numbers
• Same as decimal; if the sum of digits in a
given position exceeds the base (10 for
decimal, 2 for binary) then there is a carry
into the next higher position
+
CSC 370 (Blum)
1
3
3
7
9
5
4
13
Adding Binary Numbers
carries
1
+
CSC 370 (Blum)
1
1
1
0
1
0
0
1
1
1
39
0
1
0
0
0
1
1
35
1
0
0
1
0
1
0
74
14
Uh oh, overflow
• What if you use a byte (8 bits) to represent an
integer
1
1
1
1
0
1
0
1
0
1
0
170
1
1
0
0
1
1
0
0
204
0
1
1
1
0
1
1
0
118
???
• A byte may not be enough to represent the sum of
two such numbers.
CSC 370 (Blum)
15
Biggest
*
unsigned
integers
4 bit: 1111  15 = 24 - 1
8 bit: 11111111  255 = 28 – 1
16 bit: 1111111111111111  65535= 216 – 1
32 bit: 11111111111111111111111111111111 
4294967295= 232 – 1
• Etc.
*If one uses all of the bits available to represent only
positive counting numbers, one is said to be working
with unsigned integers.
•
•
•
•
CSC 370 (Blum)
16
Bigger Numbers
• High-level languages often offer a hierarchy of
types that differ in the number of bits used.
• You can represent larger numbers than allowed by
the highest type in the hierarchy by using more
words.
• You just have to keep track of the overflows to
know how the lower numbers (less significant
words) are affecting the larger numbers (more
significant words).
CSC 370 (Blum)
17
Negative numbers
• Negative x is the number that when added to x
gives zero
1
1
1
1
1
1
1
1
0
0
1
0
1
0
1
0
 x
1
1
0
1
0
1
1
0
 -x
0
0
0
0
0
0
0
0
• Ignoring overflow the two eight-bit numbers
above add up to zero
CSC 370 (Blum)
18
Two’s Complement: a two-step
procedure for finding -x from x
0
0
1
0
1
0
1
0
0
1
 x
• Step 1: exchange 1’s and 0’s
1
1
0
1
0
1
• Step 2: add 1 (to the lowest bit only)
1
CSC 370 (Blum)
1
0
1
0
1
1
0
 -x
19
Sign bit
• With the two’s complement approach, all
positive numbers start with a 0 in the leftmost, most-significant bit and all negative
numbers start with 1.
• So the first bit is called the sign bit.
• But note you have to work harder than just
strip away the first bit.
• 10000001 IS NOT the 8-bit version of –1
CSC 370 (Blum)
20
Add 1’s to the left to get the same
negative number using more bits
•
•
•
•
•
•
•
-5 using 8 bits
11111011
-5 using 16 bits
1111111111111011
-5 using 32 bits
11111111111111111111111111111011
When the numbers represented are whole numbers
(positive or negative), they are called integers.
CSC 370 (Blum)
21
3-bit signed and unsigned
7
6
5
4
3
2
1
0
1
1
1
1
0
0
0
0
CSC 370 (Blum)
1
1
0
0
1
1
0
0
1
0
1
0
1
0
1
0
3
2
1
0
-1
-2
-3
-4
0
0
0
0
1
1
1
1
1
1
0
0
1
1
0
0
1
0
1
0
1
0
1
0
Think of
driving a
brand new
car in
reverse.
What would
happen to the
odometer?
22
Biggest signed integers
4 bit: 0111  7 = 23 - 1
8 bit: 01111111  127 = 27 – 1
16 bit: 0111111111111111  32767= 215 – 1
32 bit: 01111111111111111111111111111111
 2147483647= 231 – 1
• Etc.
•
•
•
•
CSC 370 (Blum)
23
Most negative signed integers
4 bit: 1000  -8 = - 23
8 bit: 10000000  - 128 = - 27
16 bit: 1000000000000000  -32768= - 215
32 bit:
10000000000000000000000000000000 
-2147483648= - 231
• Etc.
•
•
•
•
CSC 370 (Blum)
24
Riddle
1
•
•
•
•
•
1
0
1
0
1
1
0
Is it 214?
Or is it – 42?
Or is it Ö?
Or is it …?
It’s a matter of interpretation
– How was it declared?
CSC 370 (Blum)
25
Hexadecimal Numbers
• Even moderately sized decimal numbers end
up as long strings in binary.
• Hexadecimal numbers (base 16) are often
used because the strings are shorter and the
conversion to binary is easier.
• There are 16 digits: 0-9 and A-F.
CSC 370 (Blum)
26
Decimal  Binary  Hex
•
•
•
•
•
•
•
•
0  0000  0
1  0001  1
2  0010  2
3  0011  3
4  0100  4
5  0101  5
6  0110  6
7  0111  7
CSC 370 (Blum)
•
•
•
•
•
•
•
•
8  1000  8
9  1001  9
10  1010  A
11  1011  B
12  1100  C
13  1101  D
14  1110  E
15  1111  F
27
Binary to Hex
• Break a binary string into groups of four
bits (nibbles).
• Convert each nibble separately.
1 1 1 0 1 1 0 0 1 0 0 1
E
CSC 370 (Blum)
C
9
28
Numbers from Logic
• All of the numerical operations we have talked
about are really just combinations of logical
operations.
• E.g. the adding operation is just a particular
combination of logic operations
• Possibilities for adding two bits
–
–
–
–
0+0=0 (with no carry)
0+1=1 (with no carry)
1+0=1 (with no carry)
1+1=0 (with a carry)
CSC 370 (Blum)
29
Addition Truth Table
INPUT
OUTPUT
A
B
Sum
A XOR B
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
CSC 370 (Blum)
Carry
A AND B
30
Multiplication: Shift and add

+
CSC 370 (Blum)
1
1
0
0
1
1
0
0
0
1
1
1
0
0
1
0
0
0
0
0
0
0
1
0
1
1
1
1
shift
shift
0
1
1
31
Fractions
• Similar to what we’re used to with decimal
numbers
3.14159 =
3 · 100 + 1 · 10-1 + 4 · 10-2 + 1 · 10-3
+ 5 · 10-4 + 9 · 10-5
1 · 21 + 1 · 20 + 0 · 2-1 + 0 · 2-2
+ 1 · 2-3 + 0 · 2-4 + 0 · 2-5
+ 1 · 2-6
(11.001001  3.140625)
11.001001 =
CSC 370 (Blum)
32
Converting decimal to binary II
• 98.61
– Integer part
•
•
•
•
•
•
•
98 / 2
49 / 2
24 / 2
12 / 2
6/2
3/2
1/2
= 49
= 24
= 12
= 6
= 3
= 1
= 0
remainder
remainder
remainder
remainder
remainder
remainder
remainder
0
1
0
0
0
1
1
– 1100010
CSC 370 (Blum)
33
Converting decimal to binary III
• 98.61
– Fractional part
•
•
•
•
•
•
0.61  2 = 1.22
0.22  2 = 0.44
0.44  2 = 0.88
0.88  2 = 1.76
0.76  2 = 1.52
0.52  2 = 1.04
– .100111
CSC 370 (Blum)
34
Another Example (Whole number part)
• 123.456
– Integer part
•
•
•
•
•
•
•
123 / 2 = 61 remainder 1
61 / 2 = 30 remainder 1
30 / 2 = 15 remainder 0
15 / 2 = 7 remainder 1
7 / 2 = 3 remainder 1
3 / 2 = 1 remainder 1
1 / 2 = 0 remainder 1
– 1111011
CSC 370 (Blum)
35
Checking: Go to
Programs/Accessories/Calculator
CSC 370 (Blum)
36
Put the calculator in Scientific view
CSC 370 (Blum)
37
Enter number while in decimal mode,
then put Calculator into binary mode
CSC 370 (Blum)
38
Another Example (fractional part)
• 123.456
– Fractional part
•
•
•
•
•
•
•
•
0.456  2 = 0.912
0.912  2 = 1.824
0.824  2 = 1.648
0.648  2 = 1.296
0.296  2 = 0.592
0.592  2 = 1.184
0.184  2 = 0.368
…
– .0111010…
CSC 370 (Blum)
39
Checking fractional part: Enter digits
found in binary mode
Note that the leading zero does not display.
CSC 370 (Blum)
40
Convert to decimal mode, then
CSC 370 (Blum)
41
Divide by 2 raised to the number of digits (in
this case 7, including leading zero)
1
2
3
4
CSC 370 (Blum)
42
In most cases it will not be exact
CSC 370 (Blum)
43
Other way around
• Multiply fraction by 2 raised to the desired
number of digits in the fractional part. For
example
– .456  27 = 58.368
• Throw away the fractional part and represent the
whole number
– 58 111010
• But note that we specified 7 digits and the result
above uses only 6. Therefore we need to put in
the leading 0
– 0111010
CSC 370 (Blum)
44
Fixed point
• If one has a set number of bits reserved for
representing the whole number part and
another set number of bits reserved for
representing the fractional part of a number,
then one is said to be using fixed point
representation.
– The point dividing whole number from fraction
has an unchanging (fixed) place in the number.
CSC 370 (Blum)
45
Limits of the fixed point approach
• Suppose you use 4 bits for the whole
number part and 4 bits for the fractional part
(ignoring sign for now).
• The largest number would be 1111.1111 =
15.9375
• The smallest, non-zero number would be
0000.0001 = .0625
CSC 370 (Blum)
46
Floating point representation
• Floating point representation allows one to
represent a wider range of numbers using
the same number of bits.
• It is like scientific notation.
CSC 370 (Blum)
47
Scientific notation
• Used to represent very large and very small
numbers.
– Ex. Avogadro’s number
•  6.0221367  1023 particles
•  602213670000000000000000
– Ex. Fundamental charge e
•  1.60217733  10-19 C
•  0.000000000000000000160217733 C
CSC 370 (Blum)
48
Scientific notation: all of these are the
same number
•
•
•
•
•
•
12345.6789
= 1234.56789  100
1234.56789  10 = 1234.56789  101
123.456789  100 =123.456789  102
12.3456789  103
1.23456789  104
Rule: Shift the point to the left and
increment the power of ten.
CSC 370 (Blum)
49
Small numbers
•
•
•
•
•
•
•
•
0.000001234
0.00001234  10-1
0.0001234  10-2
0.001234  10-3
0.01234  10-4
0.1234  10-5
1.234  10-6
Rule: shift point to the right and decrement the
power.
CSC 370 (Blum)
50
Floating Point Rules
• We’ll use a set of rules that are close but not quite
the same as the IEEE 754 standards for floating
point representation.
• Starting with the fixed point binary representation,
shift the point and increase the power (of 2 now
that we’re in binary).
• Shift so that the number has no whole number
part and also so that the first fractional bit (the
half’s place) has a 1.
CSC 370 (Blum)
51
Floats
• SHIFT expression so it is just under 1 and
keep track of the number of shifts
• 1100010.1001100110011001
• .11000101001100110011001  27
• Express the number of shifts in binary
• .11000101001100110011001  200000111
CSC 370 (Blum)
We’re not done yet so this
exponent will change.
52
Mantissa and Exponent and Sign
•
•
•
•
•
.11000101001100110011001  200000111
(Significand) Mantissa
.11000101001100110011001  200000111
Exponent
The number may be negative, so there a bit
(the sign bit) reserved to indicate whether
the number is positive or negative
CSC 370 (Blum)
53
Small numbers
• 0.000010101110
• 0.10101110  2-4
• The power (a.k.a. the exponent) could be negative
so we have to be able to deal with that.
• Floating point numbers use a procedure known as
biasing to handle the negative exponent problem.
CSC 370 (Blum)
54
Biasing
• Actually the exponent is not represented as shown
on the previously.
• There were 8 bits used to represent the exponent
on the previous slide, that means there are 256
numbers that could be represented.
• Since the exponent could be negative (to represent
numbers less than 1), we choose half of the range
to be positive and half to be negative , i.e. -128 to
127.
CSC 370 (Blum)
55
Biasing (Cont.)
• In biasing, one does not use 2’s
complement or a sign bit.
• Instead one adds a bias (equal to the
magnitude of the most negative number) to
the exponents and represents the result of
that addition.
CSC 370 (Blum)
56
Biasing (Cont.)
• With 8 bits, the bias is 128 (= 27 that is 2 raised to
the number of bits used for the exponent minus
one).
• In our previous example, we had to shift 7 times to
the left, corresponding to an exponent of +7.
• We add that shift to the bias 128+7=135.
• That is the number we put in the exponent portion:
135  10000111.
CSC 370 (Blum)
57
Big floats
• Assume we use 8 bits, 4 for the mantissa and 4 for
the exponent (neglecting sign). What is the largest
float?
• Mantissa: 1111 Exponent 1111
• 0.9375  27
• =120
• (Compare this to the largest fixed-point number
using the same amount of space 15.9375)
CSC 370 (Blum)
58
Small floats
• Assume we use 8 bits, 4 for the mantissa and 4 for
the exponent (neglecting sign). What is the
smallest float?
• Mantissa: 1000 Exponent 0000
• 0.5  2-8
• = 0.001953125
• (Compare this to the smallest fixed-point number
using the same amount of space .0625)
CSC 370 (Blum)
59
Adding Floats
• Consider adding the following numbers
expressed in scientific notation
3.456789  103
1.212121  10-2
• The first step is to re-express the number
with the smaller magnitude so that it has the
same exponent as the other number.
CSC 370 (Blum)
60
Adding Floats (Cont.)
•
•
•
•
•
•
•
1.212121  10-2
0.1212121  10-1
0.01212121  100
0.001212121  101
0.0001212121  102
0.00001212121  103
The number was shifted 5 times (3-(-2)).
CSC 370 (Blum)
61
Adding Floats (Cont.)
• When the exponents are equal the mantissas
can be added.
3.456789  103
0.00001212121  103
• =3.45680112121  103
CSC 370 (Blum)
62
Rounding
• In a computer there are a finite number of
bits used to represent a number.
• When the smaller floating-point number is
shifted to make the exponents equal, some
of the less significant bits are lost.
• This loss of information (precision) is
known as rounding.
CSC 370 (Blum)
63
One more fine point about
floating-point representation
• As discussed so far, the mantissa
(significand) always starts with a 1.
• When storage was expensive, designers
opted not to represent this bit, since it is
always 1.
• It had to be inserted for various operations
on the number (adding, multiplying, etc.),
but it did not have to be stored.
CSC 370 (Blum)
64
Still another fine point
• When we assume that the mantissa must
start with a 1, we lose 0.
• Zero is too important a number to lose, so
we interpret the mantissa of all zeros and
exponent of all zeros as zero
– Even though ordinarily we would assume the
mantissa started with a one that we didn’t store.
CSC 370 (Blum)
65
Yet another fine point
• In the IEEE 754 format for floats, you bias
by one less (127) and reserve the exponents
00000000 and 11111111 for special
purposes.
• One on these special purposes is “Not a
number” (NaN) which is the floating point
version of overflow.
CSC 370 (Blum)
66
An example
• Represent -9087.8735 as a float using 23
bits for the mantissa, 8 for the exponent and
one for the sign.
• Convert the whole number magnitude 9087
to binary: 10001101111111
• That uses up 14 of the 23 bits for the
mantissa, leaving 9 for the fractional part.
CSC 370 (Blum)
67
An example (Cont.)
• Multiply the fractional part by 29 and
convert whole number part of that to binary,
make sure in uses 9 bits (add leading 0’s if
it doesn’t).
• .8735  29 = 447.232
• 447  110111111
CSC 370 (Blum)
68
An example (Cont.)
•
•
•
•
•
10001101111111.110111111
.10001101111111110111111  214
Mantissa 10001101111111110111111
Exponent 14+128=142  10001110
Sign bit 1 (because number was negative)
CSC 370 (Blum)
69
Example 2
• 0.0076534
• No whole number part. Begin by using all
23 mantissa bits for the fractional part.
• 0.0076534  223 = 64201.3724672
• 64201  1111101011001001
• Only uses 16 places, means that so far
number starts with 7 zeros. But float
mantissas are supposed to start with 1.
CSC 370 (Blum)
70
Example 2 (Cont.)
•
•
•
•
•
0.0076534  230 = 8217775.6758016
821775  11111010110010010101111
Above is mantissa
Exponent 128 – 7 = 121  01111001
Sign bit 0 (positive number)
CSC 370 (Blum)
71
References
• Computer Architecture, Nicholas Carter
• Computer Systems” Organization and
Architecture, John Carpinelli
CSC 370 (Blum)
72