Transcript ppt

Computer Science 1000
Digital Information

What is a number?
An arithmetical value, expressed by a word,
symbol, or figure, representing a particular
quantity – Oxford English Dictionary
 in other words, a number has two
components:

quantity: the "amount"
 representation: how that amount is represented


Number – Example
consider the following quantity of people
 how can we represent this number in print?

7
 the word seven
 VII (Roman Numerals)

(tally marks)


Number
the point is, there is
more than one way to
represent the same
quantity
 the choice depends
largely on the
application


Decimal Number System
also referred to as base 10
 a widely used number system, and probably
the one you are used to
 each number is represented as a sequence
of digits: 0 1 2 3 4 5 6 7 8 9
 the quantity of people from the previous
slide is represented as: 7


Decimal Number System

why is decimal so widely used?
From: A Manual of Greek Mathematics
By Thomas Little Heath

Binary Number System
also referred to as base 2
 the system that computers use to store
numbers
 each number is represented as a sequence
of digits: 0 1
 the quantity of people from the previous
slide is represented as: 111


Binary Number System

why do computers use a binary number
system?

most electronic storage has two states: on/off




RAM: capacitor charged or not charged
HD: polarity of magnetic field
processor: open/closed switch
difficult to store information reliably in more than
two states

quantum computers are an exception

Binary Numbers
our upcoming discussion will be to
familiarize you with the binary number
system (plus a few others)
 for this discussion, we will assume that our
quantities are:

positive
 integral (no fractions)


we will relax these assumptions later on

Binary Number


any positive, integral quantity that can be
represented in decimal can also be represented in
binary
Dec
Bin
Dec
Bin
Dec
Bin
Dec
Bin
0
0
4
100
8
1000
12
1100
1
1
5
101
9
1001
13
1101
2
10
6
110
10
1010
14
1110
3
11
7
111
11
1011
15
1111
the rules for representation are very similar in both
systems

Decimal Numbers

what does base 10 really mean?
each digit in the number represents a quantity to
be multiplied by a power of 10
 these values are all summed together


for example, consider the number 1234
1234
= 1 x 1000
+ 2 x 100
+ 3 x 10
+4x1
= 1 x 103
+ 2 x 102
+ 3 x 101
+ 4 x 100

Leading Zeroes



suppose I wanted to write 1234 using 5 digits
what is the correct representation?
Answer: 01234




these are known as leading zeroes
they do not affect the quantity, as their power of 10 is
multiplied by zero
in decimal, leading zeroes are typically not reported
for binary applications like computing, leading zeroes are
often shown

Binary Numbers

the digits in base 2 represent a similar idea as in
decimal



each digit represents a value to be multiplied to a power
however, instead of multiplying to a power of 10, they are
multiplied to a power of 2
for example, consider the binary number 1101
1101
=1x
+1x
+0x
+1x
8
4
2
1
= 1 x 23
+ 1 x 22
+ 0 x 21
+ 1 x 20
In other words, the
number 1101 in
binary is the
number 13 in
decimal.

Binary Conversion to Decimal:

for each binary digit:

copy the digits vertically on its own line


multiply each digit by a power of two



I typically write the left-most digit on the top, and the
right-most digit on the bottom
bottom digit: 20 = 1
increase by one power for each vertical step
add all values together

Binary Conversion to Decimal:
example: convert 11001 to decimal
 Step 1: Write the values vertically

1
 1
 0
 0
 1


Binary Conversion to Decimal:
example: convert 11001 to decimal
 Step 2: Multiply each value by a power of 2

1 x 24 = 1 x 16 = 16
 1 x 23 = 1 x 8 = 8
 0 x 22 = 0 x 4 = 0
 0 x 21 = 0 x 2 = 0
 1 x 20 = 1 x 1 = 1


Binary Conversion to Decimal:
example: convert 11001 to decimal
 Step 3: Add numbers together

1 x 24 = 1 x 16 = 16
 1 x 23 = 1 x 8 = 8
 0 x 22 = 0 x 4 = 0
 0 x 21 = 0 x 2 = 0
 1 x 20 = 1 x 1 = 1
 Decimal:
25


Binary Conversion to Decimal:

Example 2: Recall that letters are
represented in the computer using numbers.
The ASCII value for 'K' is 1001011 in binary.
What is this number in decimal?

Binary Conversion to Decimal:
1 x 26 = 1 x 16 = 64
 0 x 25 = 0 x 16 = 0
 0 x 24 = 0 x 16 = 0
 1 x 23 = 1 x 8 = 8
 0 x 22 = 0 x 4 = 0
 1 x 21 = 1 x 2 = 2
 1 x 20 = 1 x 1 = 1
 Decimal:
75

http://jeroenstaneke.girlshopes.com/binarytoascii/

Converting Decimal to Binary
converting from decimal to binary is
straightforward
 converting to binary from decimal is a bit
more involved
 however, it is easily accomplished if you
follow the steps


Converting Decimal to Binary – Steps

To convert number X to binary

Repeat following steps until X = 0



if X is odd, then write a one
Write right-to-left
if X is even, then write a zero
divide X by 2, and ignore any remainder or fraction

Example: Convert the number 19 to binary

Repeat following steps until X = 0



X = 19 9



if X is odd, then write a one
if X is even, then write a zero
divide X by 2, and ignore any
remainder or fraction
since 19 is odd, we write a one
we then divide 19 by 2 to get 9.5
since we ignore the fraction, our new
number is 9
Result:
1
Remember: Write right-to-left

Example: Convert the number 19 to binary

Repeat following steps until X = 0



X = 19 9 4



if X is odd, then write a one
if X is even, then write a zero
divide X by 2, and ignore any
remainder or fraction
since 9 is odd, we write a one
we then divide 9 by 2 to get 4.5
since we ignore the fraction, our new
number is 4
Result:
11
Remember: Write right-to-left

Example: Convert the number 19 to binary

Repeat following steps until X = 0



X = 19 9 4 2



if X is odd, then write a one
if X is even, then write a zero
divide X by 2, and ignore any
remainder or fraction
since 4 is even, we write a zero
we then divide 4 by 2 to get 2
since there is no fraction, our new
number is 4
Result:
0 11
Remember: Write right-to-left

Example: Convert the number 19 to binary

Repeat following steps until X = 0



X = 19 9 4 2 1



if X is odd, then write a one
if X is even, then write a zero
divide X by 2, and ignore any
remainder or fraction
since 2 is even, we write a zero
we then divide 2 by 2 to get 1
since there is no fraction, our new
number is 1
Result:
0 0 11
Remember: Write right-to-left

Example: Convert the number 19 to binary

Repeat following steps until X = 0



X = 19 9 4 2 1 0



if X is odd, then write a one
if X is even, then write a zero
divide X by 2, and ignore any
remainder or fraction
since 1 is odd, we write a one
we then divide 1 by 2 to get 0.5
since we ignore the fraction, our new
number is 0
Result:
1 0 0 11
Remember: Write right-to-left

Example: Convert the number 19 to binary

Repeat following steps until X = 0



X = 19 9 4 2 1 0
Since X is now
zero, we are done.
Hence, 19 as a
binary number is
10011



if X is odd, then write a one
if X is even, then write a zero
divide X by 2, and ignore any
remainder or fraction
since 1 is odd, we write a one
we then divide 1 by 2 to get 0.5
since we ignore the fraction, our new
number is 0
Result:
1 0 0 11
Remember: Write right-to-left

Example: Convert the number 19 to binary

check your work: convert 10011 back to decimal






1 x 24 = 1 x 16 = 16
0 x 23 = 0 x 8 = 0
0 x 22 = 0 x 4 = 0
1 x 21 = 1 x 2 = 2
1 x 20 = 1 x 1 = 1
Decimal:
19
Result checks out.

Example 2: Convert the number 53 to binary
X = 53 26 13 6 3 1 0
Result:







1 x 25 = 1 x 32 = 32
1 x 24 = 1 x 16 = 16
0 x 23 = 0 x 8 = 0
1 x 22 = 0 x 4 = 4
0 x 21 = 1 x 2 = 0
1 x 20 = 1 x 1 = 1
Decimal:
53
110101
Result checks out.

Decimal to Binary – An Alternative Approach

the steps for converting from decimal to binary can
also be written as follows:

Repeat following steps until X = 0



the two approaches are equivalent, since:



divide X by 2
assign the remainder digit to result
if X is odd, then dividing by 2 produces a remainder of 1
if X is even, then dividing by 2 produces a remainder of 0
you are welcome to use either method in your lab

Other Bases



most people use base 10 encodings
computers use base 2 encodings
however, there are two other popular encodings,
particularly in computer science



octal – base 8
hexadecimal (hex) – base-16
we can extend our previous statement about binary
and decimal representations to:

any positive, integral quantity that can be represented in
decimal can also be represented in binary, octal, or hex

Octal Number System
also referred to as base 8
 octal numbers have special uses

older computers
 file permissions (shown later)

each number is represented as a sequence
of digits: 0 1 2 3 4 5 6 7
 the quantity of people, in octal: 7


Octal Numbers


the digits in base 8 represent powers of 8
for example, consider the octal number 3624
3624
= 3 x 512
+ 6 x 64
+2x 8
+4x 1
= 3 x 83
+ 6 x 82
+ 2 x 81
+ 4 x 80

Octal Conversion to Decimal:


example: convert 3624 to decimal
use our binary converter, but use powers of 8
3 x 83 = 3 x 512
 6 x 82 = 6 x 64
 2 x 81 = 2 x
8
 4 x 80 = 4 x
1
 Decimal:

= 1536
= 384
= 16
=
4
1940

Decimal Conversion to Octal




can modify our decimal to binary converter to get
octal
however, we typically are more interested in
converting octal numbers to binary
it turns out, it is really easy to convert octal
numbers to binary
if one then desires the decimal representation:
 convert the decimal to binary
 convert binary to octal

Octal to Binary
for starters, let's consider the single-digit
octal numbers, written in binary
 note that we will use leading zeroes, so that
they are all three binary digits long

Octal
Bin
Octal
Bin
0
000
4
100
1
001
5
101
2
010
6
110
3
011
7
111

Octal to Binary

Bin
Octal
Bin
0
000
4
100
1
001
5
101
2
010
6
110
3
011
7
111
the binary representation for the octal
number 467 is:


Octal
100110111
notice anything?
each group of three digits in the binary number
make up an octal digit
 i.e. 100110111 = 100 110 111 = 467


Converting Octal to Binary – Steps

To convert octal number X to binary

Repeat for each octal digit, left to right


write the three binary digits that correspond to the octal
digit
If desired, remove any leading zeroes from the
result

Octal
Bin
Octal
Bin
0
000
4
100
1
001
5
101
2
010
6
110
3
011
7
111
Converting Octal to Binary

example: convert octal 7234 to binary

Solution: 111010011100
111
010
011
100
7
2
3
4

Octal
Bin
Octal
Bin
0
000
4
100
1
001
5
101
2
010
6
110
3
011
7
111
Converting Octal to Binary

example: convert octal 1762 to binary

Solution: 001111110010
1111110010
(no leading zeroes)
001
111
110
010
1
7
6
2

Converting Octal to Binary – Steps

To convert binary number X to octal

For each group of three digits in X (right to left)


write the corresponding octal digit from our table (right to
left)
if the number of binary digits remaining is 1 or 2, then add
leading zeroes to make three digits

Octal
Bin
Octal
Bin
0
000
4
100
1
001
5
101
2
010
6
110
3
011
7
111
Converting Binary to Octal

example: convert binary 111010011100

Solution: 7234
7
2
3
4
111
010
011
100

Octal
Bin
Octal
Bin
0
000
4
100
1
001
5
101
2
010
6
110
3
011
7
111
Converting Binary to Octal

example: convert binary 1111110010

