Chapter 2. Binary and Number Representation
1 Binary — the basis of computing
1.1 Binary Theory
1.1.1 Introduction
Binary is a base2 number system that uses two mutually
exclusive states to represent information. A binary number is
made up of elements called bits where
each bit can be in one of the two possible states. Generally,
we represent them with the numerals
1
and
0
. We also talk about them
being true and false. Electrically, the two states might be
represented by high and low voltages or some form of switch
turned on or off.
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.
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.
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.
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.
1.1.2 The basis of computing
You may be wondering how a simple number is the basis of
all the amazing things a computer can do. Believe it or not,
it is! The processor in your computer has a complex but
ultimately limited set of instructions it
can perform on values such as addition, multiplication, etc.
Essentially, each of these instructions is assigned a number
so that an entire program (add this to that, multiply by that,
divide by this and so on) can be represented by a just a
stream of numbers. For example, if the processor knows
operation 2
is addition, then
252
could mean "add 5 and 2
and store the output somewhere". The reality is of course
much more complicated (see Chapter 3, Computer Architecture) but,
in a nutshell, this is what a computer is.
In the days of punchcards, one could see with their eye the one's and zero's that make up the program stream by looking at the holes present on the card. Of course this moved to being stored via the polarity of small magnetic particles rather quickly (tapes, disks) and onto the point today that we can carry unimaginable amounts of data in our pocket.
Translating these numbers to something useful to humans is what makes a computer so useful. For example, screens are made up of millions of discrete pixels, each too small for the human eye to distinguish but combining to make a complete image. Generally each pixel has a certain red, green and blue component that makes up its display color. Of course, these values can be represented by numbers, which of course can be represented by binary! Thus any image can be broken up into millions of individual dots, each dot represented by a tuple of three values representing the red, green and blue values for the pixel. Thus given a long string of such numbers, formatted correctly, the video hardware in your computer can convert those numbers to electrical signals to turn on and off individual pixels and hence display an image.
As you read on, we will build up the entire modern computing environment from this basic building block; from the bottomup if you will!
1.1.3 Bits and Bytes
As discussed above, we can essentially choose to represent anything by a number, which can be converted to binary and operated on by the computer. For example, 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. In general, with
n
bits we can represent
2^{n}
unique combinations.
8 bits gives us
2^{8} =
256
unique representations, more than enough
for our alphabet combinations. We call a group of 8 bits a
byte. Guess how big a C
char
variable is? One
byte.
1.1.3.1 ASCII
Given that a byte can represent any of the values 0
through 255, anyone could arbitrarily make up a mapping
between characters and numbers. For example, a video card
manufacturer could decide that
1
represents
A
, so when value
1
is sent to the video card
it displays a capital 'A' on the screen. A printer
manufacturer might decide for some obscure reason that
1
represented a lowercase
'z', meaning that complex conversions would be required to
display and print the same thing.
To avoid this happening, the American Standard Code for Information Interchange or ASCII was invented. This is a 7bit code, meaning there are 2^{7} or 128 available codes.
The range of codes is divided up into two major parts;
the nonprintable and the printable. Printable characters
are things like characters (upper and lower case), numbers
and punctuation. Nonprintable codes are for control, and
do things like make a carriagereturn, 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!
1.1.3.2 Parity
ASCII, being only a 7bit 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 punchcards 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
1.1.3.3 16, 32 and 64 bit computers
Numbers do not fit into bytes; hopefully your bank
balance in dollars will need more range than can fit into
one byte! All most all generalpurpose architectures are at
least 32 bit computers. This means
that their internal registers are 32bits (or 4bytes) wide,
and that operations generally work on 32bit values. 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 int
variable is 32 bits. Modern architectures are 64 bits,
which doubles the size the processor works with to 8
bytes.
1.1.3.4 Kilo, Mega and Giga 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 a round number —
(10000000000
— and
happens to be quite close to the base 10 meaning value of
"kilo" (1000 as opposed to 1024). Thus 1024 bytes naturally
became known as a kilobyte. The next
SI unit is "mega" for
10^{6}
and the prefixes continue upwards by
10^{3} (corresponding to the usual
grouping of three digits when writing large numbers). As it
happens,
2^{20}
is again close to the SI base 10 definition for mega;
1048576 as opposed to 1000000. Increasing the base 2 units
by powers of 10 remains functionally close to the SI base 10
value, although each increasing factor diverges slightly
further from the base SI meaning. Thus the SI base10 units
are "close enough" and have become the commonly used for
base 2 values.
Name  Base 2 Factor  Bytes  Close Base 10 Factor  Base 10 bytes 

1 Kilobyte  2^{10}  1,024  10^{3}  1,000 
1 Megabyte  2^{20}  1,048,576  10^{6}  1,000,000 
1 Gigabyte  2^{30}  1,073,741,824  10^{9}  1,000,000,000 
1 Terabyte  2^{40}  1,099,511,627,776  10^{12}  1,000,000,000,000 
1 Petabyte  2^{50}  1,125,899,906,842,624  10^{15}  1,000,000,000,000,000 
1 Exabyte  2^{60}  1,152,921,504,606,846,976  10^{18}  1,000,000,000,000,000,000 
It can be very useful to commit the base 2 factors to
memory as an aid to quickly correlate the relationship
between numberofbits and "human" sizes. For example, we
can quickly calculate that a 32 bit computer can address up
to four gigabytes of memory by noting that
2^{32}
can recombine to 2^{(2 +
30)}
or
2^{2} ×
2^{30}
, which is
just 4 ×
2^{30}
, where we
know
2^{30}
is a gigabyte. A 64bit value could similarly address up to
16 exabytes (2^{4}
× 2^{60}
); you
might be interested in working out just how big a number
this is. To get a feel for how big that number is,
calculate how long it would take to count to
2^{64}
if you incremented once per second.
1.1.3.5 Kilo, Mega and Giga Bits
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, MiB, for
example). Tradition largely prevents use of these terms,
but you may seem them in some literature.
1.1.3.6 Conversion
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.
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.
1.1.4 Boolean Operations
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.
1.1.4.1 Not
Usually represented by
!
,
not
simply inverts the
value, so 0
becomes
1
and
1
becomes
0
Input  Output 

