Kitchen Sync

Making the Most of What You’ve Got

This month’s column was inspired by two other articles appearing in the May/June issue of SYNC. In the first, David Lubar told of his experiences in using the NOT operator of Sinclair Basic. In the second article, Bill Eckel introduced a game called Black Hole and presented a version which he “almost” got to fit in the ZX80’s 1K available memory. These two articles started us thinking, and we decided that the Black Hole game might be the perfect medium for demonstrating both the usefulness of AND, OR, and NOT, as well as a method for packing as much possible into what might be considered a “tiny” amount of memory.

But first, a short discourse on logical operations.

As you have heard over and over again, computers only understand “ones and zeros.” While this is true, a computer’s life is not quite that dull. Since you cannot do much with just 0 and 1, bunches of 0’s and 1’s (called bits) are grouped together into larger sets, the most common of which are bytes.

The normal arithmetic operators you are accustomed to (+,-,*,/) take integers (which in the ZX80 are represented as groups of 16 bits) and add, subtract, multiply, or divide them as numbers. Likewise, AND, OR, and NOT take integers and combine them in various ways. In the instance of these operators (called logical, or Boolean, operators), however, it is more useful to think of the integer as the group of 16 individual bits rather than as a whole.

The operation “A AND B” is the collection of 16 bits that are the result of each bit of A “ANDed” with each bit of B. These logical operators are often shown in the form of tables as follows:

AND | 0  1        OR | 0  1
----+------       ---+------
  0 | 0  0         0 | 0  1
  1 | 0  1         1 | 1  1

        NOT |
        ----+----
          0 | 1
          1 | 0

As you can see, AND returns a 1 when both bits are 1; OR returns a 1 when either bit is equal to 1. NOT inverts the bit value (returns 1 if given 0, 0 if given 1).

There is one more Boolean operator you should know about, called the EXCLUSIVE OR, or XOR for short. Here is what it looks like:

XOR | 0  1
----+------
  0 | 0  1
  1 | 1  0

While OR returns a 1 if either or both bits are 1, XOR returns a 1 only if either, but not both, are 1. In other words, XOR returns a 1 if the bits are different. While XOR is not in Sinclair Basic, it can easily be coded as:

(A OR B) AND NOT (A AND B)

Groups of bits are combined to create larger values much the same way as decimal digits are combined in base 10. In base 10, the digit positions represent increasing powers of 10 from right to left (1, 10, 100, and so on). The value of the number is the sum of the digit values. Therefore, “24” represents 2 tens and 4 ones, added together, which is 24.

Binary works the same way. Bit positions represent increasing powers of 2 from right to left (1, 2, 4, 8, 16, etc.). Hence, “11000” represents 1 sixteen, 1 eight, and no fours, twos, or ones. Adding these together, we also end up with 24.

Specific bits can be turned on or off using the AND and OR operators of Sinclair Basic. To turn a bit on in an integer, you can “OR” it with a word that has just that bit (or bits) turned on. To turn a bit off, “AND” the word with one in which every bit except the one you want is turned on.

To see how all this works, try the test program in Listing 1. It asks for two numbers, A and B. Enter these in decimal (as normal numbers). You should keep running the program until you have some understanding of what is going on.

The main program itself is rather simple. The subroutine at line 1000 probably deserves some discussion, though.

Lines 1000-1010 test the leftmost bit (the sign bit, which indicates if the integer is a positive or a negative number) and print out a 0 or 1 depending on that bit’s value. The remaining bits can be tested by bit position, using a loop that steps from 14 down to zero. (The leftmost bit could not be tested in this loop because of the way the Sinclair handles numeric overflow.) Lines 1020-1030 and 1060-1070 set up a FOR-NEXT loop that counts down from 14 to 0. Lines 1040-1050 test the single bit 2**Y1 (Y1 going from 14 to 0 — 2**0 = 1)

As you can see, AND can also be used to test specific bits. If you “AND” the integer you want to test with another in which only the bits you want to test are equal to 1 (called a “mask” by programming types) the integer you end up with will be zero if none of the tested bits were set, and non-zero if any were. The resulting integer will have a 1 in each bit position that was equal to 1 in both the tested integer and the mask.

Now, back to Black Hole. If you remember, the problem was that the program still did not fit into a 1K Sinclair, which kept most Sinclair owners from playing the game. Not being very happy about being deprived of some fun with our ZX80s, we tried to do something about that.

Let us take a good look at the game itself. The game board, called the “galaxy,” has nine positions, each of which can be either a “star” or a “black hole.” The most obvious way to store the galaxy is with an array of nine integers, each representing a position in the galaxy. Since there are only 9 positions and since each position can only be in one of two states (star or hole), the entire galaxy can be represented in a single integer, with 9 of the bit positions representing the nine positions in the galaxy. This type of representation saves memory in two ways—the game board itself takes less memory, and, more importantly, the entire galaxy can be updated all at once, rather than by twiddling each position separately.

The representation we chose uses bits 1-9 (bit numbers go from 15 on the left to 0 on the right) to represent positions 1-9. So the bit that represents the state of position ‘n’ is 2**n. The remaining bits are zeros. Since the initial state of the board is all holes (0) with a star (1) in position 5, we can set the whole galaxy to the initial state with the statement LET GALAXY=2**5 (line 10). Compare this with lines 10-20 in the original program.

