Table of Contents

Binary is a number system which builds numbers from
elements called *bits*. Each bit can be
represented by any two mutually exclusive states. Generally,
when we write it down or code bits, we represent them with
`1`

and
`0`

. We also talk about them
being true and false, and the computer internally represents
bits with high and low voltages.

We build binary numbers the same way we build numbers in our traditional base 10 system. However, instead of a one's column, a 10's column, a 100's column (and so on) we have a one's column, a two's columns, a four's column, an eight's column, and so on, as illustrated below.

Table 2.1. Binary

2^{...} | 2^{6} | 2^{5} | 2^{4} | 2^{3} | 2^{2} | 2^{1} | 2^{0} |

... | 64 | 32 | 16 | 8 | 4 | 2 | 1 |

For example, to represent the number 203 in base 10, we
know we place a `3`

in the
`1's`

column, a
`0`

in the
`10's`

column and a
`2`

in the
`100's`

column. This is
expressed with exponents in the table below.

Table 2.2. 203 in base 10

10^{2} | 10^{1} | 10^{0} |

2 | 0 | 3 |

Or, in other words, 2 ×
10^{2} + 3 ×
10^{0} = 200 + 3 =
203. To represent the same thing in binary, we would have the
following table.

Table 2.3. 203 in base 2

2^{7} | 2^{6} | 2^{5} | 2^{4} | 2^{3} | 2^{2} | 2^{1} | 2^{0} |

1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |

That equates to 2^{7} +
2^{6} +
2^{3}+2^{1}
+ 2^{0} = 128 + 64
+ 8 + 2 + 1 = 203.

The easiest way to convert between bases is to use a computer, after all, that's what they're good at! However, it is often useful to know how to do conversions by hand.

The easiest method to convert between bases is
*repeated division*. To convert,
repeatedly divide the quotient by the base, until the
quotient is zero, making note of the remainders at each
step. Then, write the remainders in reverse, starting at
the bottom and appending to the right each time. An example
should illustrate; since we are converting to binary we use
a base of 2.

Table 2.4. Convert 203 to binary

Quotient | Remainder | ||
---|---|---|---|

203_{10} ÷ 2 = | 101 | 1 | |

101_{10} ÷ 2 = | 50 | 1 | ↑ |

50_{10} ÷ 2 = | 25 | 0 | ↑ |

25_{10} ÷ 2 = | 12 | 1 | ↑ |

12_{10} ÷ 2 = | 6 | 0 | ↑ |

6_{10} ÷ 2 = | 3 | 0 | ↑ |

3_{10} ÷ 2 = | 1 | 1 | ↑ |

1_{10} ÷ 2 = | 0 | 1 | ↑ |

Reading from the bottom and appending to the right
each time gives `11001011`

,
which we saw from the previous example was 203.

To represent all the letters of the alphabet we would need at least enough different combinations to represent all the lower case letters, the upper case letters, numbers and punctuation, plus a few extras. Adding this up means we need probably around 80 different combinations.

If we have two bits, we can represent four possible
unique combinations (```
00 01 10
11
```

). If we have three bits, we can represent
8 different combinations. As we saw above, with
`n`

bits we can represent
`2`

unique combinations.^{n}

8 bits gives us
`2`

unique representations, more than enough
for our alphabet combinations. We call a group of 8 bits a
^{8} =
256*byte*. Guess how bit a C
`char`

variable is? One
byte.

Given that a byte can represent any of the values 0
through 256, anyone could arbitrarily make up a mapping
between characters and numbers. For example, a video card
manufacturer could decide that the value 10 represents
`A`

, so when value 10 is sent
to the video card it displays a capital 'A' on the
screen.

To avoid this happening, the *American
Standard Code for Information Interchange* or
ASCII was invented. This is a *7-bit*
code, meaning there are 2^{7} or
128 available codes.

The range of codes is divided up into two major parts;
the non-printable and the printable. Printable characters
are things like characters (upper and lower case), numbers
and punctuation. Non-printable codes are for control, and
do things like make a carriage-return, ring the terminal
bell or the special `NULL`

code which represents nothing at all.

127 unique characters is sufficient for American English, but becomes very restrictive when one wants to represent characters common in other languages, especially Asian languages which can have many thousands of unique characters.