1

0

0

1

1.1.4.2 And
To remember how the and operation works think of it as "if one input and the other are true, result is true
Input 1  Input 2  Output 

0

0

0

1

0

0

0

1

0

1

1

1

1.1.4.3 Or
To remember how the
or
operation works think of
it as "if one input or the other input
is true, the result is true
Input 1  Input 2  Output 

0

0

0

1

0

1

0

1

1

1

1

1

1.1.4.4 Exclusive Or (xor)
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.
Input 1  Input 2  Output 

0

0

0

1

0

1

0

1

1

1

1

0

1.1.5 How computers use boolean operations
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 Moore's 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.
1.1.6 Working with binary in C
In C we have a direct interface to all of the above operations. The following table describes the operators
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.
1.2 Hexadecimal
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.
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 16bit
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
Quotient  Remainder  

203_{10} ÷ 16 =  12  11 (0xB)  
12_{10} ÷ 16 =  0  12 (0xC)  ↑ 
Hence 203 in hexadecimal is
0xCB
.
1.3 Practical Implications
1.3.1 Use of binary in code
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.
1.3.2 Masking and Flags
1.3.2.1 Masking
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. This uses the rules of logical operations to extract values.
The process is illustrated in the figure below. We
can keep two separate 4bit values "inside" a single 8bit
character. We consider the upper fourbits as one value
(blue) and the lower 4bits (red) as another. To extract
the lower four bits, we set our mask to have the lower4
bits set to 1
(0x0F
). 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.
To get the top (blue) four bits, we would invert the
mask; in other words, set the top 4 bits to
1
and the lower 4bits to
0
. You will note this
gives a result of 1010 0000
(or, in hexadecimal 0xA0
)
when really we want to consider this as a unique 4bit value
1010
(0x0A
). To get the bits
into the right position we use the right
shift
operation 4 times, giving a final
value of 0000 1010
.
#include <stdio.h>
#define LOWER_MASK 0x0F
#define UPPER_MASK 0xF0
int main(int argc, char* argv[])
{
/* Two 4bit values stored in one
* 8bit variable */
char value = 0xA5;
char lower = value & LOWER_MASK;
char upper = (value & UPPER_MASK) >> 4;
printf("Lower: %x\n", lower);
printf("Upper: %x\n", upper);
}
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.
1.3.2.2 Flags
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.
#include <stdio.h>
/*
* define all 8 possible flags for an 8 bit variable
* name hex binary
*/
#define FLAG1 0x01 /* 00000001 */
#define FLAG2 0x02 /* 00000010 */
#define FLAG3 0x04 /* 00000100 */
#define FLAG4 0x08 /* 00001000 */
/* ... and so on */
#define FLAG8 0x80 /* 10000000 */
int main(int argc, char *argv[])
{
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
/* 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)
printf("FLAG1 set!\n");
/* this of course will be untrue. */
if (flags & FLAG8)
printf("FLAG8 set!\n");
/* check multiple flags by using a logical or
* this will pass as FLAG1 is set */
if (flags & (FLAG1FLAG4))
printf("FLAG1 or FLAG4 set!\n");
return 0;
}