Bottom     Previous     Contents

Chapter Twelve
Bits, Binary and Boolean Loglc

It may seem odd to leave a discussion of the sort of thing that is often included in introductory courses on computing to the very end of a book on advanced programming. However, although bits, binary numbers and Boo lean logic do form part of the foundations of computing, most of the efforts of computer scientists have been concentrated on hiding this fact! For example, high level languages such as BASIC were invented to avoid a face-to-face confrontation with the underlying principles of computing.
The BBC BASIC interpreter will accept commands to do arithmetic in terms of the familiar decimal notation, convert everything to a binary representation, work out the result using binary arithmetic and will then convert this back to decimal for printing! In fact, it is possible to use a computer without ever realising that it has anything to do with bits, binary or Boolean logic and for the most part this is how it should be. For the ordinary user a computer is a tool and its internal workings should be hidden. The question of how much of the internal workings a programmer should know is debatable. On the one hand most programs can be written without reference to 'low level' concepts such as bits. In this sense languages such as BASIC have been successful in making programming more accessible. However, there are still many reasons why BASIC and other high level languages are not 'powerful' in terms of speed, memory use, etc., and this occasionally forces the use of assembler and other 'low level' languages.
Assembler is closer to the underlying hardware and so it works in terms of bits and binary numbers and this is often the main reason that BASIC programmers find it difficult to adapt to assembly language programming. The point is that while it is easy to understand what assembly language instructions do, and even relate them to statements in BASIC, it is not easy to see how to use them the problem is that even if the operation is familiar, it is performed on primitive forms of data not normally found in BASIC. For example, the assembly language ADC (ADd with Carry) performs the familiar operation of addition, but on eight-bit binary numbers.
It is clear that if you want to use assembler effectively you must have at least a working knowledge of some of the ideas at the heart of computing. What is less obvious is that the need for this knowledge also arises in BASIC. A BASIC program that interacts dtrectly wnh the hardware of a machine usually has to manipulate data at the level of binary numbers. Also, it is sometimes possible to save both memory and time by manipulating data directly in terms of its underlying binary representation and so avoid having to use assembler to achieve the same result.
All this suggests that once you have learned to use a high level language then the next thing to do is to learn about bits, binary and other technical topics before beginning the task of learning assembler! Bits, binary and logic may be fundamental to computing but they are definitely not the first things you should learn. If you follow this order, learning assembler will be easier because you will know about the sort of data and operations that make up an assembly language program but imagine how difficult learning BASIC would be if you had to also learn all about decimal numbers on the way! If you have already studied assembler then the contents of this chapter may help you to apply what you know.
If the idea of learning about such mathematical concepts is off-putting then it worth saying at this point that there is much in this chapter that is directly about programming! If you find any of the topics difficult at first reading, then just look them over and return to them when you actually need to know something about them.

Bit patterns

