Transcript Binary Numbers - La Salle University

Binary Numbers
PHY 201 (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
PHY 201 (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
PHY 201 (Blum)
Binary
3
Range actually split in three
High
Forbidden
range
Low
PHY 201 (Blum)
4
It doesn’t matter ….



Some of the standard voltages coming
from a computer’s power are ideally
supposed to be 3.30 volts, 5.00 volts
and 12.00 volts
Typically they are 3.28 volts, 5.14 volts
or 12.22 volts or some such value
So what, who cares
PHY 201 (Blum)
5
How to represent big integers


Use positional weighting, same as with
decimal numbers
205 = 2102 + 0101 + 5100


Decimal – powers of ten
11001101 =
127 + 126 + 025 + 024
+ 123 + 122 + 021 + 120
= 128 + 64 + 8 + 4 + 1
= 205

Binary – powers of two
PHY 201 (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
PHY 201 (Blum)
1
7
Iterate

51/2 = 25, remainder 1
1

1
0
1
0
1
25/2 = 12, remainder 1
1

0
1
12/2 = 6, remainder 0
0
PHY 201 (Blum)
1
1
8
Iterate

6/2 = 3, remainder 0
0

1
1
0
1
0
1
0
1
3/2 = 1, remainder 1
1

0
0
0
1
1
1/2 = 0, remainder 1
1
PHY 201 (Blum)
1
0
0
1
1
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
PHY 201 (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.
PHY 201 (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
PHY 201 (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
+
PHY 201 (Blum)
1
3
3
7
9
5
4
13
Adding Binary Numbers
carries
1
+
PHY 201 (Blum)
1
1
1
0
1
0
0
1
1
1
0
1
0
0
0
1
1
1
0
0
1
0
1
0
14
Uh oh, overflow*

What if you use a byte (8 bits) to represent an
integer
1

*The
1
1
0
1
0
1
0
1
0
+
1
1
0
0
1
1
0
0
1
0
1
1
1
0
1
1
0
A byte may not be enough to represent the sum of
two such numbers.
End of the World as We Know It
PHY 201 (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.
PHY 201 (Blum)
16
Bigger Numbers


You can represent larger numbers 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)
PHY 201 (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
1
1
0
1
0
1
1
0
0
0
0
0
0
0
0
0
Ignoring overflow the two eight-bit numbers
above sum to zero
PHY 201 (Blum)
18
Two’s Complement
0

1
0
1
0
1
0
Step 1: exchange 1’s and 0’s
1

0
1
0
1
0
1
0
1
Step 2: add 1 (to the lowest bit only)
1
PHY 201 (Blum)
1
0
1
0
1
1
0
19
Sign bit




With the two’s complement approach, all
positive numbers start with a 0 in the
left-most, 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
PHY 201 (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.
PHY 201 (Blum)
21
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.
PHY 201 (Blum)
22
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.
PHY 201 (Blum)
23
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?
PHY 201 (Blum)
24
3-bit unsigned and signed
7
6
5
4
3
2
1
0
1
1
1
1
0
0
0
0
PHY 201 (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 an
odometer
reading
999999
and the car
travels one
more mile.
25
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
11.001001 =
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)
PHY 201 (Blum)
26
Places

11.001001
Two’s place
One’s place
Half’s place
Fourth’s place
Eighth’s place
Sixteenth’s place
PHY 201 (Blum)
27
Decimal to binary

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
PHY 201 (Blum)
28
Decimal to binary

98.61

Fractional part







0.61 
0.22 
0.44 
0.88 
0.76 
0.52 
2
2
2
2
2
2
=
=
=
=
=
=
1.22
0.44
0.88
1.76
1.52
1.04
.100111
PHY 201 (Blum)
29
Decimal to binary


Put together the integral and fractional
parts
98.61  1100010.100111
PHY 201 (Blum)
30
Another Example (Whole number part)

123.456

Integer part








123 / 2
61 / 2
30 / 2
15 / 2
7/2
3/2
1/2
= 61
= 30
= 15
= 7
= 3
= 1
= 0
remainder
remainder
remainder
remainder
remainder
remainder
remainder
1
1
0
1
1
1
1
1111011
PHY 201 (Blum)
31
Checking: Go to All
Programs/Accessories/Calculator
PHY 201 (Blum)
32
Put the calculator in Programmer
view
PHY 201 (Blum)
33
Enter number, put into binary mode
PHY 201 (Blum)
34
Another Example (fractional part)

123.456

Fractional part









0.456 
0.912 
0.824 
0.648 
0.296 
0.592 
0.184 
…
2
2
2
2
2
2
2
=
=
=
=
=
=
=
0.912
1.824
1.648
1.296
0.592
1.184
0.368
.0111010…
PHY 201 (Blum)
35
Checking fractional part: Enter digits
found in binary mode
Note that the leading zero does not display.
PHY 201 (Blum)
36
Convert to decimal mode, then
PHY 201 (Blum)
37
Edit/Copy result. Switch to
Scientific View. Edit/Paste
PHY 201 (Blum)
38
Divide by 2 raised to the number of digits
(in this case 7, including leading zero)
1
2
3
4
PHY 201 (Blum)
39
Finally hit the equal sign. In most
cases it will not be exact
PHY 201 (Blum)
40
Other way around



Multiply fraction by 2 raised to the desired number of
digits in the fractional part. For example
7 = 58.368
 .456  2
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. (Also the fraction is less than .5 so there’s
a zero in the ½’s place.)
 0111010
PHY 201 (Blum)
41
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
PHY 201 (Blum)
42
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.
PHY 201 (Blum)
43
Scientific notation

Used to represent very large and very
small numbers

Ex. Avogadro’s number



 6.0221367  1023 particles
 602213670000000000000000
Ex. Fundamental charge e


PHY 201 (Blum)
 1.60217733  10-19 C
 0.000000000000000000160217733 C
44
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.
PHY 201 (Blum)
45
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.
PHY 201 (Blum)
46
Floating Point Rules


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.
PHY 201 (Blum)
47
Floats


SHIFT expression so it is just under 1
and keep track of the number of shifts
1100010.1001100110011001
7 shifts



.11000101001100110011001  27
Express the number of shifts in binary
.11000101001100110011001  200000111
PHY 201 (Blum)
48
Mantissa and Exponent





.11000101001100110011001  200000111
Mantissa
.11000101001100110011001  200000111
Exponent
(Actually the representation of a float is
just a little more complicated, but we
will return to that another time.)
PHY 201 (Blum)
49
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
PHY 201 (Blum)
50
Decimal  Binary  Hex








0
1
2
3
4
5
6
7








PHY 201 (Blum)
0000
0001
0010
0011
0100
0101
0110
0111








0
1
2
3
4
5
6
7








8  1000  8
9  1001  9
10  1010  A
11  1011  B
12  1100  C
13  1101  D
14  1110  E
15  1111  F
51
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
PHY 201 (Blum)
C
9
52
Addresses


With user friendly computers, one rarely
encounters binary, but we sometimes see
hex, especially with addresses
To enable the computer to distinguish various
parts, each is assigned an address, a number





Distinguish among computers on a network
Distinguish keyboard and mouse
Distinguish among files
Distinguish among statements in a program
Distinguish among characters in a string
PHY 201 (Blum)
53
How many?




One bit can have two states and thus
distinguish between two things
Two bits can be in four states and …
Three bits can be in eight states, …
N bits can be in 2N states
0
0
0
1
0
0
0
0
0
0
1
1
1
0
1
1
1
1
0
1
1
1
0
1
PHY 201 (Blum)
54
IP(v4) Addresses



An IP(v4) address is used to identify a
network and a host on the Internet
It is 32 bits long
How many distinct IP addresses are
there?
PHY 201 (Blum)
55
Characters



We need to represent characters using
numbers
ASCII (American Standard Code for
Information Interchange) is a common way
A string of eight bits (a byte) is used to
correspond to a character


Thus 28=256 possible characters can be
represented
Actually ASCII only uses 7 bits, which is 128
characters; the other 128 characters are not
“standard”
PHY 201 (Blum)
56
Unicode


Unicode uses 16 bits, how many
characters can be represented?
Enough for English, Chinese, Arabic and
then some.
PHY 201 (Blum)
57
ASCII









0  00110000
1  00110001
…
A  01000001
B  01000010
…
a  01100001
b  01100010
…
PHY 201 (Blum)
(48)
(49)
(65)
(66)
(97)
(98)
58
Booleans



A Boolean variable is something that is
true or false
Booleans have two states and could be
represented by a single bit (1 for true
and 0 for false)
Booleans appearing in a program will
take up a whole word in memory
PHY 201 (Blum)
59
Boolean Operators



A.k.a. logical operators
Have Boolean input and Boolean output
Standard:






AND
OR
NOT
XOR (either or but not both)
NOR = NOT(OR)
NAND = NOT(AND)
PHY 201 (Blum)
60
Venn Diagrams

If inside circle A means A is true, and
similarly for circle B, then (A AND B) is
the intersection
A
PHY 201 (Blum)
B
61
Truth Tables

AND
INPUT
A
0
0
1
1
PHY 201 (Blum)
B
0
1
0
1
OUTPUT
A AND B
0
0
0
1
62
Truth Tables (Cont.)

OR
INPUT
A
0
0
1
1
PHY 201 (Blum)
B
0
1
0
1
OUTPUT
A OR B
0
1
1
1
63
Truth Tables (Cont.)

XOR (Excluded OR)
INPUT
A
0
0
1
1
PHY 201 (Blum)
B
0
1
0
1
OUTPUT
A XOR B
0
1
1
0
64
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
0+1=1
1+0=1
1+1=0
PHY 201 (Blum)
(with
(with
(with
(with
no carry)
no carry)
no carry)
a carry)
65
Addition Truth Table
INPUT
OUTPUT
Sum
Carry
A XOR B A AND B
A
B
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
PHY 201 (Blum)
66
All is NAND



Actually you can use one logic gate (the
NAND) and a few tricks (like De
Morgan’s theorem) to build all of the
“combinatorial” circuitry (the circuitry
that doesn’t involve memory)
NORs work too
But we tend to think in ANDs, ORs and
NOTs
PHY 201 (Blum)
67
Bit manipulation
You can use an AND to select out part
of a word (where s is a 1 or 0, etc)

s
t
u
v
w
x
y
z
0
0
0
0
0
0
0
AND
1
1
1
1
gives
s
PHY 201 (Blum)
t
u
v
0
68
IP Addresses Revisted




LaSalle’s IP address is what’s called a Class B
IP address
Of the 32 bits the first two bits are 10 (this
identifies us as Class B)
The remaining 14 bits of the first two bytes
identify us as LaSalle
The remaining 2 bytes are for our internals
use (to assign computers within LaSalle)
PHY 201 (Blum)
69
In or Out



To see if an address is local to LaSalle,
you would restrict your attention to the
first two bytes.
HOW?
AND it with FFFF0000
PHY 201 (Blum)
70
Subnets


A network (like LaSalle’s) can be
divided further into sub-networks
Then subnet masks are used to
determine whether or not another
computer is on the same subnet
PHY 201 (Blum)
71