Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Basic Concepts Behind the Binary System
To understand binary numbers, begin by recalling elementary school math
...
So the number "193" is 1-hundreds plus 9-tens plus 3-ones
...

As you know, the decimal system uses the digits 0-9 to represent numbers
...
g
...
For
example, putting ten in the 10^0 column is impossible, so we put a 1 in the 10^1
column, and a 0 in the 10^0 column, thus using two columns
...

The binary system works under the exact same principles as the decimal system, only
it operates in base 2 rather than base 10
...
Therefore, it would shift you one column to the left
...
The first column we fill is the right-most
column, which is 2^0, or 1
...

Examples: What would the binary number 1011 be in decimal notation?

Click here to see the answer
Try converting these numbers from binary to decimal:


10
111
10101
11110





Remember:
2^4| 2^3| 2^2| 2^1| 2^0
|
|
| 1 | 0
|
| 1 | 1 | 1
1 | 0 | 1 | 0 | 1
1 | 1 | 1 | 1 | 0

Click here to see the answer
Return to Table of Contents

Binary Addition
Consider the addition of decimal numbers:
23
+48
___

We begin by adding 3+8=11
...
Next, add {(2+4)
+1} (the one is from the carry)=7, which is put in the 10's column of the sum
...

Binary addition works on the same principle, but the numerals are different
...
In decimal form, 1+1=2
...
The
decimal number "2" is written in binary notation as "10" (1*2^1)+(0*2^0)
...
" In
our vertical notation,
1
+1
___
10

The process is the same for multiple-bit binary numbers:
1010
+1111
______








Step one:
Column 2^0: 0+1=1
...

Temporary Result: 1; Carry: 0
Step two:
Column 2^1: 1+1=10
...

Temporary Result: 01; Carry: 1
Step three:
Column 2^2: 1+0=1 Add 1 from carry: 1+1=10
...

Temporary Result: 001; Carry: 1
Step four:
Column 2^3: 1+1=10
...

Record the 11
...
To multiply by two, just add a 0 on
the end
...
For the sake of simplicity, throw away
the remainder
...
Begin by
thinking of a few examples
...
and that this is
equivalent to (1*2^1)+(1*2^0)
...
Almost as intuitive is the number 5: it is
obviously 4+1, which is the same as saying [(2*2) +1], or 2^2+1
...
Looking at this in columns,
2^2 | 2^1 | 2^0
1
0
1

or 101
...
Then we
just put this into columns
...
Let's
take a look at how it works
...
To convert the decimal number 75 to binary, we would find the largest
power of 2 less than 75, which is 64
...
The largest power of 2 in 11 is 8, or 2^3
...
Subtract 8 from 11 to get 3
...
We're left with 1, which goes in 2^0, and we
subtract one to get zero
...

Making this algorithm a bit more formal gives us:
1
...
Repeat until D=0
o a
...
Let this equal P
...
Put a 1 in binary column P
...
Subtract P from D
...
Put zeros in all columns which don't have ones
...
Particularly step 3, "filling in the zeros
...
Let D= the number we wish to convert from decimal to binary
2
...

3
...
Let's try the number D=55
...
We know that 2^4=16, 2^5=32, and 2^6=64
...

2^5<=55, so we put a 1 in the 2^5 column: 1-----
...
Subtracting 1 from P gives us 4
...

Next, subtract 16 from 23, to get 7
...

2^3>7, so we put a 0 in the 2^3 column: 110--Next, subtract 1 from P, which gives us 2
...
Subtract 1 from P to get 1
...
Subtract 1 from P to get 0
...
Subtract 1 from P to get -1
...


Another algorithm for converting decimal to binary
However, this is not the only approach possible
...

All binary numbers are in the form
a[n]*2^n + a[n-1]*2^(n-1)+
...
The
only way a number can be odd is if it has a 1 in the 2^0 column, because all powers of
two greater than 0 are even numbers (2, 4, 8, 16
...

Now we need to do the remaining digits
...
It is also easy to
see that multiplying and dividing by 2 shifts everything by one column: two in binary
is 10, or (1*2^1)
...

Similarly, multiplying by 2 shifts in the other direction: (1*2^1)*2=(1*2^2) or 10 in
binary
...
+ a[1]*2^1 + a[0]*2^0}/2

is equal to
a[n]*2^(n-1) + a[n-1]*2^(n-2) +
...
Take the number
163
...
We
also know that it equals 162+1
...

Two's column: Dividing 162 by 2 gives 81
...
Since we divided the number by two, we "took out" one power
of two
...
+ a[1]*2^0 has a
power of two removed
...
We learned earlier
that there is a 1 in the 2^0 column if the number is odd
...

Practically, we can simply keep a "running total", which now stands at 11 (a[1]=1 and
a[0]=1)
...


Four's column: Now we can subtract 1 from 81 to see what remainder we still must
place (80)
...
Therefore, there must be a 0 in the 4's column,
(because what we are actually placing is a 2^0 column, and the number is not odd)
...
This is even, so we put a 0 in
the 8's column
...

We can continue in this manner until there is no remainder to place
...

2
...

Repeat until D=0:
a) If D is odd, put "1" in the leftmost open column, and subtract 1 from

D
...

c) Divide D by 2
...
Let D=163
2
...

Subtract 1 from D to get 162
...

Temporary Result: 01
New D=81
D does not equal 0, so we repeat step 2
...


b) D is odd, put a
Subtract 1 from D to
c) Divide D=80 by
Temporary Result: 11
D does not equal 0, so

1 in the 2^1 column
...

2
...


2
...

c) Divide D by 2
...


b) D is even, put a 0 in the 2^3 column
...

Temporary Result: 0011
New D=10
2
...

c) Divide D by 2
...


a) D is odd, put a 1 in the 2^5 column
...

c) Divide D by 2
...


b) D is even, put a 0 in the 2^6 column
...

Temporary Result: 0100011
New D=1
2
...

Subtract 1 from D to get D=0
...

Temporary Result: 10100011

New D=0

D=0, so we are done, and the decimal number 163 is equivalent to the binary
number 10100011
...
10100011=(1*2^0)+(1*2^1)+(1*2^5)+(1*2^7)=1+2+32+128= 163
...
An 8-bit number is 8 digits long
...

Signed Magnitude:
The simplest way to indicate negation is signed magnitude
...

"0" indicates that the number is positive, "1" indicates negative
...
To indicate -12, we would
simply put a "1" rather than a "0" as the first bit: 10001100
...

However, negative numbers are represented differently
...
Thus, 12 would be 00001100,
and -12 would be 11110011
...
To compute the value of a negative number, flip the
bits and translate as before
...
Add 1 if the number is negative
...
To verify this, let's subtract
1 from 11110100, to get 11110011
...

In this notation, "m" indicates the total number of bits
...
To represent a number (positive or negative) in excess 2^7,
begin by taking the number in regular binary representation
...
For example, 7 would be 128 + 7=135, or 2^7+2^2+2^1+2^0, and, in
binary,10000111
...

Note:



Unless you know which representation has been used, you cannot figure out the
value of a number
...


To see the advantages and disadvantages of each method, let's try working with them
...
Then convert back to decimal numbers
...
Then convert back to decimal numbers

---