The raw material of computing is the bit pattern. All the other types of data described in Chapter Five are represented in the computer's memory using bit patterns. A bit pattern is nothing more complicated than its name suggests; that is, a pattern of zeros or ones. A memory location can store only a fixed size of bit pattern. In most of the current micros, including the BBC Micro, a single memory location always stores a bit pattern consisting of eight bits. A group of eight bits is such a common unit that it is given the name of byte probably the best known piece of all computer jargon. However, it is important to realise that this use of eight bits is entirely arbitrary and it will change as new generations of computers with greater memory capacities are produced.
A bit pattern can be used to represent all sorts of information. For example, suppose that you live in a house with eight rooms then you could record which rooms had lights on and which had them off by using one bit per room and a code such as (0=off and 1=on. In this way the bit pattern 00000011 would mean that all but two of the rooms had their lights off. It is important to realise that the information a bit pattern holds is entirely in the eye of the beholder. If, for example, we take 0 to mean 'light on' and 1 to mean 'light off' then the same bit pattern as above now records the fact that all the lights are on bar two! A bit pattern doesn't have a built-in meaning; it all depends what you use it for.

Simple binary

The most familiar use of a bit pattern is as a binary number. In some ways the familiarity of binary numbers is a problem in that it tends to obscure the more fundamental idea of a bit pattern. In fact, we are generally so familiar with numbers that it is often difficult to see how they work. Although the use of a bit pattern to represent a number is almost identical to the way that we use patterns of digits to represent numbers, if often causes a great deal of trouble for beginners. The best advice is that if you are in any doubt about how binary, or any other sort of number system, works then compare it with the way that decimal numbers work.
The standard decimal representation of a number uses a 'place value' system. For example, the number 123 means I 'lot' of one hundrgd, 2 'lots' of tens and 3 'lots' of I. In other words, the meaning of a digit depends on its 'place' within a number. Another way of expressing the meaning of a decimal number like 123 is:

1*100 + 2*10 + 3*1

and you can see that the value of the number is arrived at by multiplying each digit by a constant, or 'weight', that depends on its position. In the case of a decimal number the weights follow a regular pattern, starting with a weight of I for the right-hand digit and this weight increases by a factor of l0 for each position moved to the left. If the digit positions are numbered with the first position on the left as 0, the weight for position I is simply 10^1. (To see that this equation works you need to know that 10^0 is 1. Indeed, it is a strange fact that any value raised to the zero is 1.)
The most obvious way of using a bit pattern to represent a number is to modify the decimal place value system to take account of the fact that each bit has only two states (0 or 1) unlike the ten different states that a decimal digit can take (0 to 9). Apart from the binary weights being powers of two rather than powers of ten no other modifications are required. in other words the bit pattern l0 l0 interpreted as a binary number is:

1*8 + 0*4 + 1*2 + 0*1

Notice that only 0 and 1 can occur in a binary number and the weights are given by 2^1 where I is the bit position numbered starting from 0. If you work out the sum of each bit multiplied by its associated weight you will, of course, get the value that the big pattern represents in decimal. This simple observation is all that is needed to write a BBC BASIC function that will convert binary to decimal:

10 INPUT B$
20 PRINT FNbin_to_dec(B$)
30 GOTO l0

9000 DEF FNbin_to_dec(B$)
9010 LOCAL I,D
9020 D=0
9030 FOR I=1 TO LEN(B$)
9040 D=D+EVAL(MID$(B$,I,1))*2^(I-1)
9050 NEXT I
9060 =D

You can use this function to convert a string of zeros and ones to decimal but notice that it doesn't check to see that no other characters are used in the string and that it isn't the fastest method of converting to decimal.
Once you understand the way that the binary place value system works, binary numbers are easy. For example, the smallest number that can be stored in a single eight-bit memory location is 00000000, or just 0 in decimal, and the largest is 11111111, or 255 in decimal. If you need to use a larger numeric range then you can extend the number of bits available by using more than one memory location. For example, using the bit pattern stored in two memory locations provides sixteen bits to represent a number and this gives a range of 0 to 65535. One of the memory locations has to be used to store the eight bits associated with the smaller place values i.e. bit 0 to bit 7 this is called the 'least significant' byte and the other is used to store the bits associated with the larger place values i.e. bit 8 to bit 15 and this is called the 'most significant' byte. The only trouble is that the byte indirection operator 'T only handles single memory locations. That is:

?A=100

will first convert the decimal number 100 to an eight-bit binary representation and then store the bit pattern in the memory location whose address is in 'A'. You cannot use'?' to store a vaine that needs sixteen bits to represent it directly. For example:

?A=3000

will not convert 3000 to a 16-bit binary representation and store it in the two memory locations indicated by 'A'. To store a 16-bit value it is necessary to separate out the most and least significant bytes. This is most easily done using the operators MOD and DIV:

Most significant byte = value DIV 256
Least significant byte = value MOD 256

Putting the two bytes back together is just as easy. If A contains the least significant byte and A+1 the most significant then:

value=?A+256*(A?1)

The reason why these equations succeed in splitting and recombining 16-bit numbers will be clear after the section on bit manipulation.

Negative numbers or two's compliment binary

With simple binary it is only possible to use bit patterns to represent postive integers. It is important to realise at this stage that there are a number of different ways of making a bit pattern represent negative numbers. For example, we could use the standard decimal method of a special symbol to indicate that a number is negative - +6 is a positive number and -6 is a negative number. This is known as sign magnitude representation because each number is composed of a sign that indicates whether it is positive or negative and a number that indicates its size or 'magnitude'. The sign magnitude method can be used with bit patterns to represent both positive and negative numbers. In binary the sign magnitude method is just as easy. The sign of a number is indicated by one of the bits, usually with 0 standing for positive and 1 for negative and the remaining bits represent the magnitude using simple binary. For example, an eight-bit sign magnitude number would conventionally use bit 7, the most significant bit, to indicate the sign of the number so:

00000111

would be +7, because bit 7 is 0 for a positive number and the remaining bits represent 7 in simple binary. On the other hand:

10000111

would be -7 because bit 7 is 1 for a negative number and the remaining bits still represent 7 in simple binary.
Although sign magnitude representation is simple to understand it is not easy to do arithmetic with. For this reason most computers use a different method of representing positive and negative numbers known as two's complement representation. This is the method used by the 6502 and by BBC BASIC so it is worth explaining in detail.
It is a fundamental property of a negative number that when added to a positive number of the same magnitude the answer is zero. For example 7+(-7) is 0. In fact this is more than a fundamental property, it is the definition of a negative number! That is, the negative of X is a number Y such that:

X+Y=0

if you can find any number Y that satisfies this equation then it is the negative of X. This looks like an impossible task until you examine the way that binary arithmetic is performed on computers. Unlike paper and pencil arithmetic computer arithmetic is always carried out to a fixed number of bits. For example, using 8-bit numbers and 8-bit arithmetic the result of adding 1 to 255 will be:

1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0

or 256, but 256 needs nine bits to represent it and the computer only keeps the first eight. Thus, in computer arithmetic 255 + 1 is 0. As 1 + 255 equals 0 you should be able to see that 255 can be regarded as a representation of -1. To be precise, it is the two's complement representation of -1. Starting from 0 it is possible to find the representation of the negative of each value. That is the negative of 0 is 0, the negative of 1 is 255, the negative of 2 is 254 and so on. Notice that apart from zero the negative of X is simply:

256 - X

Also notice that whereas an 8-bit simple binary number could represent values in the range 0 to 255, an 8-bit two's complement number can only represent positive numbers from 0 to 127. This is because 128 to 255 are used to represent negative numbers in the range -128 to -1. In binary the fact that 0 to 127 represent positive numbers and 128 to 255 represents negative numbers means that it is possible to use bit 7 to test if a number is negative or positive.
In the same way, 16-bit arithmetic simply ignores any 17th bit that is generated as part of the result Thus in 16-bit arithmetic 1+65535 equals 0 and by the same reasoning 65535 can be taken to be the 16-bit two's complement representation of -1. At first sight it may seem confusing that the two's complement representation of -1 depends on the number of bits that are used but it is not so difficult if you recall that the largest number that can be stored before returning to zero depends on the number of bits. In the case of 16-bit two's complement representation the range that can be represented is --32768 to +32767 and the negative of X is given by:

65536 - X

The great advantage of two's complement numbers from the point of view of the assembly language programmer is that they can be added together without having to worry about whether they are positive or negative. This is not the case with sign magnitude representation. If you want to add 6 and -3 you actually have to notice that the second number is negative and do a subtraction i.e. 6 - (+3). With two's complement this is unnecessary. The same sum in 8-bit two's complement, for example, is 6 + 253 (253 is the 8-bit two's complement representation of 3) which gives 259 or, after ignoring all but the first eight bits, the correct answer, 3. In the same way two's complement numbers can be subtracted without having to take any notice of the sign of any of the operands.

