Transcript Binary Arithmetic

Binary Arithmetic
Math For Computers
Huh?
• Binary numbers are NUMBERS
• That means you can add, subtract, multiply, and
divide
• 2+2=4
• In Binary: 10 + 10 = 100
• So you COULD just convert all numbers to
decimal, do the math, and then convert the
answer back…
• But I don’t care about the math
• I want you to understand how a computer does it!
Addition
• Similar to addition of large decimal
numbers
• You need to “carry” when a number gets
carried bits
too large for a single digit
• In binary, that’s 1 + 1 = 10
11_
• (or 0, carry a 1)
11 0011
• If you have 1 + 1 + 1 = 11
+ 1011
• (or 1, carry a 1)
11 1110
Addition Practice
•
•
•
•
•
•
1110 + 1010
1001 + 111
1111 0000 + 1111
111 1000 + 1111
1000 1100 + 1100 0110
Take a few minutes to try them
•
(answers in the PowerPoint Notes)
Overflow
• 1111 1111 + 100 = 1 0000 0011
• The answer is more than 1 byte large
• A computer typically will make it
DROP THE EXTRA BIT ON THE LEFT
• The computer’s answer: 11 (binary)
or 3 (decimal)
• This is called an overflow error
• Sometimes overflow behavior is
undefined (unpredictable)
Why overflow happens
• A computer’s processor stores information
in something called a register.
• Registers have a limited space – they can
only store a certain number of bits.
• If a processor does a calculation and the
answer exceeds the capacity of the
register, then the extra bits are dropped
• Modern registers are usually 16 or 32 bits,
but for this class we’ll only use 8 bits.
Addition Practice Pt. 2
• Do the math, but give the answer an 8-bit
computer would give
• 1111 1111 + 1010
• 1010 1100 + 111 1111
• 1000 0000 + 1000 0000
• 1101 1010 + 1110 0110
•
(answers in the PowerPoint Notes)
Negative Numbers for Computers
• A computer needs a way to represent
negative numbers (there’s no “negative
sign” in the comp)
• One Idea:
• Use one of the bits to indicate the sign of
the number, instead of using it as a digit
Sign Bit (the bad way)
• So the 1st bit of a number indicates it’s
sign
• Examples:
• 00000010 is 2
• 10000010 is -2
Problem with sign bit system
• 2 zeros is a waste (10000000 and
00000000 are both zero)
• Computer processors can’t subtract
without special instructions
• We need a way to subtract by adding!
• Huh?
Twos Complement
• Consider this idea: a binary digit “place
value” could be negative!
negative
eights
fours
twos
ones
1
0
1
1
• So the above number is actually 3 (the
positive bits) minus 8 = -5
• 1000 in the above system actually
represents the decimal number -8
• The example above is 4 bits. Most problems
for this class will assume 8 bits.
Twos Complement cont.
• REALLY IMPORTANT: Notice that with
both negative number systems you
need to know the number of total
bits you are going to use!
• We’ll assume 8 bits for simplicity.
• What is the value of the “negative
place”?
• What is the new range of numbers?
(Hint: It’s not 0 – 255 anymore)
Calculating Twos Complement
• Example: -1 in (8-bit) twos complement
is
1111 1111
• Still confused?
• Remember, everything is the same
except for a negative place value!
-128
64
32
16
8
4
2
1
1
1
1
1
1
1
1
1
• -128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = -1
• Btw, a “normal” binary number (where
1111 1111 = 255) is called “unsigned”
Calculating Twos Complement
Pt. 2
• Shortcut: Convert the positive binary
number, switch all the bits (0s become
1s, 1s become 0s), then add 1
• It only doesn’t work for -128 (no
positive number)
• Try some!
Set 1
Set 2
• -127
• -5
• -23
• -117
• -8
• -52
• -100
• -12
Actually Subtracting, finally
• Once you’ve got Twos Complement figured
out, subtracting is IDENTICAL TO ADDING
(but now using our twos complement
numbers)
• Example: Decimal 100 - 20
• Binary: 0110 0100 - 0001 0100
• 2s complement of 20: 1110 1100
0110 0100
+1110 1100
1 0101 0000
• Overflow bit is dropped, as usual
• 0101 0000 is… 80
• So this 2s complement system USES overflow
Practice Excercises
• Do in Binary (know how to do decimal
conversions, 2s complement conversions,
and binary addition)
Set 1
Set 2
• 12 – 2
• 50 - 10
• 2 - 1
• 66 – 30
• 127 - 128
• 35 – 44
Just to be clear:
If you have a binary number
like 1101 0110
It could be 214, or -42
There’s no way to tell if it’s negative just
by looking at it!
• Assume it is positive, unless the problem
states otherwise.
•
•
•
•
Multiplication & Division
• We’ll just talk about multiplying and dividing by
the powers of 2
• This is called “shifting”
• Just like when you multiply or divide by 10, you
just shift the decimal point
• In binary, when you multiply or divide by 2, you
shift the “binary point”
• 4*2=8
• 100 * 10 = 1000
• 4/2=2
• 100 / 10 = 10
Shifting Details
•
•
•
•
•
•
•
•
•
Multiplying can also be called left-shifting
Dividing: right-shifting
Left-Shifting can give you the overflow error
1000 0000 * 10 = 1 0000 0000
For 2s complement negative numbers,
overflow will give really weird results
Again, the leftmost bit is dropped
Right-shift is DIFFERENT FOR TWOS
COMPLEMENT vs. unsigned binary numbers
Unsigned: shift in a 0 for the leftmost bit
2s comp: shift in a COPY of the leftmost bit
Shifting Diagram
Left-Shifting by 2 (multiply by 4)
Right-Shifting by 2 (divide by 4)
1111 1111
11 1111 1100
These two 1s are
dropped and
disappear due to
overflow
1111 1111
These 1s are
dropped!
Twos
Complement
1111 1111 11
Two copies of the 1
were shifted in on
the left. If the
leftmost bit was 0,
two 0s would have
been shifted in.
Unsigned
0011 1111 11
0s are always
shifted in for
unsigned numbers
More Shifting Examples
Unsigned numbers
1011 0111 * 10 = 0110 1110 (overflow)
1111 1111 * 100 = 1111 1100 (overflow)
0001 1111 * 1000 = 1111 1000
Twos Complement
1111 1111 * 10 = 1111 1110
1000 0001 * 10 = 0000 0010 (overflow!)
-127 * 2 = 2…?
1000 0000 / 1 0000 = 0000 1000
1001 1100 / 100 = 1110 0111
0011 0010 / 10 = 0001 1001
0001 0011 / 100 = 0000 0100 (?????)
Instead of 0s, 1s
19 / 4 = 4
were shifted in
So when you divide, you lose precision
on the left
(the computer will drop bits that go off
because that was
the right side – this means the answer
the leftmost bit
is always rounded down towards -∞)
of the original
byte
View this
slide in a
slide
show!
Fancy Shifting Animation:
Multiplication
Also called left-shifting
(look at the animation)
This red box
is a register
0110100
10
1
Lets
And
Now
So
put
thethe
the
some
bits
bits
processor
that
bits
shift
went
into
togets
the
outan
left
register
ofinstruction
the
by register
3(8
places
bits)
And the new empty spaces
are
filled
with
zeros
areto(because
dropped
multiply
8this
is the
number
3ofrd overflow
power
bycorrect
8 of 2)answer,
Notice
that webecause
won’t
get
the
because of overflow. If the original number
was smaller and had three zeros on the left,
then the overflow would have only dropped
zeros, and the answer would be accurate.
View this
slide in a
slide
show!
Negative Number
Multiplication Overflow
For Negative numbers, be aware that
overflow will yield some strange results
1 0 1 0 1 1 0 01
The
computer
erases
the bit
that we
overflowed
Let’s
Take
multiply
this 8-bit
by 2.
negative
This
means
binary
number:
left-shiftand
by 1.
puts 10101101
in a zero on
the(or
right,
like it’s
= -83
positive
173)supposed to.
But the new number is 01011010, which equals 90!
This happened because the lower limit of 8-bit
twos complement negative numbers is -128.
However, -83 * 2 would have gone below that.
View this
slide in a
slide
show!
Fancy Shifting Animation:
Division
Also called right-shifting
(look at the animation)
10 01 1 0 1 0 1 1
The computer
drops
the bits
that
wentsimilar
out of the
Dividing
by powers
2 is very
If the original
Let’s
trynumber
dividing
was
by negative
4.ofWhen
that
(-85),happens,
then the only
registerto
tomultiplying.
the right. If Here,
the original
number
was
have
ourthe
difference
the number
would be
inthat
the register
ones we
come
will
inshift
on
to the
left side
positiveoriginal
(171), then
the
computer
will
put
zeros
on
binary
number
in2the
register.
nd power
insteadright
of zeros.
by 2 places.
This time
(4 our
is the
answer
is -22.ofIt2)should
the left.(10101011
The final =answer
is:-85)
42. Notice that this
171
OR
be -21.75, but the computer rounded down again. Just
isn’t a totally accurate answer (it should be 42.75)
remember that when you round a negative number
Because the computer dropped some bits we lost
DOWN, it becomes more negative!
precision. Basically, the computer will always round
down.
Microsoft Calculator
It’s actually useful for this binary stuff
Use it to double-check and test yourself
Put it into Scientific mode (under view) and you’ll see
buttons for decimal, binary, hex, and octal
Calculator Cont.
• If you click on the decimal (Dec) button
and then enter a negative decimal
number, then click the Binary (Bin)
button, you’ll see that negative number
in Twos Complement form
• If you do any arithmetic in Binary, and
the Byte button is activated, you’ll see
the “computer’s answer” (overflow)
• You can then click over to Decimal to
see what that number would be
Shifting Excercises
• Convert to Binary, then give the computer’s
answers
• Use Calc for the initial conversions and answerchecking
• Btw, I use an asterisk (*) for multiplication
-50 * 2
12 * 4
78 * 4
-100 * 2
10 / 2
-120 / 8
12 / 8
-12 / 4
Restating the Obvious
• The MATH ISN’T IMPORTANT. I can get the
answers from a calculator.
• Understanding these processes gives you
an idea of how the computer works.
• If the only thing you understand is that
computers are actually pretty simple
machines that need lots of instructions to
work properly, then you’re doing pretty
good (ok, you won’t so well on the test if
you can’t do the calculations, but at least
you have the general idea)