To alleviate this, modern systems are moving away from
ASCII to *Unicode*, which can use up to 4
bytes to represent a character, giving
*much* more room!

ASCII, being only a 7-bit code, leaves one bit of the
byte spare. This can be used to implement
*parity* which is a simple form of error
checking. Consider a computer using punch-cards for input,
where a hole represents 1 and no hole represents 0. Any
inadvertent covering of a hole will cause an incorrect value
to be read, causing undefined behaviour.

Parity allows a simple check of the bits of a byte to
ensure they were read correctly. We can implement either
*odd* or *even* parity
by using the extra bit as a *parity
bit*.

In odd parity, if the number of 1's in the 7 bits of information is odd, the parity bit is set, otherwise it is not set. Even parity is the opposite; if the number of 1's is even the parity bit is set to 1.

In this way, the flipping of one bit will case a parity error, which can be detected.

XXX more about error correcting

Numbers do not fit into bytes; hopefully your bank
balance in dollars will need more range than can fit into
one byte! Most modern architectures are *32
bit* computers. This means they work with 4 bytes
at a time when processing and reading or writing to memory.
We refer to 4 bytes as a *word*; this is
analogous to language where letters (bits) make up words in a
sentence, except in computing every word has the same size!
The size of a C `it`

variable is 32 bits. Newer architectures are 64 bits, which
doubles the size the processor works with (8 bytes).

Computers deal with a lot of bytes; that's what makes them so powerful!

We need a way to talk about large numbers of bytes,
and a natural way is to use the "International System of
Units" (SI) prefixes as used in most other scientific areas.
So for example, kilo refers to
10^{3} or 1000 units, as in a
kilogram has 1000 grams.

1000 is a nice round number in base 10, but in binary
it is `1111101000`

which is
not a particularly "round" number. However, 1024 (or
2^{10}) is
(`10000000000`

), and happens
to be quite close to the base ten meaning of kilo (1000 as
opposed to 1024).

Hence 1024 bytes became known as a
*kilobyte*. The first mass market
computer was the Commodore 64, so named because it had 64
kilobytes of storage.

Today, kilobytes of memory would be small for a wrist
watch, let alone a personal computer. The next SI unit is
"mega" for
`10`

.
As it happens,
^{6}`2`

is again close to the SI base 10 definition; 1048576 as
opposed to 1000000.^{20}

The units keep increasing by powers of 10; each time it diverges further from the base SI meaning.

Table 2.5. Bytes

2^{10} | Kilobyte |

2^{20} | Megabyte |

2^{30} | Gigabyte |

2^{40} | Terrabyte |

2^{50} | Petabyte |

2^{60} | Exabyte |

Therefore a 32 bit computer can address up to four
gigabytes of memory; the extra two bits can represent four
groups of `2`

. A 64 bit computer can address up
to 8 exabytes; you might be interested in working out just
how big a number this is! To get a feel for how bit that
number is, calculate how long it would take to count to
^{30}
bytes.`2`

if you incremented once per second.^{64}

Apart from the confusion related to the overloading of
SI units between binary and base 10, capacities will often
be quoted in terms of *bits* rather than
bytes.

Generally this happens when talking about networking or storage devices; you may have noticed that your ADSL connection is described as something like 1500 kilobits/second. The calculation is simple; multiply by 1000 (for the kilo), divide by 8 to get bytes and then 1024 to get kilobytes (so 1500 kilobits/s=183 kilobytes per second).

The SI standardisation body has recognised these dual
uses, and has specified unique prefixes for binary usage.
Under the standard 1024 bytes is a
`kibibyte`

, short for
*kilo binary* byte (shortened to KiB).
The other prefixes have a similar prefix (Mebibyte, for
example). Tradition largely prevents use of these terms,
but you may seem them in some literature.

George Boole was a mathematician who discovered a whole
area of mathematics called *Boolean
Algebra*. Whilst he made his discoveries in the mid
1800's, his mathematics are the fundamentals of all computer
science. Boolean algebra is a wide ranging topic, we present
here only the bare minimum to get you started.

Boolean operations simply take a particular input and
produce a particular output following a rule. For example,
the simplest boolean operation,
`not`

