Specifying Bit Patterns

Some bit patterns are thrust upon us from the outside world and many of them are specified as literals. A literal is just a value specified at compile time that the compiler converts to a specified bit pattern. We use numeric literals or constants so often that we almost ignore them.

For example:

int a = 42;

seems simple and innocent, but the compiler reads the 42, the literal, and converts it into a bit pattern 00101010 and stores this in the variable a. There are many ways to specify a bit pattern using a constant – decimal, octal, hex and so on. For now all that matters is that you realize that in C every number you specify is converted into a representation that gives a bit pattern.

The next question is how numbers become bits and vice versa.

Place Value Systems

Bits are our raw material and we don’t need to start from numbers to find them useful. In fact, numbers are just another “something” that bits can represent. However, unlike simple states, representing numbers requires a bit more organization. If you know everything about place value systems skip this section, although it does point out some things that more mathematical approaches miss.

Consider how you might keep a record of how many cars have passed your front door. You might well use a mark to indicate each one as it goes by to avoid getting confused:

but after a while the number of marks would become too many to cope with. In most cases you might start grouping the marks together – perhaps five at a time:

and you might use a special symbol for five cars:
                   V      V      V      V     111

where V represents a group of five ones. Congratulations, you have now invented the Roman system of number representation.

Your next obvious step as the number gets bigger is to invent another symbol for a bigger grouping. For example, X for ten items, which means we can now write:

XX111

to represent 23. We will ignore many ways the Romans invented ways to make their system simpler – for example 1X is a valid representation of 9 things as the small value to the left of the big value is subtracted from the big value.

This isn’t a bad way to represent numbers until you try to do arithmetic and then you quickly discover its limitations. Try adding the number of cars I saw yesterday (27) to the number today:

(XXV11)+(XX111) = (XXV11XX111) = XXVXXV = XXXXVV = XXXXX

there is much regrouping of symbols to cope with.

If you think this is cumbersome try subtraction and then multiplication. For example, what is XXV11 times X? It turns out to be easier to convert the Roman numerals to decimal notation, do the sum and then convert back.

Let’s suppose for a moment that you are a Roman trying to make the system better. The key principle is that you use symbols to represent groups of items. So 1 is one item and V is a group of five. Clearly to represent a larger number you need to make bigger groups. Why not just repeat your first clever idea and use V to represent a group of five things, but why not have each thing be a group of five! This is the sort of thing a programmer would invent. So:

V = (11111)

and

V = (VVVVV)

The problem is working out which of these you have when you encounter a V. The less creative thing to do is just invent another symbol and we are back to the Roman method. The really clever idea is to use the position that you write the symbol in a group of symbols. This is clever because, not only do you not need to invent another symbol, you can get rid of the symbol you just invented as well.

So you might
record:

which is four lots of five and three lots of one i.e. 23 in our standard notation. Notice that you now don’t need the new symbol V. You are counting in groups of five but you only need a symbol for numbers up to five because when you hit five you simply record a one in the next place.

This is such a good idea you might as well carry on with it. Why not add another position to count groups of five lots of five things, i.e. 25 things in our standard notation. For example:

So we now have one lot of 25, two of five and three ones making a total of 38 in our notation. Notice that again we still don’t need the symbol for five and we don’t need a new symbol for 25 – the place value system just works with the symbols we have. When you reach four lots of five and four lots of ones adding one more simply gives you one lot of 25 and a mark in the third position.