BBC integers

Rather than explore the implications of 8-bit and 16-bit two's complement numbers, it is probably more useful to concentrate on the format used by BBC BASIC to represent integers. That is 32-bit two's complement. Obviously a 32-bit number takes four memory locations to store. The bytes are stored starting with the least signficant byte so the arrangement in memory is:

byte A+3 A+2 A+1 A
b31 to b24 b23 to b16 b15 to b8 b7 to b0

where A is the address of the first byte. The range of values that can be represented is a staggering:

-2,147,483,648 to 2,147,483,647

and to find the two's complement representation of X use:

4294967296 - X

However, the word indirection operator '!' will automatically convert decimal numbers into the correct two's complement representation and vice versa. For example, !A = -2147483648 will store a bit pattern consisting of all ones in the four memory locations starting at A.

Fractions - floating point binary

After extending the use of bit patterns to represent negative numbers, the next obvious step is to find a way of representing fractions. Just as in the case of negative numbers there are many ways of achieving this. The simplest method is just to work as if there was a 'binary point' in the bit pattern. The binary point works in a way analogous to the familiar decimal point. Bits to the left of a binary point have place values that increase by a factor of two, but bits to the right of a binary point have place values that decrease by a factor of two. For example, the bit pattern:

weight 8 4 2 1 1/2 1/4 1/8 1/16
0 1 1 0 . 1 1 0 0