Solution: 1762
1
7
6
2
0011
111
110
010
add leading zeroes

Octal – Uses


one common place where octal numbers are used are for file
permissions in a Linux system
briefly stated, there are three types of file permissions




read: a user can read the contents of a file
write: a user can save contents to the file
execute: a user can execute (run) the file
there are three types of users:



the owner of the file
people in the owner's group
everyone else

Octal – Uses


permissions in files are either yes/no (binary)
hence, we can represent all possible permissions with 9
binary bits









first bit: does the owner of the file have read permission
second bit: does the owner of the file have write permission
third bit: does the owner of the file have execute permission
fourth bit: does the owner's group have read permission
fifth bit: does the owner's group have write permission
sixth bit does the owner's group have execute permission
seventh bit: does everyone have read permission
eighth bit: does everyone have write permission
ninth bit: does everyone have execute permission

Octal
Bin
Octal
Bin
0
000
4
100
1
001
5
101
2
010
6
110
3
011
7
111
Octal – Uses

we can represent these 9 bits using three octal
digits




first digit: user permissions
second digit: group permissions
third digit: everyone else's permissions
e.g. suppose that a file has permissions: 750




in binary: 111 101 000
file owner has all permissions
owner's group has read and execute permission
everyone else has no permission

Hex Number System
also referred to as base 16
 hex numbers have special uses

memory addresses
 colours


like our other systems (decimal, binary,
octal), represented as a sequence of digits
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ....
 what are the other digits?


Hex Number System

hex uses the letters A to F to represent its remaining 6 digits:









10 in decimal is A in hex
11 in decimal is B in hex
12 in decimal is C in hex
13 in decimal is D in hex
14 in decimal is E in hex
15 in decimal is F in hex
e.g. 4E7F represents a hexidecimal number
note that some people write hex in lower case (4e7f)
the quantity of people, in hex: 7

Hex Numbers


the digits in base 16 represent powers of 16
for example, consider the hex number 4E7F
4E7F
= 4 x 163
+ E x 162
+ 7 x 161
+ F x 160
= 4 x 4096
+ 14 x 256
+ 7 x 16
+ 15 x 1

Hex Conversion to Decimal:


example: convert 4E7F to decimal
use our binary converter, but use powers of 16
4 x 163 = 4 x 4096 = 16384
 E x 162 = 14 x 256 =
3584
 7 x 161 = 7 x
16 = 112
 F x 160 = 15 x
1 =
15
 Decimal:
20095


Decimal Conversion to Hex



can modify our decimal to hex converter to get octal
like octal numbers, we typically convert between
hex and binary
like octal, it is really easy to convert hex numbers to
binary

Hex to Binary
like octal, we can write all digits of hex using
a fixed sequence of 4 binary digits
 leading zeroes are used when necessary

Hex
Bin
Hex
Bin
Hex
Bin
Hex
Bin
0
0000
4
0100
8
1000
C
1100
1
0001
5
0101
9
1001
D
1101
2
0010
6
0110
A
1010
E
1110
3
0011
7
0111
B
1011
F
1111

Hex
Bin
Hex
Bin
Hex
Bin
Hex
Bin
0
0000
4
0100
8
1000
C
1100
1
0001
5
0101
9
1001
D
1101
2
0010
6
0110
A
1010
E
1110
3
0011
7
0111
B
1011
F
1111
Hex to Binary

the binary representation for the hex
number 8B7 is:


100010110111
similar to octal:
each group of four digits in the binary number
make up a hex digit
 i.e. 100010110111 = 1000 1011 0111 = 8B7


Converting Hex to Binary – Steps

To convert hex number X to binary

Repeat for each digit, left to right


write the four binary digits that correspond to the hex digit
If desired, remove any leading zeroes from the
result

Hex
Bin
Hex
Bin
Hex
Bin
Hex
Bin
0
0000
4
0100
8
1000
C
1100
1
0001
5
0101
9
1001
D
1101
2
0010
6
0110
A
1010
E
1110
3
0011
7
0111
B
1011
F
1111
Converting Hex to Binary