simply inverts the value
of the input operand. Other operands usually take two inputs,
and produce a single output.

The fundamental Boolean operations used in computer
science are easy to remember and listed below. We represent
them below with *truth tables*; they simply
show all possible inputs and outputs. The term
*true* simply reflects
`1`

in binary.

Usually represented by
`!`

,
`not`

simply inverts the
value, so `0`

becomes
`1`

and
`1`

becomes
`0`

Table 2.6. Truth table for *not*

Input | Output |
---|---|

`1` | `0` |

`0` | `1` |

To remember how the and operation
works think of it as "if one input *and*
the other are true, result is true

Table 2.7. Truth table for *and*

Input 1 | Input 2 | Output |
---|---|---|

`0` | `0` | `0` |

`1` | `0` | `0` |

`0` | `1` | `0` |

`1` | `1` | `1` |

To remember how the
`or`

operation works think of
it as "if one input *or* the other input
is true, the result is true

Table 2.8. Truth table for *or*

Input 1 | Input 2 | Output |
---|---|---|

`0` | `0` | `0` |

`1` | `0` | `1` |

`0` | `1` | `1` |

`1` | `1` | `1` |

Exclusive or, written as
`xor`

is a special case of
`or`

where the output is true
if one, and *only* one, of the inputs is
true. This operation can surprisingly do many interesting
tricks, but you will not see a lot of it in the
kernel.

Table 2.9. Truth table for *xor*

Input 1 | Input 2 | Output |
---|---|---|

`0` | `0` | `0` |

`1` | `0` | `1` |

`0` | `1` | `1` |

`1` | `1` | `0` |

Believe it or not, essentially everything your computer does comes back to the above operations. For example, the half adder is a type of circuit made up from boolean operations that can add bits together (it is called a half adder because it does not handle carry bits). Put more half adders together, and you will start to build something that can add together long binary numbers. Add some external memory, and you have a computer.

Electronically, the boolean operations are implemented
in *gates* made by
*transistors*. This is why you might have
heard about transistor counts and things like Moores Law. The
more transistors, the more gates, the more things you can add
together. To create the modern computer, there are an awful
lot of gates, and an awful lot of transistors. Some of the
latest Itanium processors have around 460 million
transistors.

In C we have a direct interface to all of the above operations. The following table describes the operators

Table 2.10. Boolean operations in C

Operation | Usage in C |
---|---|

`not` | `!` |

`and` | `&` |

`or` | `|` |

`xor` | `^` |

We use these operations on variables to modify the bits within the variable. Before we see examples of this, first we must divert to describe hexadecimal notation.

Hexadecimal refers to a base 16 number system. We use this in computer science for only one reason, it makes it easy for humans to think about binary numbers. Computers only ever deal in binary and hexadecimal is simply a shortcut for us humans trying to work with the computer.

So why base 16? Well, the most natural choice is base 10, since we are used to thinking in base 10 from our every day number system. But base 10 does not work well with binary -- to represent 10 different elements in binary, we need four bits. Four bits, however, gives us sixteen possible combinations. So we can either take the very tricky road of trying to convert between base 10 and binary, or take the easy road and make up a base 16 number system -- hexadecimal!

Hexadecimal uses the standard base 10 numerals, but adds
`A B C D E F`

which refer to
`10 11 12 13 14 15`

(n.b. we
start from zero).

Traditionally, any time you see a number prefixed by
`0x`

this will denote a
hexadecimal number.

As mentioned, to represent 16 different patterns in binary, we would need exactly four bits. Therefore, each hexadecimal numeral represents exactly four bits. You should consider it an exercise to learn the following table off by heart.

Table 2.11. Hexadecimal, Binary and Decimal

Hexadecimal | Binary | Decimal |
---|---|---|

`0` | `0000` | `0` |

`1` | `0001` | `1` |

`2` | `0010` | `2` |

`3` | `0011` | `3` |

`4` | `0100` | `4` |

`5` | `0101` | `5` |

`6` | `0110` | `6` |

`7` | `0111` | `7` |

`8` | `1000` | `8` |

`9` | `1001` | `9` |

`A` | `1010` | `10` |

