Bits are central to computers. All information in a computer is represented as bits. Bits are also fundamental to how programs make decisions and how arithmetic is approximated in a computer. So it is worth your energy to understand bits and how they are used.
While this section of the course does not directly concern itself with programming and Pascal, it does provide a way of looking at what you are doing that will deepen your understanding and allow you to `look through' Pascal and see the machine and the ideas behind the machine that make everything work.
Pascal does not concern itself with bits and their representations; it pretends they are not there. But underneath, when you run a Pascal program the machine is following its own rules, and it has its own way of doing things. It is important that you understand this mechanism when you program in Pascal, because every operator and statement in a Pascal program is bound by the limits of the computer and the bits that make it work.
More important, Pascal pretends that Boolean values, integers, and characters are different things, when underneath they are all just combinations of the same thing with different operations. Seeing the unity beneath the diversity of the Pascal types allows you to understand the means of creating new types of your own devising.
No matter how hard Pascal tries to be `machine independent' and
mathematical, its basic concepts are machine concepts, and its
programs are bound by computer limitations.
Mathematics is tied to the infinite; there are an infinite number
of integers; there are an infinite number of fractions between
0.0001 and 0.0002.
In mathematics whenever you need a number to represent something
the number appears magically and is available to use, some of these
numbers are hard to write out because they are not a simple fraction,
like pi and the 
, but they are still there.
But Pascal is tied to computing machines and finite ways of doing things.
The value pi can not be represented in the common methods of representing
numbers inside a computer. However as programmers we are usually satisfied
with a machine representation of some fraction which comes close to
the value of pi.
Computer arithmetic works so well across the usual domain of numbers that we experience daily that it lulls us into a false sense of security, We forget that the computer doesn't really handle the generality of mathematical arithmetic; numbers don't go on forever inside a computer; fractions are only approximate; and danger lurks around every method of computation. It is dangerous to reason about programs using mathematics without thinking about machine limitations because often things which are mathematically correct and provable just don't `compute'. We will meet several examples later.
Because all practical programming languages, including Pascal and C are bound to the computer and thus to particular ways in which the computer hardware is constructed, you need to understand these ideas. By understanding the basic representations of numbers used in computers you can reason out why the mathematics doesn't work.
You have coded several programs, in 07.100 and in the first part of this course. You should begin to feel confident that you can write a simple Pascal program. This should help you put these ideas into a framework so you can more clearly see the computing machine that will cary out your program.
This section of the course will help you deepen your understanding and give you these insights. You should read and reread these notes until you understand everything. The material covered here is so basic and important that you have to know it intuitively. Everything else you learn about computer's will be based on these ideas.
In computer studies there are many different ways of looking
at, defining, and using a bit.
This short survey is aimed to give you the basics of each
of those ways to look at this most fundamental of computer concepts -- a bit.
A bit represents information, any information. Call it an information carrier. The minimum number of bits required to hold some data is a measure of how much information the data contains.
The ever classic example is: How much information is required to represent the outcome of flipping a coin. Assume we have an ideal coin, when flipped we expect the coin to land with equal numbers of heads and tails being visible; we never expect it to land on its edge and stand upright.
Flipping this ideal coin represents two equally likely outcomes: TAIL or HEAD. If the coin lands heads one can write down the bit value `1' to completely represent the outcome of the coin toss. This represents the amount of information held by a bit: zero or one. A bit represents one outcome of two equally likely alternatives from an experiment.
So a sequence of bits can represent a series of successive coin tosses.
A mechanism, like a box that flips coins, which produces a series of bits, is sometimes called an information source. It is a little odd to call something that produces random bits an information source, but in communications a bit is a bit, it doesn't matter where it came from, so from that perspective information is the same as noise.
Later we will show that results, which you do not expect, give you more information than ones you do expect; the more unexpected an event the more information it gives. This is not your usual notion of information, but it is a technical definition that gives insight into what you can do with computers. Therefore from that technical perspective flipping a coin gives you maximal information because you never know what the next bit will be. This is another sense in which a random series of bits and information are the same thing.
As an aside, the ceiling function, ceil(p), is one that is handy
and will get used a lot.
Ceil is defined so that if the argument, p, has no fractional components
then ceil(p) gives back the same integer number as a result, and
if p does have fractional components ceil(p) gives the next higher integer.
The result of ceil is always an integer.
Thus: the ceil( 3.00001 ) is 4, the ceil( 3.9 ) is 4,
and the ceil( 4 ) is 4.
The ceiling function is sometimes represented as a peculiar set of brackets
is 4.
There is also a floor function which works like ceiling.
Thus: floor( 3.00001 ) is 3, the floor( 3.9 ) is 3,
and the floor( 4 ) is 4.
Floor can also be represented as 
.
Now, back to the topic,
how many equally likely outcomes are there if a coin is flipped twice?
Four equally likely outcomes can be represented by two bits. For three coin flips 8 different equally likely outcomes and three bits. For four coin flips 16 different equally likely outcomes and four bits. And so on.
This tells us that if something has N equally likely possibilities
it will take: 
bits
to represent the outcomes. (Why do we take the ceiling?)
For example if one is to toss a pair of dice, there are 36 equally likely
possibilities: 
is approximately 5.169925 thus it takes 6 bits
to represent the toss of a pair of dice.
You will find it useful for your future in computing to memorize the
first 16 or so powers of two.
And I mean memorize, it will help you finish exam after exam faster,
leaving you time to work on other problems.
By memorizing them you will be able to spot powers of two when you see them,
and that will help see deeper relationships that you may exploit.
The small powers of two are:
Note that 25 is 32 and 26 is 64. The log2 of 36 (which we looked up earlier) was 5.169925 a number just greater than the log2 of 32, which is exactly 5. So the exponents of the powers of two give you a feeling for the log base 2 of a number. This is another reason to remember the powers of two table.
A good number to remember is 3.321928, the 
.
It tells you how many bits are in ten things, like ten fingers
or ten digits.
To get a feel for the number of bits you need to represent 500 things,
follow the following reasoning! Since 500 has 3 digits,
multiply the number of digits by 3.32 to get 9.96 or 9 or 10 bits.
Note the estimate is right on. Ten is little over the answer,
which should be 9 bits. This is because 3 decimal digits numbers include
all the numbers up to 999,
999 requires ten bits to represent.
Here the trick is to use the number of decimal
digits as a measure of the log10 of the number to get a quick, worst
case estimate of the number of bits required.
A more accurate way is to compute
to find the number of bits required.
It is easy to compute the log2 of a number on a calculator by using
the following formula:
can be computed by finding
then multiplying that by
the magic number 3.3219 and you get: 8.9657.
Doing 
gives the correct answer 9 bits.
If you can't remember the magic number 3.3219 then use a formula
in which the calculator can figure out all the numbers in the formula.
Computationally this is not as good because you have to remember
what to divide by what.
Multiplication is easier; it can be done in any order.
Another example, if you have a bit representation that is 52 bits long,
how many decimal digits will be needed to represent the
same information?
The answer is 
giving 15.66 or it will take
16 decimal digits to uniquely identify each of the 252 cases
(i.e. using 
).