represents 6.75 using eight bits with the binary point fixed between bit 3 and bit 4. This representation is known as fixed point binary and used to be very popular but it has fallen from favour because of its limited numerical range. However, it is often useful in assembly language programs where a limited amount of arithmetic is required.
The most common way of representing fractional numbers and the method that the BBC Micro uses is called floating point binary. This is the binary equivalent of the familiar decimal exponential notation. In decimal a number can be written as:

mantissa * 10^exponent

This form of representation is used by BBC BASIC when the number is too large or too small to print conveniently on the screen. If you try:

PRINT 2^32

you will see the result 4.2949673E9 which means 4.294967*10^9 (the E stands for 'Exponent'). You can also enter numbers in this format in response to an INPUT staternent.
A floating point binary representation has the same overall format as a decimal exponential representation. In the case of BBC BASIC a single byte is used to store the exponent and four bytes are used for the mantissa:

byte A A+1 A+2 A+3 A+4
exponent four byte mantissa
high ® low byte

where A is the address of the first byte. The exponent part of the representation has to allow for the possibility that the exponent might be negative. For this reason an 'excess 128' representation is used. This is yet another way to use a bit pattern to represent both positive and negative integers. As you might guess, an excess 128 representation means that 128 is added to the true exponent before it is stored. Thus 129 would represent an exponent of +1 and 127 would represent an exponent of -1. The value of the number stored is given by multiplying the value of the mantissa by 2^(E-128) where E is the contents of the first memory location. Notice that it is 2 raised to the power of the exponent and not 10! The value stored in the mantissa is represented in rather an odd way. Firstly, it is always assumed that the binary point is just before the first bit and the value that the mantissa represents is more than .5 and less than 1. You can always make sure that the value of the mantissa is more than .5 and less than 1 by altering the value of the exponent. With these two conditions in mind the exponent is represented as a simple binary fraction. However, as this fraction always lies between .5 and less than I you should be able to see that the bit that comes after the binary point is always a I. (The place value of this bit is .5). Always setting a bit to the same value is a waste of storage and so it is used instead as a sign bit. Thus, the mantissa is a modified sign magnitude fixed point representation! It is important to notice that the mantissa is not stored as a two's complement value in the way that an integer is.
This description of floating point is a little complicated so it is worth giving a few examples. The bit pattern:

byte 0 1 2 3 4
sign bit
¯
10000001 00000000 00000000 00000000 00000000
decimal 129 0 0 0 0

represents an exponent of 1 (=129-128) and positive mantissa of value .5. (The sign bit, that is bit 7 of byte 1, is 0 so the number is positive and although all the other bits of the mantissa are also 0, the first bit after the binary point is always 1). Thus the value represented is .5*2^1=1. The bit pattern:

byte 0 1 2 3 4
sign bit
¯
10000011 11100000 00000000 00000000 00000000
decimal 131 224 0 0 0

represents an exponent of 3 (= 131 - 128) and a mantissa of -.875 (-=.5+.25+.125) which gives a value of -7 (=.875*2^3).
If you know the floating point representation it is possible to' 'pick up' values stored in BASIC variables from assembler but any sort of floating point arithmetic is far better handled in BASIC.

Binary Coded Decimal

To close this discussion of how bit patterns can be used to represent numeric values it is interesting to give an example of a completely different method. Binary Coded Decimal (or BCD) representation is a sort of cross between a decimal representation and simple binary. The principle is that instead of converting the entire decimal number to binary each digit is converted separately. As the largest decimal digit is 9, or 100! in binary only four bits are needed per digit. For example the number 1234 would be represented in BCD as:

1 2 3 4
0001 0010 0011 0100

