(Last Mod: 27 November 2010 21:38:39 )
Pointers are a topic that present a major obstacle for many people.
In the base-10 numbering system nearly everyone is familiar with, the word "digit" refers to one of the ten symbols used to encode values into a written representation. The number 3784, for instance, consists of four digits. Each one of the digits can be any of the ten symbols, 0 through 9, that we use in this system. We refer to this set of ten digits as "decimal digits" because as we go from one to the next, say a 4 to a 5, the value changes by one-tenth (hence "deci-") of the number base.
If we were to use a different number base, the word "digit" would still have the same meaning. In the case of base-2, we would have just two symbols, 0 and 1, to choose from for each digit. We refer to this as the set of "binary digits". Instead of having to constantly use the phrase "binary digit", it has been shortened to simply "bit" for convenience.
A bit always refers to a single digit that can take on exactly one of two possible states. Depending on the context, we might refer to these states using a number of different labels. Some of the more common ones are:
{0, 1}, {OFF, ON}, (LO, HI), {FALSE, TRUE}, {CLEARED, SET}
Generally the first label in each group is stored the same way as the first label in any other group and the same for the second label. In other words, if we store a LO as 0V on a capacitor and HI as 5V on a capacitor, then 5V would also be interpreted as being a 1, ON, TRUE, and SET, depending on which pair of labels made the most sense in a given context. This is NOT engraved in stone and playing games with the polarity of different signals is one of the common ways that digital designers use to obtain higher performance from a particular system, although usually at the expense of clarity.
A bit can be used to encode whether a certain piece of information is in one of two possible states. It might tell us whether a light is on or off. It might tell us whether the water level in a tank is rising or not. It might tell whether the pressure in a line is within sage limits or not. While useful, a single bit is almost never sufficient to provide all of the information that we need. Therefore we use many bits in combination to build up what is known as a "digital system". A digital system is simply a system where the signals we are interested in are encoded into discrete digits - usually binary digits or bits. The counterpart to a digital system is an analog system where the signals are encoded by some parameter, such as the voltage on a wire, that can take one any value within a continuous range.
Modern digital systems, of which a computer is just one example, are nothing more than machines that combine many, many bits of information along with some mechanism of "reading" what the state of each of those bits presently is and of "writing" to each of those bits so as to force it to take on one of the possible values that it can represent.
So far we have dealt only with individual bits. Although we could build up a digital system strictly working with individual bits - and many systems, even some complex systems, are constructed just this way - we often find it easy to work with collections of several bits as a single piece of data. The usual motivation for doing so is that we want to represent information that cannot be encoded adequately using just two states. By using multiple bits, the number of states that can be encoded grows exponentially. To be more specific, if we have N bits, then we can encode 2N different states.
The term "byte" was coined by Dr. Werner Buchholz from IBM in the 1956 and was meant to apply to a data group consisting of eight bits. He apparently used the common meaning of "bit" as meaning a "small bite" and replaced the 'i' with a 'y' to prevent "bite" from being mistaken too easily for "bit". While it certainly caught on, "byte" quickly became the generic term used for the "atomic" data size of a processor - atomic meaning the smallest addressable amount of memory. Many systems therefore existed that have bytes that where anywhere from six to nine bits wide. Today, almost all machines use an eight-bit byte and, unless indicated otherwise, all of the material in this course is to be interpreted as referring to eight bit bytes.
With eight bits, a byte can take on 28, or 256, distinct states. Although it is completely up to us to determine what each one of those unique states represents, there are a couple of highly standardized mappings - integers and characters.
Since computers are used extensively for processing numeric data, it is only reasonable that one of the mappings for a collection of bits should represent numeric values. As will be explored in later lessons, there are many different ways to map numeric values onto a set of bits. For now, we will limit the discussion to non-negative integers using a mapping known as "straight binary" or "unsigned binary".
Sticking to our 8-bit byte, with 256 discrete values available to us, we will use them to represent the integers 0 through 255. The mapping we will use will follow the same rules as the base-10 numbering system we use everyday. As with the other ways to represent numeric values in binary, we will explore the rules and properties of positional numbering systems in much greater depth in later lessons.
| Bit # | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| Label | b7 | b6 | b5 | b4 | b3 | b2 | b1 | b0 |
| Weighting | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 |
| Decimal | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Notice that we start the labeling with 0 instead of 1. This is almost universal in computer science and, for most applications, is quite convenient. Notice that the bit number, the bit label, and the exponent to which the base (2) is raised are all the same because of this convention.
| Bit # | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| Label | b7 | b6 | b5 | b4 | b3 | b2 | b1 | b0 |
| Weighting | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 |
| Decimal | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| 10110101 = | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| Value | 128 | 0 | 32 | 16 | 0 | 4 | 0 | 1 |
The value of each bit it obtained by multiplying the bit by the weighting for that bit, as shown in the above table in the "Value" row. The value for the byte as a whole is then simply the sum of the values for all the bits. In this case it turns out to be:
Value = 1011 0101 b = (1 x 128) + (0 x 64) + (1 x 32) + (1 x 16) + (0 x 8) + (1 x 4) + (0 x 2) + (1 x 1) = 181
Notice that we separated the binary representation into groups of four bits. This is for readability, just as we frequently separate large decimal values into groups of three digits separated by commas. In order to prevent confusion, we also generally indicate when a number is not expressed in decimal form unless the context makes if very clear that this is the case. For binary representations, we commonly follow the value with a 'b'. If subscripted numbers are available to us, then we might also us a subscripted '2' after the value.
Fast and efficient ways of performing number base conversions will be a topic of a later lesson. For now, we will use the brute force method as it is adequate for our present needs. We will simply start with the largest weighting and, if it is less that the value we are trying to represent, we will set that bit and subtract that weighting from our value. If it is larger than our value, we clear that bit and do nothing to our value. We then proceed to the next bit using the remaining part of our original value and follow this same procedure until we get to the smallest weighting. Using this, we find that the number from our example would be represented as:
| Bit # | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| Label | b7 | b6 | b5 | b4 | b3 | b2 | b1 | b0 |
| Weighting | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 |
| Decimal | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| 217 = | 128 | 64 | 0 | 16 | 8 | 0 | 0 | 1 |
| Result | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
Value = 217 = 1101 1001 b
Not surprisingly, the same basic set of arithmetic operators that you are already familiar with are available for use with integers stored as bytes in a computer. Because of the finite range of values that can be represented by a specific number of bits and because only integers can be represented in an integer data type, there are a few issues that need to be understood in order to avoid programming errors.
The addition of two integers behaves exactly as you would expect provided the limits on the range of representable numbers is not exceeded.
The subtraction of one integer from another behaves exactly as you would expect provided the limits on the range of representable numbers is not exceeded.
The multiplication of two integers behaves exactly as you would expect provided the limits on the range of representable numbers is not exceeded.
The division of two integers does not behave exactly as you would expect - the result is the integer quotient with any fractional part discarded. For signed integers, if the result is negative, then the result is truncated towards zero. For instance, if (-14)/(5) would yield a result of (-2).
Module division is the remainder after integer division. For instance, 15 The division of two integers does not behave exactly as you would expect - the result is the integer quotient with any fractional part discarded. For signed integers, if the result is negative, then the result is truncated towards zero. For instance, if (-14)/(5) would yield a result of (-2).
The integer and modulo division operations are linked by the required relationship that:
a = (a / b)*b + (a % b)
Notice that this means that:
(a % b) = a - (a / b)*b
and
(a / b) = (a - (a % b)) / b
The C language does not have an exponentiation operator - no matter how hard people constantly try to invoke one. It doesn't exist. There is a function in the math library, pow(), that returns the result of one value raised to another value. It is also very common to simply use repeated multiplication when small, integer exponents are needed.
If the ideal result of one of the above operations cannot be represented by the data type in use, then the result may or may not be well defined. In the case of C, the behavior is defined for unsigned integer types, but not for signed integer types. For unsigned integers, the result "wraps around" using modulo-2N arithmetic. In short, this means that, given an ideal result, the actual result can be found as follows:
Actual Result = (Ideal Result) + k*2N
Where k is an integer (positive, negative, or zero) such that the actual result falls in the range:
0 <= Actual Result < 2N
Again, the C standard does not define the behavior under similar conditions for signed integers.
The basic assignment operator in C is the single equals sign, '='. On the right hand side of the assignment operator is an expression that evaluates to a value and on the left hand side is an expression that evaluates to an "lvalue". Simply put, an lvalue is anything that can accept a assignment - known as an "object". After evaluating the expression on the right, the resulting value is written to the memory allocated for the object indicated by the expression on the left. Note that this use of the term "object" has nothing to do with the same term used in the context of Object Oriented Programming. In C, an "object" is merely a region of data storage whose contents can represent values.
Examples:
char j, k;
j = 9; // The right hand side evaluates to the value 9 and this value is written to the memory location allocated for the variable j.
k = 2 * j + 4; // The right hand side evaluates to 22 and this is written to the memory location allocated for k.
k = j * k; // The right hand side evaluates to 198 and written to k.
j + k = 45; // Illegal, because the left hand side does not evaluate to an object that can be written to.
At first, lvalues will be simple variable names. In later lessons, more complicated expressions that evaluate to an lvalue will be introduced and explored.
Nearly all expressions in C evaluate to a value that can be assigned to another object. This includes assignment operators. An assignment operation evaluates to the value that was assigned. This property makes the following statements legal, though not always advisable from a readability perspective.
j = k = 12;
j = 4 + (k = 5 + 2*j) + 16;
In programming one of the most common types of operations that get performed are so called "read-modify-write" operations where the present value stored in an object is first read, then modified in some manner, and finally the result is written back into the same object. These can frequently be written in the following generic form:
(lvalue) = (lvalue) (operator) (expression);
Examples would include:
j = j + 4;
k = k * (j + 1);
This is so common, that most operators in C have a shortcut form called an "abbreviated assignment operator" that permits the above generic form as:
(lvalue) (operator)= (expression);
So the two examples above could be re-written as:
j += 4;
k *= (j + 1);
Notice that not all expressions that are read-modify-write can be written using an abbreviated assignment operator. For instance, the statement:
k = 2 * (k + 1);
Cannot be. In general, an abbreviated assignment operator can be used if the present value of the object is one operand of an operator and the entire remainder of the expression is the other operand, which is what the generic form above specifies.
Just as read-modify-write operations are so common that they warranted shortcut forms, a special subset of read-modify-write operations is similarly so common as to warrant even shorter forms. Specifically, incrementing and decrementing the value stored in an object is so common that the generic expression:
(lvalue) = (lvalue) + 1;
Can not only be written using an abbreviated assignment expression in the form:
(lvalue) += 1;
But it can also be written in the even shorter form:
(lvalue)++;
This is called the "increment operator". More specifically, for reasons explained shortly, it is the "post-increment operator". There is also a "post-decrement operator" that behaves as follows:
(lvalue) = (lvalue) - 1;
Can be written as
(lvalue)--;
There is, however, a subtle difference. The value of a post-increment or post-decrement operation is the original value stored in the object. For example:
j = 15;
k = 13 + j++;
The (j++) expression evaluates to 15 and so the result that is stored in k is the value 28.
When it is desired to have the new value used in the expression, the pre-increment and pre-decrement operators can be used. Here the '++' or '--' operator is simply written prior to the object to be modified. For example:
j = 15;
k = 13 + ++j;
The (++j) expression evaluates to 16 and so the result that is stored in k is the value 29.
When used in expressions, it is best to separate the concept of the evaluated value from the side effect. For instance, in the expression
k = k + (j + 1);
The expression in parentheses evaluates to a value. Where the object j gets modified or not is irrelevant to the question of what value the expression evaluates to. The same is true for the increment and decrement operators. The post- versions evaluate to what ever the operand is while the pre- versions evaluate to one greater than, or one less than, the operand as appropriate.
The fact that these operators change the value stored in an object, in addition to evaluating to a value, is referred to as a "side effect". The same is true of all of the assignment operators. In most cases where they are used, we are only interested in the side effect. But when they are used as part of a larger expression it must be kept in mind that the assignment action itself is considered a side effect. The important thing to note is that the exact time at which side-effects are applied is not tightly defined. The C language standard defines "sequence points" and states that all side effects must be applied prior to proceeding to the next sequence point. But within a section of code in between sequence points the side effect can be applied immediately or delayed until just before the sequence point is reached.
The practical effect that this has for most programmers is that a very strong rule of thumb is to never perform more than one assignment operation on the same object within the same expression and never use the value stored in an object that is subject to side-effects except in the segment of the expression that is responsible for the side-effect.
For example:
k = k++;
Has two side-effects on k, one from the post-increment operator and one from the assignment operator. While the right hand expression evaluates to a well-defined value - the original value of k - the value that eventually gets stored in k is undefined because the order in which the side-effects are applied is undefined.
j = 2 * k + (k++);
The value of k when it is multiplied by 2 is undefined because the side-effect may or may not have been applied prior to evaluating that part of the expression.