Lines 35-70 simply print out the galaxy.

Line 75 tests to see if the value of GALAXY is 0. GALAXY being equal to 0 means that the collection of 16 bits that represents the value of GALAXY is all zeros. So GALAXY=0 means that each position in the galaxy is a black hole—the definition of losing.

Line 95 tests to see if the value of GALAXY is 990. This value is represented by a pattern of bits where bits 1, 2, 3, 4, 6, 7, 8, and 9 are 1’s and bit 5 along with the unused bits (0 and 10-15) are zeros. You can verify this with the binary calculator above. This pattern is the definition of a win.

Line 130 tests to see if the selected position is valid. Since you can only shoot at stars and not at black holes, the input would be invalid, if the selected bit position were a zero.

Lines 135 and 202-219 are the most cryptic part of the program. Looking back at Eckel’s original Black Hole article, we see that for each possible move, there is a pattern of positions that must be inverted (a star becomes a hole, a hole a star). If the state of the galaxy can be represented in a single integer, then certainly each of these patterns can be too. Line 135 selects the appropriate subroutine to set the value of CHANGE to represent the required pattern.

For example, if you look at the pattern of positions that must be inverted if you choose to shoot at star 5, you can see that positions 2, 4, 5, 6, and 8 must be inverted. The others must stay the same. This can be represented by setting the corresponding bit for each position that must be inverted. Therefore, the required value (mask) would have bits 2, 4, 5, 6, and 8 set with the other bits cleared. This is what is done in line 210. You can use the binary calculator program to verify that 372 has the correct pattern of zeros and ones.

While OR can be used to set certain bits to ones and AND can be used to set certain bits to zeros, XOR can be used to invert certain bits without knowing their original value. This is done in line 140.

As you can see, by carefully selecting the representation of the data of your program, you can squeeze more into—and get more out of—the 1K memory of the Sinclair.

Listing 1.

  10 PRINT "ENTER A"
  20 INPUT A
  30 PRINT "ENTER B"
  40 INPUT B
  50 CLS
  60 PRINT "A",
  70 LET Z=A
  80 GO SUB 1000
  90 PRINT "B",
 100 LET Z=B
 110 GO SUB 1000
 120 PRINT "##NOT A",
 130 LET Z= NOT A
 140 GO SUB 1000
 150 PRINT "#NOT B",
 160 LET Z= NOT B
 170 GO SUB 1000
 180 PRINT "A AND B",
 190 LET Z=A AND B
 200 GO SUB 1000
 210 PRINT "A OR B",
 220 LET Z=A OR B
 230 GO SUB 1000
 240 PRINT "A XOR B",
 250 LET Z=(A OR B) AND NOT
     (A AND B)
 260 GO SUB 1000
 270 PRINT
 280 PRINT
 290 GO TO 10
1000 IF Z<0 THEN PRINT "1";
1010 IF NOT Z<0 THEN
     PRINT "0";
1020 LET Y1=14
1030 FOR Y=1 TO 15
1040 IF Z AND 2**Y1 THEN
     PRINT "1";
1050 IF (Z AND 2**Y1)=0
     THEN PRINT "0";
1060 LET Y1=Y1-1
1070 NEXT Y
1080 PRINT "#";Z
1090 RETURN

 10 LET GALAXY=2**5
 15 CLS
 20 PRINT "BLACK HOLE"
 25 PRINT
 30 PRINT
 35 FOR I=0 TO 2
 40 FOR J=1 TO 3
 45 IF (GALAXY AND (2**(3*
    I+J)))=0 THEN PRINT "O ";
 50 IF GALAXY AND (2**(3*
    I+J)) THEN PRINT "* ";
 55 NEXT J
 60 PRINT ,3*I+1;" ";3*I+2;
    " "; 3*I+3
 65 PRINT
 70 NEXT I
 75 IF NOT GALAXY=0 THEN GO
    TO 95
 80 PRINT "YOU BLEW IT"
 85 PRINT "YOU ARE LOST IN
    SPACE FOREVER"
 90 STOP
 95 IF NOT GALAXY=990 THEN
    GO TO 115
100 PRINT "CONGRATULATIONS"
105 PRINT "YOU FOUND THE
    BLACK HOLE"
110 STOP
115 PRINT "WHICH STAR?"
120 INPUT STAR
125 IF STAR<1 OR STAR>9 THEN
    GO TO 120
130 IF (GALAXY AND 2**STAR)
    =0 THEN GO TO 120
135 GO SUB 2*STAR+200
140 LET GALAXY=(GALAXY OR
    CHANGE) AND NOT (GALAXY
    AND CHANGE)
145 GO TO 15
202 LET CHANGE=54
203 RETURN
204 LET CHANGE=14
205 RETURN
206 LET CHANGE=108
207 RETURN
208 LET CHANGE=146
209 RETURN
210 LET CHANGE=372
211 RETURN
212 LET CHANGE=584
213 RETURN
214 LET CHANGE=432
215 RETURN
216 LET CHANGE=896
217 RETURN
218 LET CHANGE=864
219 RETURN