example: convert hex C234 to binary

Solution: 1100001000110100
1100 0010
C
2
0011 0100
3
4

Hex
Bin
Hex
Bin
Hex
Bin
Hex
Bin
0
0000
4
0100
8
1000
C
1100
1
0001
5
0101
9
1001
D
1101
2
0010
6
0110
A
1010
E
1110
3
0011
7
0111
B
1011
F
1111
Converting Hex to Binary

example: convert hex 3762 to binary

Solution: 0011011101100010
11011101100010
0011 0111
3
7
(no leading zeroes)
0110 0010
6
2

Converting Hex to Binary – Steps

To convert binary number X to hex

For each group of four digits in X (right to left)


write the corresponding hex digit from our table (right to
left)
if the number of binary digits remaining is 1, 2, or 3, then
add leading zeroes to make four digits

Hex
Bin
Hex
Bin
Hex
Bin
Hex
Bin
0
0000
4
0100
8
1000
C
1100
1
0001
5
0101
9
1001
D
1101
2
0010
6
0110
A
1010
E
1110
3
0011
7
0111
B
1011
F
1111
Converting Binary to Hex

example: convert binary 1100001000110100

Solution: C234
C
2
1100 0010
3
4
0011 0100

Hex
Bin
Hex
Bin
Hex
Bin
Hex
Bin
0
0000
4
0100
8
1000
C
1100
1
0001
5
0101
9
1001
D
1101
2
0010
6
0110
A
1010
E
1110
3
0011
7
0111
B
1011
F
1111
Converting Binary to Hex

example: convert binary 11011101100010

Solution: 3762
3
7
11 0111
0011
add leading zeroes
6
2
0110 0010

Hex – Uses



recall that each byte in memory has an address (like a
mailbox number)
these numbers are typically listed using hexidecimal
e.g. from a Microsoft tutorial on address space

Hex – Uses



another common use of hex numbers are to
represent colours
recall our discussion about colour models, in
particular, the RGB (Red-Green-Blue) model
a copy of the relevant slide from the Terminology III
slides has been included here, for convenience
From the
term3.ppt slides
(Week 2).

Colour Model


the colours defined by each series of bits depends on the
colour model
example: RGB (red-green-blue)



each colour is made up of a combination of red, green, and blue
the intensity of each channel determines the colour that we see
examples:






no red, no green, no blue = black
full red, no green, no blue = red
full red, full green, no blue = yellow
full red, no green, full blue = magenta
full red, full green, full blue = white
half red, no green, no blue = darker red

Colour Model

in a 24-bit scheme, the intensity of each colour is
governed by a value between 0 and 255

0 = no colour
255 = full colour
128 = half colour

examples:









red = 0, green = 0, blue = 0  black
red = 255, green = 0, blue = 0  red
red = 255, green = 255, blue = 0  yellow
red =255, green = 0, blue = 255  magenta
red = 255, green = 255, blue = 255  white
red = 128, green = 0, blue = 0  dark red
red = 255, green = 128, blue = 0  orange

Colour Model – why 0-255?
recall that each colour is represented using 24
bits
 each channel is given 8 bits
 as it turns out




the smallest 8-bit number: 00000000 = 0
the largest 8-bit number: 11111111 = 255
e.g. consider our example of orange:




red = 255, green = 128, blue = 0
converting to binary:
red = 11111111, green = 10000000, blue = 00000000
hence, orange in 24-bit binary = 111111111000000000000000

Colour Model



what is desired is to specify a colour using a single
value, rather than 3
specifying the binary is too long, and error prone
what about decimal?



the previous 24-bit binary number can be converted to
decimal:
111111111000000000000000 = 16744448
would you remember that this number means orange?

Hex to the Rescue


as we've shown, each digit in hexadecimal
represents four bits in binary
hence, we can represent our colours using 6 hex
digits




first two digits: red channel
next two digits: green channel
last two digits: blue channel
each channel is a hex number between 00 and FF

FF in hex = 255 in decimal