`B` | `1011` | `11` |

`C` | `1100` | `12` |

`D` | `1101` | `13` |

`E` | `1110` | `14` |

`F` | `1111` | `15` |

Of course there is no reason not to continue the pattern
(say, assign G to the value 16), but 16 values is an excellent
trade off between the vagaries of human memory and the number of
bits used by a computer (occasionally you will also see base 8
used, for example for file permissions under UNIX). We simply
represent larger numbers of bits with more numerals. For
example, a sixteen bit variable can be represented by 0xAB12,
and to find it in binary simply take each individual numeral,
convert it as per the table and join them all together (so
`0xAB12`

ends up as the 16-bit
binary number
`1010101100010010`

). We can use
the reverse to convert from binary back to hexadecimal.

We can also use the same repeated division scheme to change the base of a number. For example, to find 203 in hexadecimal

Table 2.12. Convert 203 to hexadecimal

Quotient | Remainder | ||
---|---|---|---|

203_{10} ÷ 16 = | 12 | 11 (0xB) | |

12_{10} ÷ 16 = | 0 | 12 (0xC) | ↑ |

Hence 203 in hexadecimal is
`0xCB`

.

Whilst binary is the underlying language of every computer, it is entirely practical to program a computer in high level languages without knowing the first thing about it. However, for the low level code we are interested in a few fundamental binary principles are used repeatedly.

In low level code, it is often important to keep your structures and variables as space efficient as possible. In some cases, this can involve effectively packing two (generally related) variables into one.

Remember each bit represents two states, so if we know a
variable only has, say, 16 possible states it can be
represented by 4 bits (i.e. 2^{4}=16
unique values). But the smallest type we can declare in C is
8 bits (a `char`

), so we can
either waste four bits, or find some way to use those left
over bits.

We can easily do this by the process of
*masking*. Remembering the rules of the
logical operations, it should become clear how the values are
extracted.

The process is illustrated in the figure below. We are
interested in the lower four bits, so set our mask to have
these bits set to `1`

. Since
the `logical and`

operation
will only set the bit if *both* bits are
`1`

, those bits of the mask set
to `0`

effectively hide the bits
we are not interested in.

Figure 2.1. Masking

To get the top (blue) four bits, we would invert the
mask. You will note this gives a result of
`0x90`

when really we want a
value of `0x09`

. To get the
bits into the right position we use the ```
right
shift
```

operation.

*Setting* the bits requires the
`logical or`

operation.
However, rather than using
`1`

's as the mask, we use
`0`

's. You should draw a
diagram similar to the above figure and work through setting
bits with the ```
logical
or
```

operation.

Often a program will have a large number of variables
that only exist as *flags* to some
condition. For example, a state machine is an algorithm that
transitions through a number of different states but may only
be in one at a time. Say it has 8 different states; we could
easily declare 8 different variables, one for each state. But
in many cases it is better to declare *one 8 bit
variable* and assign each bit to
*flag* flag a particular state.

Flags are a special case of masking, but each bit
represents a particular boolean state (on or off). An
*n* bit variable can hold
*n* different flags. See the code example
below for a typical example of using flags -- you will see
variations on this basic code very often.

Example 2.1. Using flags

1 #include <stdio.h> // define all 8 possible flags for an 8 bit variable 5 // name hex binary #define FLAG1 0x01 // 00000001 #define FLAG2 0x02 // 00000010 #define FLAG3 0x04 // 00000100 #define FLAG4 0x08 // 00001000 10 // ... and so on #define FLAG8 0x80 // 10000000 int main(int argc, char *argv[]) { 15 char flags = 0; //an 8 bit variable // set flags with a logical or flags = flags | FLAG1; //set flag 1 flags = flags | FLAG3; //set flag 3 20 // check flags with a logical and. If the flag is set (1) // then the logical and will return 1, causing the if // condition to be true. if (flags & FLAG1) 25 printf("FLAG1 set!\n"); // this of course will be untrue. if (flags & FLAG8) printf("FLAG8 set!\n"); 30 // check multiple flags by using a logical or // this will pass as FLAG1 is set if (flags & (FLAG1|FLAG4)) printf("FLAG1 or FLAG4 set!\n"); 35 return 0; }