Using four bits per digit means that it is possible to store two digits per memory location and this ghes a range of 0 to 99 which should be compared to the 0 to 255 that can be achieved using simple binary. The main advantage of BCD is that conversion to binary is easy and can be done as digits are entered from a keyboard, say. BCD arithmetic is also an exact parallel of what happens in decimal and this can be a advantage for some applications where accuracy is essential.
The BCD representation is particularly useful in assembler and to this end the 6502 can work in a 'decimal mode'. The instruction SED will SEt Decimal mode and CLD will CLear Decimal mode, i.e. return the 6502 to normal binary arithmetic. In decimal mode two bytes are added together using ADC or subtracted using SBC as if they each represented a pair of decimal digits in BC D. For example,

SED
CLC
LDA #20
ADC #86

will produce the result 112 in the A register. That is the bit patterns that represents 20 and 86 are:

20 = 0001 0100
86 = 0101 0110

which corresponds to 14 and 56 in BCD. Now 14 + 56 =70 and this is represented in BCD by the bit pattern:

0111 0000

which if treated as a simple binary number and converted to decimal is 112.
Notice that during this example the bit pattern was regarded as representing different things. For the purposes of the assembler the bit pattern was expressed in terms of a decimal number but for the purposes of BCD arithmetic it was a pair of digits. This is quite proper and is typical of the sort of 'mental gymnastics' that an advanced assembly language programmer often goes through in thinking about data. A bit pattern can be interpreted and hence written down in many ways. For example the bit pattern :

10000111

is 135 in decimal if it is interpreted as simple binary; it is 7 as a sign magnitude number; it is 121 as a two's complement number; it is 87 in BCD and so on ... The important point is that the reality is the underlying bit pattern what it represents depends on the way we interpret it and the operations that we subject it to.

Hexadecimal

BBC BASIC can work with both decimal numbers and hexadecimal numbers. The main advantage of hex is that it is very easy to convert to binary. For this reason it is a particularly simple way of specifying a bit pattern. Hex numbers use a place value representation with weights that are powers of l6. This use of weights larger than l0 means that it is necessary to invent some extra symbols to stand for values between 10 and IS, As explained in the BBC User Guide the conventional choice for these new symbols is A to F. Thus counting in hex goes ()to 9 as usual and then A, B, C, D, E and F. After F ( 15) the place value system comes into play and the next number is 10 standing for

1*l6 + 0*1

or 16 in decimal. The conversion of hex numbers to decimal follows the method used to convert binary to decimal that is each digit is multiplied by the appropriate weight and the results are totalled. The only complication is the need to work out unfamiliar expressions such as E*16 which are tackled by converting the extra symbols A to F to decimal before trying to perform the multiplication i.e. E*16 is simply 15*16.
However, as already mentioned, the importance of hex numbers is that they are remarkably easy to convert to binary and vice versa. The reason for this is that each symbol that makes up a hex number can be converted to binary without reference to the rest of the number. For example, to convert :

F7C3

all that you have to do is to write down the binary equivalent, of each symbol, that is:

F 7 C 3
1111 0111 1100 0011

giving 1111011111000011 as the answer. Note that you have to be careful to remember to write down four bits for each symbol (because the range 0 to 15, that is 0000 to 1111, takes four bits to represent). To convert a binary number to hex, form groups of four bits starting from the right (adding zeros to the final group if it has less than four bits). Then each group of four bits can be separately converted to hex. For example:

10110110111

can be converted to hex by first forming groups of four bits:

0101 1011 0111

(Notice the extra zero added to the group on the far left.) Then each group is converted to a single hex character:

5 B 7
0101 1011 0111

giving 5B7.
This method of converting hex to binary and binary to hex is so simple that it is always to be preferred as a way of writing down a bit pattern. As a single hex character corresponds to four bits and vice versa it only needs a pair of hex characters to represent the contents of a single memory location. For example, the most common explicit use of bit patterns in BBC BASIC is in user-defined characters. A row of eight dots can be represented by a pattern of eight-bits and this pattern is usually written in a VDU 23 statement as a pair of hex digits.
It is well known that in BBC BASIC a hex number is distinguished by writing '&' in front. A feature that is easy to miss from even a careful reading of the User Guide is that "~" can be used to force a value to be printed in hex. The easiest way to input hex numbers is to use the EVAL function, as in:

INPUT N$
N=EVAL("&"+N$)

Unfortunately "~" cannot be used to convert decimal numbers to hex strings as it can only be used in PRINT statements. However, a function to convert decimal to hex can be found in the disassembler in Chapter Eleven.

Bit patterns and logic

The use of bit patterns to represent numbers is in many ways a very sophisticated idea that might be better introduced after the rather simpler topic of using bit patterns in Boolean logic. Boolean logic may be simple but it is much less familiar than arithmetic and for this reason it has been left until a later stage.
Boolean logic involves the manipulation of two values usually called true and false, although in practice they can be any two distinct values. Obviously it is possible to make a bit pattern represent a number of Boolean values as each bit can be interpreted as meaning true or false. Thus the bit pattern 0 l0! could be taken to mean 'false, true, false, true' if we assume that 0 is representing false and 1 is representing true. The fundamental operations of Boo lean logic, AND, OR and NOT, are fairly well known even to non-programmers as they are very similar to their everyday English equivalents. That is x AND y, where x and y are Boolean values (or truth values) is TRUE if, and only if, x and y are both TRUE; x OR y is TRUE if either x or y are true; and NOT x is TRUE if x is FALSE and vice versa. A good way of explaining the action of a logical operator is by a truth table that lists the result of the operation for each possible value of x and y. For example AND may be characterised by:

x y x AND y
0 0 0
0 1 0
1 0 0
1 1 1

You may have noticed that while the idea of using a bit pattern to represent a number of logical values was introduced at the start of the section the logical operators have been introduced in terms of their effect on a pair of single bits. That is, while the result of I AND 0 can be easily worked out to be 0, so far no meaning has been attached to expressions such as 01 l0 AND 1010. There are in fact a number of ways that this can be done but the most common is the so-called bitwise extension to the standard logical operations. A bitwise operation manipulates pairs of bits that occupy the same positions within their respective bit patterns. For example, the bitwise evaluation of 0110 AND 1010 first calculates bit zero of the result by ANDing together the bit zeros of each bit pattern - that is 0 AND 0. Then the second bit of th result is calculated in an analogous manner using the second bit of each bit pattern and so on. This is best visualised as:

0110
AND 1010
0010

Bitwise versions of OR and NOT can be similarly arrived at. For example, the bitwise implementation of 0110 OR 1010 is:

0110
OR 1010
1110

and NOT 0110 is simply obtained by 'inverting' each of the bits in turn giving 1001 as the result.
Bitwise logical operations are particularly useful for carrying out 'bit manipulation', that is independently changing some bits within a bit pattern without altering others. For this reason it is the most common method used to extend the logical operators to bit patterns, but it is important to realise that it is by no means universal - see for example ZX BASIC as implemented on the ZX81 or Spectrum.

BASIC logic

In BBC BASIC TRUE and FALSE are represented by integers, -1 for TRUE and 0 for FALSE. The logical operators are AND, OR, NOT and EOR (EOR stands for Exclusive OR and will be described later). Ifyou use these operators on the values 0 and --I then they behave exactly as you would expect. For example -1 AND 1 is -1 and NOT 0 is -1. However, if you try using them with other integer values you will find that, rather than printing an error message, the BBC Micro will return another integer as a result. For example, if you try PRINT 16 OR 3 you will see the result 19 printed. From the last section you should be able to see that BBC BASIC is in fact implementing its logical operators in a bitwise fashion. In fact the logical operators are applied bit wise to the four bytes that are used to represent an integer. That is, the result of l6 OR 3 is:

00000000 00000000 00000000 00010000
OR 00000000 00000000 00000000 00000011
00000000 00000000 00006000 00010011

which is, of course. the binary representation of 19.
The only complication to this simple bitwise implementation is that an integer is represented using two's complement For example, what is -1 OR 7? The answer is easy as long as you remember or work out the bit pattern used to represent -1 (using two's complement):

-1 = 11111111 11111111 1111111 11111111
7 = 00000000 00000000 00000000 00000111
-1 OR 7 = 11111111 11111111 11111111 11111111