Hex
Bin
Hex
Bin
Hex
Bin
Hex
Bin
0
0000
4
0100
8
1000
C
1100
1
0001
5
0101
9
1001
D
1101
2
0010
6
0110
A
1010
E
1110
3
0011
7
0111
B
1011
F
1111
Hex Colours

represent our number for orange in
hexadecimal
binary: 111111111000000000000000
 with spaces: 1111 1111 1000 0000 0000 0000
 as hex: FF8000


where are hex colours used?
imaging applications
 webpages


From the colour selector in GIMP:
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>Nested Elements</title>
</head>
<body style="background-color: yellow">
<h1 style="background-color: orange"> Heading </h1>
<p>This is a paragraph. </p>
</body>
</html>
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>Nested Elements</title>
</head>
<body style="background-color: #FF0000">
<h1 style="background-color: #FF8000"> Heading </h1>
<p>This is a paragraph. </p>
</body>
</html>
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>Nested Elements</title>
</head>
<body style="background-color: #80FF00">
<h1 style="background-color: #880088"> Heading </h1>
<p>This is a paragraph. </p>
</body>
</html>

Base Notation



consider the number 101
this could be a hex number, decimal number, octal
number or binary number, each with different
values
to differentiate:



some people will write a subscript to indicate the base
e.g. 1012 indicates binary, while 10110 indicates decimal
in computer science:


octal numbers are often indicated by a leading 0
hex numbers are often indicated by a leading 0x

Number Sizes

consider a common personal calculator
non-scientific
 no exponents


what is the biggest number that we can
store?

Number Sizes

Answer: depends on the number of digits
1 digit: 9
 2 digits: 99
 3 digits: 999
 4 digits: 9999
 and so on


Number Sizes

we can generalize the previous by noticing the
following:






1 digit: 9 = 10-1 = 101-1
2 digits: 99 = 100-1 = 102-1
3 digits: 999 = 1000-1 = 103-1
4 digits: 9999 = 10000-1 = 104–1
...
in other words: given x digits, the largest number
that we can represent is 10x - 1

Number Sizes

given a calculator again, what's the smallest
number we can store?
same assumptions as before
 no negatives


Answer: 0
note: leading blanks are
the same as zeroes


Number Sizes

in summary, given x digits, we can represent any
number between 0 and 10x - 1


e.g. given 4 digits, we can represent any number between
0 and 9999
equivalently, the number of unique numbers
that we can represent using x digits is 10x

e.g. given two digits, we can represent 100
different numbers: 00, 01, 02, 03, ..., 97, 98, 99

Number Sizes

the same statements can be applied to
numbers in other bases
given x binary digits, we can represent any
number between 0 and 2x - 1
 equivalently, the number of unique numbers that
we can represent using x binary digits is 2x


Number Sizes – Example:

suppose I have exactly four binary digits

what is the largest number I can represent?


what is the smallest number I can represent?


24 - 1 = 15 (1111)
0 (0000)
how many different numbers can I store?

24 = 16
Dec
Bin
Dec
Bin
Dec
Bin
Dec
Bin
0
0000
4
0100
8
1000
12
1100
1
0001
5
0101
9
1001
13
1101
2
0010
6
0110
10
1010
14
1110
3
0011
7
0111
11
1011
15
1111

Number Sizes – Applications
consider our 24-bit colour model
 how many unique colours can we
represent?
 Answer:

the number of unique numbers that we can
represent using x binary digits is 2x
 hence, the number of unique colours = 224 =
16777216


Number Sizes – Applications




public-key cryptography uses secret keys to encrypt and
decrypt information as it passes between two parties
briefly stated, in order to read your incoming information, an
eavesdropper would have to obtain your key somehow
suppose your key was a 256-bit number (common)
how many possible keys are there?



the number of unique numbers that we can represent using x binary
digits is 2x
hence, the number of possible keys is: 2256
=115792089237316195423570985008687907853269984665640564039
457584007913129639936 ( roughly 1.15 x 1077)
for reference, one estimate on the number of atoms in the observable
universe = 4 x 1079