%% LyX 2.0.6 created this file. For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english]{article}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage{textcomp}
\usepackage{amsmath}
\usepackage{subscript}
\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\noun}[1]{\textsc{#1}}
%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\newenvironment{lyxcode}
{\par\begin{list}{}{
\setlength{\rightmargin}{\leftmargin}
\setlength{\listparindent}{0pt}% needed for AMS classes
\raggedright
\setlength{\itemsep}{0pt}
\setlength{\parsep}{0pt}
\normalfont\ttfamily}%
\item[]}
{\end{list}}
\makeatother
\usepackage{babel}
\begin{document}
\title{Learning the Binary System}
\author{\noun{Alex McAlpine}}
\date{Formated to \LaTeX{}: 11/25/2012}
\author{Original Document:}
\author{\noun{www.brainlubeonline.com/counting\_on\_binary/}}
\maketitle
\begin{abstract}
This is a document on the base-2 abstract numerical system, or Binary
system. This is a VERY easy concept to learn, it's amazing that the
binary system is not common knowledge! In fact it's easier than the
system you already know!
\pagebreak{}\end{abstract}
\begin{lyxcode}
\tableofcontents{}
\pagebreak{}
\end{lyxcode}
\section{What is it?}
We should begin by defining a \emph{numeral}. A \emph{numeral} is
a symbol that describes a number. Expressions such as: \emph{4}, \emph{IV},
\emph{78}, \emph{101} are all \emph{numerals} describing\emph{ }numbers.
A \emph{numeral} is not a number, it is an expression describing a
number. A number is a concept of quantity. One must know the difference
because the same number may be described by many different numerals.
An example would be 4 (in radix-10, or Base-10, the way we think),
IV(in Roman numerals), or (100, in Radix-2, or Base-2, otherwise known
as Binary). The fact is, for small numbers, it is actually easier
to think in base-2, or binary, than it is to think in base-10, or
decimal. Multiplication and division is way easier in binary than
the decimal way we were taught in school.
Thinking in different bases could be compared to a farmer looking
into egg cartons, counting by 12s; more on this later. What this means
is 3 dozen (base-12) is 3{*}12 = 36, in decimal (base 10, not base
12) that would be 3{*}10 + 6 = 36. Just keep reading, you'll get it,
really! Radix n is a numeration system with a base of n. Later we
will learn about octal numbers (a numeration system with a base of
8, or radix 8 where the \emph{n} in \emph{Radix n} is 8).
A clock uses a Radix 60, numeration system, at least the seconds and
minutes. These are just good examples to get you thinking about the
concept, and difference between \emph{numbers} and \emph{numerals}.
A quick example of a an octal number would be 26\textsubscript{8}
The eight in subscript tells us we are looking at a number described
in Radix-8 notation. We will get into octals later, you do not have
to understand this right now, this is just to introduce you to the
concept. This number represents 2{*}8+6 in base-10 or 22\textsubscript{10}.
This will make sense later.
When we write a number we assume it is in decimal format (radix-10),
unless the subscript tells us otherwise, or it is obviously implied.
This means 14\textsubscript{10} is unnecessary because we already
will assume that the text means 14 in decimal.
Base-2, or the binary system is the simplest system one can count
in because there are only two symbols to indicate a\emph{ number}
1 \& 0 that's it. The decimal system needs 10 different symbols to
describe the same numbers 0-9. and each place from the right to the
left is a multiple of 10.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
{\footnotesize{10 to the Power of: (10}}\emph{\footnotesize{\textsuperscript{\emph{n}}}}{\footnotesize{)}} & {\footnotesize{10\textsuperscript{\emph{6}}}} & {\footnotesize{10\textsuperscript{\emph{5}}}} & {\footnotesize{10\textsuperscript{\emph{4}}}} & {\footnotesize{10\textsuperscript{\emph{3}}}} & {\footnotesize{10\textsuperscript{\emph{2}}}} & {\footnotesize{10\textsuperscript{\emph{1}}}} & {\footnotesize{10\textsuperscript{\emph{0}}}}\tabularnewline
\hline
\hline
& {\footnotesize{1,000,000}} & {\footnotesize{100,000}} & {\footnotesize{10,000}} & {\footnotesize{1,000}} & {\footnotesize{100}} & {\footnotesize{10}} & {\footnotesize{1}}\tabularnewline
\hline
\end{tabular}
\par\end{center}
This means that the place from right to left, determines the power
of the numeral. The same is true for the binary system.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
2 to the Power of: (2\emph{\textsuperscript{n}}) & 2\emph{\textsuperscript{6}} & 2\emph{\textsuperscript{5}} & 2\emph{\textsuperscript{\emph{4}}} & 2\emph{\textsuperscript{\emph{3}}} & 2\emph{\textsuperscript{\emph{2}}} & 2\emph{\textsuperscript{\emph{1}}} & 2\emph{\textsuperscript{\emph{0}}}\tabularnewline
\hline
\hline
& 64 & 32 & 16 & 8 & 4 & 2 & 1\tabularnewline
\hline
\end{tabular}
\par\end{center}
That's all there is to it. Now let's try converting some numbers from
decimal to binary.
First lets try 48.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
Decimal: & 128 & 64 & 32 & 16 & 8 & 4 & 2 & 1\tabularnewline
\hline
\hline
Binary: & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0\tabularnewline
\hline
\end{tabular}
\par\end{center}
\begin{center}
32 + 16 = 48, this is 110000 in binary, read from right to left. This
is six characters long (the most significant bit is six from the right)
so this would be at it's smallest, a six \emph{bit} number. Usually,
computers reserve a set amount of memory for numbers in sectors with
an equal size, such as 8, 16, 32, or even 64 bits. So this number
in an 8-bit register would be 00110000 (in other words the extra zeros
to the left are put in as \emph{padding}, this will be important later
when we talk about bit shifting, but for now don't worry about it.)
\par\end{center}
Let's do another one, how about 19.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
Decimal: & 128 & 64 & 32 & 16 & 8 & 4 & 2 & 1\tabularnewline
\hline
\hline
Binary: & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1\tabularnewline
\hline
\end{tabular}
\par\end{center}
This gives us the 8-bit binary number 00010011. This is because the
largest power of 2 (16 in base-10) is the most significant bit, the
remainder is 3\textsubscript{10}, this means 2\textsuperscript{1}
will go into that once with a remainder of 1\textsubscript{10} which
is 2\textsuperscript{0}. (Remember from a few tables above that 2\textsuperscript{0}=
1\textsubscript{10}, 2\textsuperscript{1}= 2\textsubscript{10},
and 2\textsuperscript{2}= 4\textsubscript{10})
\section{Why use it? Why not?}
It is thought that we use the decimal system because we have 10 fingers,
but the truth is we could have just as easily used the binary system
naturally. The Mayans used a base-20 system, perhaps because they
used their toes also. The reason we want to be able to think in binary
is for programming and circuit design. The most basic TTL component
is the \emph{flip-flop} (a switch). It is High or Low, On of Off,
1 or 0. If we wanted a computer to think in base-10 we would need
9 different states not including a 0. With Radix-2 we only need 2
states, 1 or 0. This is the most efficient numeration system a digital
computer can work with at the lowest level. As a matter of fact this
will remain true for ALL computers until analog, or multi-state computers
are invented.
The question is; if it's so great, why don't we use it all the time?
Well it can get very tedious to write, for instance 36771 in decimal
notation only takes 5 characters to describe. In binary notation it
is: 1000000000000011, the same number takes 16 characters to describe,
over 3 times as many characters! The reason is simple, decimal notation
has 10 characters to choose from to describe a number 0-9, binary
only has 2 characters, 1 and 0. There are systems that can shorten
decimal numbers also, such as base-16, known as the hexadecimal system
that we will learn about later. The same number in hex is 8003, this
is because in hex notation there are 16 characters to choose from,
0-F! For instance 3A in hex is equal to 58 in decimal. This is because
A is in the 1's column (16\textsuperscript{0}), and 3 in the 16's
column (16\textsuperscript{1}) so (3{*}16+10 = 58, 10 = A in hex,
carry the 1 in decimal), more on that later.
To fully understand binary, we will need to study another type of
numeration system as well, this system is referred to as the octal
system. Yes you guessed it, the octal system is Radix-8, using the
characters 0 though 7. The reason we need to learn about counting
in base-8 will become clear later. Working in octal numbers is an
easy way to convert binary numerations to decimal notation, octal
numbers are sort of a mid point. Every three bits of a binary number
represent an octal digit. This makes it easy to look at a binary number
and see what it is as an octal. Again more on this later, the writing
here is just to tell you what is coming so you are not thrown into
the world of unknown numeral systems.
\section{Binary Numbers}
\subsection{Binary Conversion}
OK, so now we have a vague understanding of binary notation. The next
question is; do we have an understandable, programmable way of getting
binary numbers from decimal numbers? The answer is yes! Lets start
with 7\textsubscript{10}; all you have to do is keep dividing by
2 until there is no number left. I'll explain, the first divide by
2, is 3 in decimal. This gives us a remainder of 1\textsubscript{10};
there are only two numbers a remainder can be in binary or when dividing
by two, 1 or 0. This is a powerful piece of information because it
makes all your calculations much easier. When you divide to get binary,
you only record the remainders, and you only operate (divide) on the
result of your division. This will become clear in a moment, this
table will help you see how to convert 7 in decimal to 0111 in binary.
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
Divide: & 7/2 = 3 & 3/2 = 1 & 1/2 = 0\tabularnewline
\hline
\hline
Remainder: & = 1 & = 1 & = 1\tabularnewline
\hline
\end{tabular}
\par\end{center}
You than flip the result and that gives you 111, or 0111 with a zero
on the left to pad the number to 4 bits.
Now lets try converting 9\textsubscript{10} to binary.
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
Divide: & 9/2 = 4 & 4/2 = 2 & 2/2 = 1 & 1/2 = 0\tabularnewline
\hline
\hline
Remainder: & = 1 & = 0 & = 0 & = 1\tabularnewline
\hline
\end{tabular}
\par\end{center}
Notice that each time we divide (9/2 gives us 4, then we divide 4
by 2, that gives us 2, then 2/2 give us 1 and so forth) we only record
the remainders. Then, we flip the results, and there is our number
1001\textsubscript{2}. Up until now our numbers have been symmetrical
so the flip has not been apparent. Lets try one that is not symmetrical:
Let's try 23\textsubscript{10}.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
Divide: & 23/2 = 11 & 11/2 = 5 & 5/2 = 2 & 2/2 = 1 & 1/2 = 0\tabularnewline
\hline
\hline
Remainder: & = 1 & = 1 & = 1 & = 0 & = 1\tabularnewline
\hline
\end{tabular}
\par\end{center}
The answer is 10111\textsubscript{2}. Now it matters which way we
read the number, 11101 is a very different number than 10111. We always
start reading the binary number from the last operation we worked
on (bottom to top). That's it, that is the hardest part, it's all
down hill from here!
Converting binary numbers to decimal notation is as easy as adding.
The 8-bit number 00010011\textsubscript{2} for example.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
Decimal: & 128 & 64 & 32 & 16 & 8 & 4 & 2 & 1\tabularnewline
\hline
\hline
Binary Place: & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1\tabularnewline
\hline
\end{tabular}
\par\end{center}
Just add where you see a 1. (16 + 2 + 1 = 19)
Just to review, for any number denoted \emph{a}, where \emph{a }is
any non-zero number:
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\emph{\scriptsize{a\textsuperscript{\emph{0}}}} & \emph{\scriptsize{a\textsuperscript{\emph{1}}}} & \emph{\scriptsize{a\textsuperscript{\emph{2}}}} & \emph{\scriptsize{a\textsuperscript{\emph{3}}}} & \emph{\scriptsize{a\textsuperscript{\emph{4}}}} & \emph{\scriptsize{a\textsuperscript{\emph{n}}}}\tabularnewline
\hline
\hline
{\scriptsize{Always = 1}} & {\scriptsize{Always = }}\emph{\scriptsize{a (}}{\scriptsize{the value
of }}\emph{\scriptsize{a)}} & {\scriptsize{=}}\emph{\scriptsize{a{*}a}} & \emph{\scriptsize{=a{*}a{*}a}} & \emph{\scriptsize{=a{*}a{*}a{*}a}} & {\scriptsize{=}}\emph{\scriptsize{a{*}a...n}}{\scriptsize{ times}}\tabularnewline
\hline
\end{tabular}
\par\end{center}
\subsection{Addition}
To add two numbers in binary, you do it the same way as you do in
the decimal system, only it is much easier in binary. This is because
you are only adding, or carrying, a 1, and the result in each column
can only be a 1, or a 0. So here we go:
\begin{tabular}{cccc}
& & & \tabularnewline
& & 0 & \tabularnewline
& + & 0 & \tabularnewline
\hline
& & 0 & \tabularnewline
\end{tabular}
\rule[0.5ex]{1\columnwidth}{2pt}
\begin{tabular}{cccc}
& & & \tabularnewline
& & 1 & \tabularnewline
& + & 0 & \tabularnewline
\hline
& & 1 & \tabularnewline
\end{tabular}
\rule[0.5ex]{1\columnwidth}{2pt}
\begin{tabular}{cccc}
& & & \tabularnewline
& & 1 & \tabularnewline
& + & 1 & \tabularnewline
\hline
& 1 & 0 & \tabularnewline
\end{tabular}A '\emph{1}' is carried
\rule[0.5ex]{1\columnwidth}{2pt}
\begin{tabular}{cccc}
& & 1 & \tabularnewline
& & 1 & \tabularnewline
& + & 1 & \tabularnewline
\hline
& 1 & 1 & \tabularnewline
\end{tabular}A '\emph{1}' is carried and a '\emph{1}' remains
\rule[0.5ex]{1\columnwidth}{2pt}
\begin{tabular}{cccc}
& & 1 & \tabularnewline
& & 1 & \tabularnewline
& & 1 & \tabularnewline
& + & 1 & \tabularnewline
\hline
& 1 & 0 & \tabularnewline
+ & 1 & 0 & \tabularnewline
\hline
1 & 0 & 0 & \tabularnewline
\end{tabular}
\rule[0.5ex]{1\columnwidth}{2pt}
Above we just turn the 4 numbers into 2 (we add the top 1 + 1, then
the bottom 1 + 1) Then we simply add those two binary numbers together
as well.
\rule[0.5ex]{1\columnwidth}{2pt}
\begin{tabular}{ccccccccc}
& & & & & & & & \tabularnewline
& & 1 & 0 & 1 & 1 & 0 & 1 & 1\tabularnewline
& + & 0 & 1 & 1 & 1 & 0 & 1 & 0\tabularnewline
\hline
& 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1\tabularnewline
\end{tabular}In decimal this is: %
\begin{tabular}{cccc}
& & & \tabularnewline
& 9 & 1 & \tabularnewline
+ & 5 & 8 & \tabularnewline
\hline
1 & 4 & 9 & \tabularnewline
\end{tabular}
\rule[0.5ex]{1\columnwidth}{2pt}
The last one here, is not realistic because the two numbers to be
added were 7 bits long. Let's pad them (on the left of course so it
doesn't change their value to make them 8 bits long).
\rule[0.5ex]{1\columnwidth}{2pt}
\begin{tabular}{cccccccccc}
& & & & & & & & & \tabularnewline
& & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1\tabularnewline
& + & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0\tabularnewline
\hline
& & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1\tabularnewline
\end{tabular}In decimal this is: %
\begin{tabular}{cccc}
& & & \tabularnewline
& 9 & 1 & \tabularnewline
+ & 5 & 8 & \tabularnewline
\hline
1 & 4 & 9 & \tabularnewline
\end{tabular}
\rule[0.5ex]{1\columnwidth}{2pt}
All we did was add a zero to each number to bring it up to 8 bits
in length. If we were working on a system where the registers WERE
actually 7-bit, then we would have a problem because the result of
the addition is 8 bits in length and the last bit (to the left) would
be truncated (lost). The computer would see this if it had 7-bit registers:
\rule[0.5ex]{1\columnwidth}{2pt}
\begin{tabular}{cccccccccc}
& & & & & & & & & \tabularnewline
& & & 1 & 0 & 1 & 1 & 0 & 1 & 1\tabularnewline
& + & & 0 & 1 & 1 & 1 & 0 & 1 & 0\tabularnewline
\hline
& & & 0 & 0 & 1 & 0 & 1 & 0 & 1\tabularnewline
\end{tabular}
In decimal this is: %
\begin{tabular}{cccc}
& & & \tabularnewline
& 9 & 1 & \tabularnewline
+ & 5 & 8 & \tabularnewline
\hline
& 2 & 1 & \tabularnewline
\end{tabular}\textbf{!\textasciitilde{}\textasciitilde{} WRONG \textasciitilde{}\textasciitilde{}!}
\rule[0.5ex]{1\columnwidth}{2pt}
\subsection{Subtraction}
Subtraction in binary is the same as in decimal. You borrow just like
you would in the decimal system the only difference is that you are
just working with 1 and 0. Here we go:
\begin{tabular}{cccc}
& & & \tabularnewline
& & 0 & \tabularnewline
& - & 0 & \tabularnewline
\hline
& & 0 & \tabularnewline
\end{tabular} Binary %
\begin{tabular}{cccc}
& & & \tabularnewline
& & 0 & \tabularnewline
& - & 0 & \tabularnewline
\hline
& & 0 & \tabularnewline
\end{tabular}Decimal
\rule[0.5ex]{1\columnwidth}{2pt}
\begin{tabular}{cccc}
& & & \tabularnewline
& & 1 & \tabularnewline
& - & 0 & \tabularnewline
\hline
& & 1 & \tabularnewline
\end{tabular} Binary %
\begin{tabular}{cccc}
& & & \tabularnewline
& & 1 & \tabularnewline
& - & 0 & \tabularnewline
\hline
& & 1 & \tabularnewline
\end{tabular}Decimal
\rule[0.5ex]{1\columnwidth}{2pt}
\begin{tabular}{cccc}
& & & \tabularnewline
& & 1 & \tabularnewline
& - & 1 & \tabularnewline
\hline
& & 0 & \tabularnewline
\end{tabular} Binary %
\begin{tabular}{cccc}
& & & \tabularnewline
& & 1 & \tabularnewline
& - & 1 & \tabularnewline
\hline
& & 0 & \tabularnewline
\end{tabular}Decimal
\rule[0.5ex]{1\columnwidth}{2pt}
\begin{tabular}{ccccc}
& & & & \tabularnewline
& & 1 & 0 & \tabularnewline
& - & 0 & 1 & \tabularnewline
\hline
& & & 1 & \tabularnewline
\end{tabular} Binary %
\begin{tabular}{ccccc}
& & & & \tabularnewline
& & & 2 & \tabularnewline
& - & & 1 & \tabularnewline
\hline
& & & 1 & \tabularnewline
\end{tabular}Decimal
\rule[0.5ex]{1\columnwidth}{2pt}
You must remember, whenever you borrow, you are borrowing from two
times the amount (one column to the left). Go over the following carefully.
Here is an example of borrowing:
\begin{tabular}{ccccccc}
& & & & & & \tabularnewline
& & 1 & 0 & 1 & 1 & 0\tabularnewline
& - & 0 & 1 & 0 & 1 & 0\tabularnewline
\hline
& & 0 & 1 & 1 & 0 & 0\tabularnewline
\end{tabular} Binary %
\begin{tabular}{cccc}
& & & \tabularnewline
& 2 & 2 & \tabularnewline
- & 1 & 0 & \tabularnewline
\hline
& 1 & 2 & \tabularnewline
\end{tabular} Decimal
\rule[0.5ex]{1\columnwidth}{2pt}
\begin{tabular}{ccccccc}
& & & & & & \tabularnewline
& & & 1 & & & \tabularnewline
& & 1 & 1 & 1 & 1 & 0\tabularnewline
& - & 0 & 1 & 0 & 1 & 0\tabularnewline
\hline
& & 0 & 1 & 1 & 0 & 0\tabularnewline
\end{tabular} \textbf{Remember When Borrowing:} It is the same as putting two ones
over the borrowing column.
\rule[0.5ex]{1\columnwidth}{2pt}
\subsection{Multiplication}
Multiplication and division will never get easier than this, because
in binary you will never multiply (or divide) anything greater than
1! Multiplication is performed with the same method used in decimal
mathematics, from right to left, and shifting left with each new operation
multiplier.
\begin{tabular}{ccccccc}
& & & & 0 & 1 & 1\tabularnewline
& & & {*} & 1 & 1 & 0\tabularnewline
\cline{3-7}
& & & & 0 & 0 & 0\tabularnewline
& & & 0 & 1 & 1 & \tabularnewline
& & 0 & 1 & 1 & & \tabularnewline
\cline{3-7}
& & 1 & 0 & 0 & 1 & 0\tabularnewline
\end{tabular} Binary %
\begin{tabular}{cccc}
& & & 3\tabularnewline
& {*} & & 6\tabularnewline
\hline
& & 1 & 8\tabularnewline
\end{tabular} Decimal
\rule[0.5ex]{1\columnwidth}{2pt}
\begin{align*}
\begin{array}{cccc}
\\
\\
\\
\\
\\
\end{array}
\end{align*}
\begin{tabular}{ccccccccccccccccc}
& & & & & & & & & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0\tabularnewline
& & & & & & & {*} & & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1\tabularnewline
\cline{3-17}
& & & & & & & & & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0\tabularnewline
& & & & & & & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \tabularnewline
& & & & & & & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & & \tabularnewline
& & & & & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & & & \tabularnewline
& & & & & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & & & & \tabularnewline
& & & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & & & & & \tabularnewline
& & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & & & & & & \tabularnewline
& & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & & & & & & & \tabularnewline
\cline{3-17}
& & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0\tabularnewline
\end{tabular} Binary %
\begin{tabular}{ccccc}
& & 2 & 1 & 0\tabularnewline
& {*} & 1 & 4 & 9\tabularnewline
\hline
& 1 & 8 & 9 & 0\tabularnewline
& 8 & 4 & 0 & \tabularnewline
2 & 1 & 0 & & \tabularnewline
\hline
3 & 1 & 2 & 9 & 0\tabularnewline
\end{tabular} Decimal
\rule[0.5ex]{1\columnwidth}{2pt}
You should notice the pattern above. When multiplying by a 0, it is
zero across the board, when multiplying by 1, it is the same number
it always is (the top number). This is important when we get into
bitshifting. With a large enough register, we can just shift and add
to multiply. For instance if we count one set of zeros, then a 1's
row again we shift twice to the left then add, if we count two rows
of zeros then a 1's row again, we shift 3 times to the left than add.
You do not have to understand this right now. Really, if you understand
multiplication in binary, then this page has done it's job so far.
Hang with it!
\subsection{Division}
Division is just as simple in binary notation becuase when you divide,
your numbers may either go into the number, or not. In other words
if the divisor goes into the number you are dividing, it will only
go in once, or not at all. The only quotent you can have is either
a 1 or a 0.
1000\textsubscript{2} \textdiv{} 100\textsubscript{2} = 10\textsubscript{2}
\ensuremath{\equiv} 8\textsubscript{10} \textdiv{} 4\textsubscript{10}
= 2\textsubscript{10}
\rule[0.5ex]{1\columnwidth}{2pt}
\begin{tabular}{cccccccccc}
& & & & & & & & 1 & \tabularnewline
\cline{7-10}
& & 1 & 0 & 0 & / & 1 & 0 & 0 & 0\tabularnewline
& & & & & & 1 & 0 & 0 & \tabularnewline
\cline{7-10}
& & & & & & 0 & 0 & 0 & 0\tabularnewline
\end{tabular}
You just divide and subtract just like you would with the decimal
system. Here is a larger example:
\begin{tabular}{ccccccccccccc}
& & & & & & & & & & & & \tabularnewline
\cline{8-13}
& & 1 & 0 & 0 & 1 & / & 1 & 1 & 0 & 1 & 1 & 0\tabularnewline
& & & & & & & & & & & & \tabularnewline
\end{tabular}
\rule[0.5ex]{1\columnwidth}{2pt}
\begin{tabular}{ccccccccccccc}
& & & & & & & & & & 1 & & \tabularnewline
\cline{8-13}
& & 1 & 0 & 0 & 1 & / & 1 & 1 & 0 & 1 & 1 & 0\tabularnewline
& & & & & & & 1 & 0 & 0 & 1 & & \tabularnewline
\cline{8-13}
& & & & & & & 0 & 1 & 0 & 0 & 1 & 0\tabularnewline
& & & & & & & & & & & & \tabularnewline
\end{tabular}
\rule[0.5ex]{1\columnwidth}{2pt}
\begin{tabular}{ccccccccccccc}
& & & & & & & & & & 1 & 1 & \tabularnewline
\cline{8-13}
& & 1 & 0 & 0 & 1 & / & 1 & 1 & 0 & 1 & 1 & 0\tabularnewline
& & & & & & & 1 & 0 & 0 & 1 & & \tabularnewline
\cline{8-13}
& & & & & & & 0 & 1 & 0 & 0 & 1 & 0\tabularnewline
& & & & & & & & 1 & 0 & 0 & 1 & \tabularnewline
\cline{8-13}
& & & & & & & 0 & 0 & 0 & 0 & 0 & 0\tabularnewline
& & & & & & & & & & & & \tabularnewline
\end{tabular}
\rule[0.5ex]{1\columnwidth}{2pt}
\begin{tabular}{ccccccccccccc}
& & & & & & & & & & 1 & 1 & 0\tabularnewline
\cline{8-13}
& & 1 & 0 & 0 & 1 & / & 1 & 1 & 0 & 1 & 1 & 0\tabularnewline
& & & & & & & 1 & 0 & 0 & 1 & & \tabularnewline
\cline{8-13}
& & & & & & & 0 & 1 & 0 & 0 & 1 & 0\tabularnewline
& & & & & & & & 1 & 0 & 0 & 1 & \tabularnewline
\cline{8-13}
& & & & & & & 0 & 0 & 0 & 0 & 0 & 0\tabularnewline
& & & & & & & 0 & 0 & 0 & 0 & 0 & 0\tabularnewline
\cline{8-13}
& & & & & & & 0 & 0 & 0 & 0 & 0 & 0\tabularnewline
& & & & & & & & & & & & \tabularnewline
\end{tabular}
\rule[0.5ex]{1\columnwidth}{2pt}
\section{Bitwise Operations}
\subsection{1's Compliment}
TTL circuits generally deal with multiplication by adding the number
to be multiplied, to itself\emph{ n} number of times. In other words
4 {*} 9 is adds 4, 9 times. Division is the same way, the circuits
just use subtraction instead of addition as division is the inverse
of multiplication. Processors can be a little different but usually
the compiler will shield you from having to think about these things.
This brings us though, to subtraction. Computers do not really need
to subtract, only add by an operation called \emph{1's compliment}
to get a subtracted result. When performing subtraction, the number
you are subtracting numbers from is called the \emph{minuend}. The
amount you are subtracting is called the \emph{subtrahend}.
Now that we have a few of the terms out of the way let's start talking
about 1's compliment. 1's compliment is where you turn the 1's in
a binary number into 0's and the 0's into 1's, just write the exact
\emph{inverse} of whatever state that column in the number reads.
For example 10011010 is 01100101 in 1's complement. To subtract in
binary you simply invert the subtrahend and add to the minuend. To
better put it, you add the minuend to the 1's complement of the subtrahend.
If the sum of the addition adds a digit, we carry this (a 1\textsubscript{2})
to the right-side end. This is called \emph{end-around carry} here
are some examples:
Remember: When borrowing in n\textsubscript{2} (Binary), it is the
same as putting two ones over the borrowing column.
\begin{tabular}{ccccccc}
& & & & & & \tabularnewline
& & 1 & 0 & 1 & 1 & 0\tabularnewline
& - & 0 & 1 & 0 & 1 & 0\tabularnewline
\hline
& & & 1 & 1 & 0 & 1\tabularnewline
\end{tabular}\textbf{ }or %
\begin{tabular}{ccccccc}
& & & & & & \tabularnewline
& & 1 & 0 & 1 & 1 & 0\tabularnewline
& + & 1 & 0 & 1 & 0 & 1\tabularnewline
\hline
& End-around Carry 1: & 0 & 1 & 0 & 1 & 1\tabularnewline
& & & & & & 1\tabularnewline
\hline
& & & 1 & 1 & 0 & 0\tabularnewline
\end{tabular} Remember: add the \emph{end-around carry}.
\rule[0.5ex]{1\columnwidth}{2pt}
This works because by adding the inverse you are dealing with what's
left as a value from 0. If you think about it for a while it will
become clearer.
If there is not a 1\textsubscript{2} to carry, we have a negative
result. If you have a negative result, you will need to recomplement
the result (invert it). This is important because you will not get
the result you are looking for if you subtract in the standard fashion
and you get a negative number:
\begin{tabular}{ccccccc}
& & & & & & \tabularnewline
& & 1 & 0 & 1 & 1 & 1\tabularnewline
& - & 1 & 1 & 0 & 1 & 0\tabularnewline
\hline
& & - & 1 & 1 & 0 & 1\tabularnewline
\end{tabular}\textbf{WRONG!}
\rule[0.5ex]{1\columnwidth}{2pt}
\textbf{or}
\rule[0.5ex]{1\columnwidth}{2pt}
\begin{tabular}{ccccccc}
& & & & & & \tabularnewline
& & 1 & 0 & 1 & 1 & 1\tabularnewline
& + & 0 & 0 & 1 & 0 & 1\tabularnewline
\hline
& Invert: & 1 & 1 & 1 & 0 & 0\tabularnewline
\hline
& - & 0 & 0 & 0 & 1 & 1\tabularnewline
\end{tabular} \textbf{Correct!}
\rule[0.5ex]{1\columnwidth}{2pt}
This happens because the computer (or human) will effectively borrow
to infinity. If you want to get around this and still use the standard
human method of binary subtraction just make your subtrahend the smallest
number and know that that result is a negative.
With the micro-controllers available now, you will rarely need to
deal with TTL circuits and the compilers now are so advanced you really
will probably not need to deal with 1's complement. You will deal
with 2's complement however. 2's complement is insanely easy to explain.
The last bit is inverted for negative numbers. That's it, that is
all there is to it. This means an 8-bit register that would normally
go from 0\textsubscript{10} (00000000\textsubscript{2}) to 255\textsubscript{10}
(11111111\textsubscript{2}), would have 7 bits (one less) for a magnitude
and one bit reserved for a polarity. Using the 2's complement syntax
that register will now describe -127\textsubscript{10} (10000000\textsubscript{2})
to 127\textsubscript{10} including a 0\textsubscript{10}. The -0\textsubscript{10}
takes a little thinking about, you are not gaining any room, the 0
has the potential to be it's inverse just as the rest of the numbers
do. It will become clear with a little pondering.
\subsection{Big and Little Endians}
Endiannism there is an interesting etymology for this word that is
beyond the scope of this page. We will however discuss the terms meaning.
A packet is a block on information, they can vary in size, for our
purposes we will make our packet size 1 byte (8-bits). The Endianness
of a packet of information, a byte (anything 8-bits in length) for
example is the description of which way the data travels. For instance,
in these articles we have been reading binary numbers with the least
significant bit on the right. A computer may see things differently,
a computer may read information in a little-endian way or a big-endian
way. Here is a table to help us:
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
Endian & First Bit & Last Bit\tabularnewline
\hline
\hline
Little & Least Significant & Most Significant\tabularnewline
\hline
Big & Most Significant & Least Significant\tabularnewline
\hline
\end{tabular}
\par\end{center}
Early Motorola and IBM chips were big-endian and Intel chips were
little-endian. This means that the IBM chips interpreted the first
bit of an 8-bit variable as the 128 column. In reality there are many
different types of endians, for instance with large packets of packets.
Another example are systems that treat a 32-bit number as two 16-bit
numbers. This really needs to be dealt with on a project to project
basis. I mention it here only as a diagnostic step you may want to
take if you are having trouble.
\section{Bit Shifting}
Bitshifting is the practice of shifting all the columns of a binary
number to the left or the right. The left-shift operator in languages
with a C like syntax look like this <\textcompwordmark{}< . The left-shift
operator will shift the bits to the left in a variable \emph{n} times,
with a default shift of 1 place. This means 00001011 shifted to the
left once will now be 00010110. This effectively doubled the numbers
magnitude. What happens with a number like 1011 though? Shifted once
to the left, this number would end up 0110. This is because the left-shift
operator is not an end-around carry operator. The original number
is lost. When using the left-shift operator, you may shift 1, 2,...n
times to the left by the syntax \emph{N} <\textcompwordmark{}< \emph{timesToShift};
where N is the variable to be shifted and timesToShift is the, you
guessed it, the \# of times the variable is to be shifted.
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
\# To Shift: & Not Shifted & \emph{N}<\textcompwordmark{}<1 & \emph{N}<\textcompwordmark{}<2 & \emph{N}<\textcompwordmark{}<3\tabularnewline
\hline
\hline
Number & 10101100 & 01011000 & 10110000 & 01100000\tabularnewline
\hline
\end{tabular}
\par\end{center}
This brings us the the right-shift. >\textcompwordmark{}>\textcompwordmark{}>
The right-shift operator does the inverse of the left-shift. 101100
shifted once to the right would be 010011 all information shifted
off the right is lost. The right-shift operator divides the number,
if you right-shift once you have divided the number in half. If the
number was an odd number, you are truncating the modulus.
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
\# To Shift: & Not Shifted & \emph{N}>\textcompwordmark{}>\textcompwordmark{}>1 & \emph{N}>\textcompwordmark{}>\textcompwordmark{}>2 & \emph{N}>\textcompwordmark{}>\textcompwordmark{}>3\tabularnewline
\hline
\hline
Number & 10101100 & 01010110 & 00101011 & 00010101\tabularnewline
\hline
\end{tabular}
\par\end{center}
Ok, so what happens when we are using 2's compliment and trying to
bitshift in this manor? We get funny results! They've already thought
about this, the operator is the arithmatic-right-shift operator. >\textcompwordmark{}>
This operator is not an end-around carry operator, but it does pad
with the state of the most significant bit (the polarity bit). For
instance this number: 10001110 shifted right arithmetically 3 times
would be 11110001. There is not an arithmatic-left-shift operator
because it would not produce a number you could not derive from the
operators already given.
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
\# To Shift: & Not Shifted & \emph{N}>\textcompwordmark{}>\textcompwordmark{}>1 & \emph{N}>\textcompwordmark{}>\textcompwordmark{}>2 & \emph{N}>\textcompwordmark{}>\textcompwordmark{}>3\tabularnewline
\hline
\hline
Number & 10101100 & 11010110 & 11101011 & 111110101\tabularnewline
\hline
\end{tabular}
\par\end{center}
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
\# To Shift: & Not Shifted & \emph{N}>\textcompwordmark{}>\textcompwordmark{}>1 & \emph{N}>\textcompwordmark{}>\textcompwordmark{}>2 & \emph{N}>\textcompwordmark{}>\textcompwordmark{}>3\tabularnewline
\hline
\hline
Number & 00101100 & 00010110 & 00001011 & 00000101\tabularnewline
\hline
\end{tabular}
\par\end{center}
\section{Other Computer Numbering Systems}
\subsection{Octal System}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
Decimal Number & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\tabularnewline
\hline
\hline
Octal Number & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 10 & 11\tabularnewline
\hline
\end{tabular}
\par\end{center}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
Decimal Number & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20\tabularnewline
\hline
\hline
Octal Number & 12 & 13 & 14 & 15 & 16 & 17 & 20 & 21 & 22 & 23 & 24\tabularnewline
\hline
\end{tabular}
\par\end{center}
The octal system is radix-8 (\emph{N}\textsubscript{8}), this system
uses the numerals 0-7. This system is a great thing to know. When
you're using the octal system, you can at a glance, know what number
you are looking at in binary. Every three binary columns are an octal
number. Let's look at a table:
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
Binary Number & Decimal Equivalent & Octal Equivalent\tabularnewline
\hline
\hline
101101 & 32+8+4+1=45\textsubscript{10} & 55\textsubscript{8}=5{*}8+5=45\textsubscript{10}\tabularnewline
\hline
111100 & 32+16+8+4=60\textsubscript{10} & 74\textsubscript{8}=7{*}8\textsubscript{10}+4=45\textsubscript{10}\tabularnewline
\hline
\end{tabular}
\par\end{center}
Every three binary columns can go from 0 - 7 in magnitude. This means
you are either staring at a 1's column, a 2's column, or a 4's column.
Every set of three to the left over you go, you add a {*} 8. (C\textsuperscript{n}).
This table will show Octal numbers:
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
Binary Number & Octal Sets & Conversion Equivalent\tabularnewline
\hline
\hline
10110101 & 10 110 101 & 2{*}8\textsuperscript{2}\textsubscript{10}+6{*}8\textsuperscript{1}\textsubscript{10}+5{*}8\textsuperscript{0}\textsubscript{10}=181\textsubscript{10}\tabularnewline
\hline
\end{tabular}
\par\end{center}
\subsection{Hexadecimal System}
The Hexadecimal system, hex, is radix-16. Until now, we have dealt
with numeration systems with less characters than the decimal system.
We are now going to look at a system with 16 different glyphs with
magnatudes from 0 to 15. Instead of a subset showing the base, in
hex we simply add 0x as a prefix to show that we are working in hex:
\begin{center}
{\tiny{}}%
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
{\tiny{Decimal Number}} & {\tiny{0}} & {\tiny{1}} & {\tiny{2}} & {\tiny{3}} & {\tiny{4}} & {\tiny{5}} & {\tiny{6}} & {\tiny{7}} & {\tiny{8}} & {\tiny{9}} & {\tiny{10}} & {\tiny{11}}\tabularnewline
\hline
\hline
{\tiny{Hex Number}} & {\tiny{0x00}} & {\tiny{0x01}} & {\tiny{0x02}} & {\tiny{0x03}} & {\tiny{0x04}} & {\tiny{0x05}} & {\tiny{0x06}} & {\tiny{0x07}} & {\tiny{0x08}} & {\tiny{0x09}} & {\tiny{0x0A}} & {\tiny{0x0B}}\tabularnewline
\hline
\end{tabular}
\par\end{center}{\tiny \par}
\begin{center}
{\tiny{}}%
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
{\tiny{Decimal Number}} & {\tiny{12}} & {\tiny{13}} & {\tiny{14}} & {\tiny{15}} & {\tiny{16}} & {\tiny{17}} & {\tiny{18}} & {\tiny{19}} & {\tiny{20}} & {\tiny{21}} & {\tiny{22}} & {\tiny{23}}\tabularnewline
\hline
\hline
{\tiny{Hex Number}} & {\tiny{0x0C}} & {\tiny{0x0D}} & {\tiny{0x0E}} & {\tiny{0x0F}} & {\tiny{0x10}} & {\tiny{0x11}} & {\tiny{0x12}} & {\tiny{0x13}} & {\tiny{0x14}} & {\tiny{0x15}} & {\tiny{0x16}} & {\tiny{0x17}}\tabularnewline
\hline
\end{tabular}
\par\end{center}{\tiny \par}
\begin{center}
Here are some larger numbers:
\par\end{center}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
Decimal Number & 40 & 255 & 256 & 257 & 89372 & 1512394\tabularnewline
\hline
\hline
Hex Number & 0x28 & 0xFF & 0x100 & 0x1001 & 0x15D1C & 0x1713CA\tabularnewline
\hline
\end{tabular}
\par\end{center}
\end{document}