That is -1 OR 7 is simply -1. If you find all of this conversion to two's complement difficult or confusing then the best thing to do is to use hex. For example PRINT ~(&E3 OR &3F) gives the result &FF.
Finally, it is worth pointing out that while TRUE and FALSE are -1 and 0 respectively, the IF statement will treat any non-zero value as TRUE. That is, the IF statement is more accurately described as:

IF numeric expression THEN list 1 ELSE list 2

and 'list 1' will be executed if 'numeric expression' is non-zero and 'list 2' will be executed if 'numeric expression' is zero.

Logic in assembler - EOR

The 6502 performs all of its logical operations as bitwise instructions working on eight-bits at a time. Of course, you can manipulate larger bit patterns by repeating the operations on eight-bits at a time. For example:

AND #&40

will perform a bitwise AND of the current contents of the A register and &40 leaving the result in the A register. The logical operations included in the 6502% instruction set are AND, OR and EOR. Y ou might be puzzled by the absence of a NOT command and the presence of EOR. In practice, there are a number of ways of producing the same effect as a NOT command and one of them is to use EOR. EOR stands for Exclusive OR and its action is best explained by way of a truth table:

x y x EOR y
0 0 0
0 1 1
1 0 1
1 1 0

If you examine this table you will see that x EOR y is true if x or y is true, but not both. This corresponds more closely to the English use of'or' than OR. For example, if you say 'you can have marmalade or jam' you generally mean that the choice is one or the other but not both! EOR can be used to produce the same effect as a NOT instruction. If you want to perform a bitwise NOT on the contents of the A register then use:

EOR #&FF

This works because each bit in the A register is EORed with a '1' bit in the bit pattern and if you look at the truth table you will see that 0 EOR 1 is 1 and 1 EOR 1 is 0 which is exactly what is needed to implement a NOT operation.

Bit manipulation

The need to manipulate and test the value of individual bits within bit patterns is fundamental to many areas of programming, particularly where any direct interaction with the hardware is involved. Using the bitwise logical operators it is easy to set any bit within a bit pattern to zero or one or to change its existing value from 0 to 1 or vice versa.
In particular, you can set any bit or group of bits to zero by ANDingthe bit pattern with another specially constructed bit pattern called a mask. For example, suppose you want to set the first three bits in a bit pattern to zero then you would AND it with a mask consisting of all ones apart from the first three bits. To see how this works examine the following:

value = 10101010
mask = 11110000
result =1010 1000

Notice that the last three bits will always be zero no matter what the last three bits in 'value' are (because 0 or 1 when ANDed with a Oproducesa 0). ln the same way OR can be used to set any bit or group of bits to I and EOR can be used to NOT or 'flip' any bit or group of bits.
To be precise:

(1) To set any group of bits to 1 construct a mask value consisting of zeros in every bit position apart from the bit positions that you want to set to 1. This mask is then ORed with the bit pattern that you want to alter.

(2) To set any group of bits to 0 construct a mask value consisting of ones in every bit position apart from the bit positions that you want to set to 0. This mask is then ANDed with the bit pattern that you want to alter.

(3) To 'flip' any group from their current value construct a mask consisting of zeros in every bit position apart from the bit positions that you want to alter. This mask is then EORed with the bit pattern that you want to alter.
For example, if you want to 'flip' the first three bits of an eight-bit value, the mask you would use would be:

00000111

or &07 in hex. If you EOR &07 with any value you will discover that as required the first three bits are unchanged, but the rest of the value is unchanged. For example, &55 EOR &07 gives the result &52.

Extracting information - USR and shifts

Setting groups of bits to zero without affecting the rest of the bit pattern is often used in conjunction with shift operations to extract information from a bit pattern. A shift operation, as its name suggests, will shift all the bits in a bit pattern one place to the right or the left. For example a right shift of the bit pattern:

10011011

gives

01001100

Notice that as well as shifting all the bits one place to the right we have also 'produced' a zero that has been shifted into bit 7's position and the old value of bit 0 has been 'lost'. Apart from the direction of shift i.e. left or right shift operations can also differ in the value that they shift 'into' the bit pattern and what happens to the bit that is shifted out. Shifting a zero in and losing the bit that is shifted out is called a logical shift.
Using a logical shift and the logical operators it is possible to isolate any group of bits within a bit pattern. For example, a JSR function returns a value that is best considered as a bit pattern made up in the following way:

P |Y |X |A

where P is the contents of the status register, Y is the contents of the Y register, X the contents of the X register and A the contents of the A register. Notice that each register value is composed of eight-bit and hence the [JSR function returns a four byte bit pattern that is interrupted by BBC BASIC as an integer. Suppose that the particular [JSR function that you have written returns its result in the X register and the values in the P, Y and A register are irrelevant. To isolate the byte that comes from the X register from the other three bytes, all that you have to do is to set all of the unwanted bits to zero and then perform eight logical right shifts. That is, first AND the value with:

&0000FF00

and then perform the eight logical shift rights. For example, if the value returned by USR is &B1123486 then the result of ANDing it with the above mask is &00003400 and the result of eight right shifts is &00000034 or just &34.
This method can be used directly in 6502 assembler because the 6502 has both logical operations and logical shifts. However, BBC BASIC doesn't have a shift operation and so it looks as though this method cannot be used. Fortunately this is not the case as there is a correspondence between right shift operations and division by two and left shift operations and multiplication by two. Dividing a number by two and ignoring any fractional part has the same effect as shifting the bit pattern one place to the right. In general BASIC this can be implemented as INT(V/2) where V holds the bit pattern to be shifted to the right. In BBC BASIC a better and faster way is to use the DIV operator which performs integer division and so automatically ignores any fractional part. Thus, to isolate the X register's value in BBC BASIC use:

(V AND &0000FF00) DIV 256

(Dividing by 256 is the same as dividing by 2 eight times, i.e. 256=2^8, and so performs eight right shifts as required.)
Using shifts (implemented as divisions and multiplications in BASIC) and logical operations it is possible to isolate, test and generally alter any bit or group of bits within a bit pattern and this opens up all sorts ofmemorysaving methods of 'packing' data into the smallest possible space. Bit manipulation is a common tool in advanced programming.

Logic functions - predicates

For the final section in the final chapter of this book we return to the subject of program clarity. Sometimes it is necessary to write a very simple IF statement that is complicated by the difficulty of the 'condition' that it tests for. For example, suppose you had written a program that counted the number of letters (as opposed to numbers, spaces and punctuation characters) a string contained. The IF statement that actually does the counting is simple enough in conception:

IF C$ = a letter THEN COUNT COUNT+1

where C$ contains the character being tested. The trouble is that the condition C$ a letter is not BASIC and turning it into valid BASIC obscures its meaning:

IF (C$>="A" AND C$<="Z") OR (C$>="a" AND C$<="z") THEN
COUNT=COUNT+1

The first bracket tests to see if C$ is in the set of upper-case characters and the second tests to see if it is in the set of lower-case characters. Obviously if either of these tests is true then CS is a letter and hence they are connected together using OR.
It is not possible to simplify this 'letter test' condition and so you might come to the conclusion that there is nothing that can be done to improve the clarity of the program - this is not so. A simple idea from logic can be applied with great success in BBC BASIC - the predicate function. A predicate function is, roughly speaking, a function that returns a Boolean value. As BBC BASIC represents TRUE and FALSE by integers there is nothing stopping us from writing functions that return Boolean values. For example the 'letter test' condition can be easily turned into a predicate function :

1000 DEF FNletter(C$)
1010 LOCAL T%
1020 T%=C$>="A" AND C$<="Z")
1030 T%=T% OR (C$>="a" AND C$<="Z"
1040 =T%

Notice the way that within the function the complex condition can be worked out in stages so that it can be understood in the same way this is always a good idea. Once this function has been defined the IF statement can now be written:

IF FNletter(C$) THEN COUNT=COUNT+l

or as

IF FNletter(C$)=TRUE THEN COUNT=COUNT+1

depending on which you find the clearest expression of your intentions.

Theory

If you really want to be confident about computing, there is a lot more theory to learn about binary numbers, Boolean logic, etc. Most of it is quite straightforward as long as you keep askingyourselfthe question 'what does this theory really mean in terms of bit patterns and operations'. The best way of ensuring this practical outlook is to learn theory as and when you need it in your programming. A great deal of this book has been about increasing your awareness of the possibilities rather than getting involved in a great deal of detail. In computing, finding out what you don't know and what you need to know is a substantial part of the battle!


Next     Top