TIGCC Programming Lessons

Lesson 8: Bit Manipulation

Step 5 - The Other Bitwise Operations: OR, XOR, and NOT

There are several other kinds of bitwise operations, so I hope you liked AND, because here come even more. Hopefully, now that you are acquainted with the most common bitwise operator, the other ones will be easier to learn and understand.

The next bitwise operator we need to discuss is the bitwise OR. Bitwise OR is very similar to bitwise AND, but instead of returning true only when both bits are true, bitwise OR returns true if either bit is true. Let's look a small example so you can see how it works in general:

   0b0011101001011011
OR 0b1100010111010010
   ------------------
   0b1111111111011011

I know the example is very abstract, but it is useful for demonstrating the logic side of the operation. Remember that bitwise means 'bit by bit'. So we perform the test bit by bit on every bit in our source and destination, and the result is the bits strung together.

The most common use you will have for bitwise OR will be masked sprites, but I don't want to delve into that right now, because it would take a long time to explain the concept. We'll come back to bitwise OR later on. Just make sure you understand how the bits get changed during an OR operation. You won't have use of this until later, but the bitwise OR operation in C is represented by the single pipe character, |. So, 0x3A5B | 0xC5B2 would perform the OR operation we did in the example.

The next bitwise operation is called bitwise XOR, also known as eXclusive OR. Remember that OR sets a bit in the result to be true if either bit is set. Well, exclusive or sets a bit in the result if either one of the bits are set, but not both. Let's look at a quick example:

    0b1001110110001001
XOR 0b0001111001101110
    ------------------
    0b1000001111100111

This is again very abstract, but it's important to understand how the bitwise operators work. The most common use you will probably have for XOR is unmasked sprites. We have already used unmasked sprites, so you already know how they work a little. Now you can see how they work. The XOR operation takes the pixels on the screen, and the pixels from your sprite. The result is what we put on the screen.. Knowing this, we can see exactly how unmasked sprites work, and why drawing them and erasing them is the same.

If we have an area on the screen which is blank, the pixels will be all zeros, so when we XOR the sprite to the blank screen, the entire area of the sprite will be drawn on the screen, because the 1's on the sprite will be the only 1's in our XOR operation, making them the exclusive bits that will be set in the result. And, when we go to erase our sprite, the sprite's 1's will interfere with the 1's from the original sprite we drew on the screen, setting all the bits back to zero. This also shows you why unmasked sprites are only good when you don't need background, and why they are the simpler form of sprites. The bitwise XOR operation in C is represented by the single caret ^. So, to perform the operation we did in the example in C, we would do this: 0x9D89 ^ 0x1E6E.

The last bitwise operation we should take a look at is bitwise NOT. This last operation simply sets all the bits as the inverse of whatever they are. All the 1's become 0's and all the 0's become 1's. This is useful in many circumstances. When we talk about masked sprites, we will see how using bitwise not makes for an easy way to define inverse bit masks, but since we aren't talking about that yet, let's go into a topic we do have use for: the _rowread() function.

Remember in our last example, we used _rowread() to read a row of the keyboard. We needed to create an inverse mask of the keyboard row we wanted to read. To do that, we would take the row we wanted, and subtract it from the value 0xFFFF, the highest possible short integer value. This method is a little bulky though. It requires some extra work on our part, and why should we have to do that? We are using a computer after all. Shouldn't it take care of this arithmetic stuff for us? Well, it can. Remember that bitwise NOT sets all the bits to its inverse, an an inverse bit mask is just what we need.

The ESC row on the TI-89 is row 7, corresponding to the 6th bit in the matrix. So, the 6th bit would be represented by the hex number 0x0040. But that's not the number we need to use for _rowread(), because _rowread() requires an inverse mask, and we only have a mask. But we can use bitwise NOT to our advantage here. Instead of subtracting 0x0040 from 0xFFFF, we can just use the bitwise NOT of 0x0040. Bitwise NOT in C is represented by the ~ tilde character. Let's take a look at an example:

enum KeyboardRows89 {ESCROW = ~0x0040, ARROWROW = ~0x0001};

There are probably better uses for bitwise NOT, but it does save us a step or two in our programming.

Step 6 - Bit Shifting

We have almost covered all the topics related to bit manipulation, but there is still one very important topic that remains. Bit shifting. Bit shifting is the process of moving the places of the bits one or more places. That explanation doesn't really tell you much about bit shifting though, so let's try an example instead.

Shift Right 2 places: 0b0111001101110110 = 0b0001110011011101

Did you see what happened there? Probably not, so let's go over it. I shifted the bit places two positions to the right. This means the 2 right most bits (the bits on the right end, or the least significant bits) have been shifted out completely. They are gone. All the bits that were to the left of those initial right two bits are now two bit positions to the right. And in the first two bit positions, we have 0's. This is what happens when we shift bits. If we shift right, the lowest bits get lost, and the upper bits get new zeros. When we shift left, just the oppose, the lowest bits get new zero's and the upper bits get lost.

Now, you may be asking yourself, what is the purpose of this bit manipulation? Well, there are many reasons for shifting bits, but as you probably have guessed by now, it all comes down to efficiency. Let's say we needed to test for a certain position on a map grid. The grid we are checking is at position (9,5), where (0,0) is the upper left hand corner of the screen. Each of the areas on the map grid contains either a 1 meaning it is occupied, or a 0 meaning it is not occupied. We want to test if this position on the map is occupied. So, how can we use bit shifting to help us in this endeavor? Easy; first we can grab the row we are looking for (which will probably be part of an array), so, since we are looking at the 5th row, let's assume we have a variable map[] which contains all the rows of the map. Inside each map[] element is an integer representing the positions on that row. We are looking for the 9th position. So, if we start with the bit mask 0x8000 (or in binary 0b1000000000000000, i.e. the first position inside the row), then we need to check the 9th position, which would be 0b000000001000000000000000 or 0x0080. Now, you might say, why don't we just start with 0x0080. Well, we won't know ahead of time which position on the map we want to check. If we are writing a program which can check any position on the map, we have to take the position we want to check (which we won't know until we run the program), and check it against the map (and we may have multiple maps, but we'll keep it simple here and assume we only have a single map). So, if we have our row, which we will assume to have the bits set as 0b1111 1000 0001 1101, or in hex 0xF81C, and we want to check position 9, which is 0x0080, we can compare our two numbers using the AND operator. Remember AND will return true if the bit of our mask is set in the result. But remember that we don't have a proper mask yet, because we don't know the value until the program is run. So, this is where our bit shifting comes in. We will start with the mask 0x8000, and shift it down to the correct position, the ninth bit. So, we will shift right 8 positions, to turn 0x8000 into 0x0080. Since we start numbering at 0, we will usually not have to worry about subtracting one from our shift, because 9 will actually be 8, since we start counting at 0. This makes things nice and easy. Let's look at how that would be done in code.

unsigned int mask = 0x8000;
unsigned int mapRow = 0xF81C;	// this would be a function argument in real code
short int position = 8;	// find the 9th position. This would be an argument too...

// shift the mask right by the position
mask = mask >> position;

if (mask & mapRow) {
	// position is occupied...
}

The right shift operator is >> double greater-than, and << double less-than for left shift. The shift goes in the direction the "arrows are pointing". I know they don't look much like arrows, but just follow the point, or reread this lesson if you forget. Or better yet, read the TIGCC docs about C operators, cause it covers this too.

I think you can see how useful this would be in a game for testing positions. It has other uses too, but this is a very common use.

Step 7 - Bit Manipulation in Action

Our last program went a long way towards working something real with bit manipulation (among the other concepts we've learned), but we can go even further and add background to our little program now that we have added bit shifting.

So, start TIGCC. Create a new project and a new C Source File called bitmanip. Modify the file so that it looks like this:

bitmanip.c

#include <tigcclib.h>
#include "bitmanip.h"

inline void drawBlock(POSITION pos) {
    Sprite8(pos.x*BLOCK_WIDTH,pos.y*BLOCK_HEIGHT,BLOCK_HEIGHT,block,LCD_MEM,SPRT_XOR);
}

inline void eraseBlock(POSITION pos) {
    drawBlock(pos);
}

inline void moveBlock(POSITION oldPosition, POSITION newPosition) {
    eraseBlock(oldPosition);
    drawBlock(newPosition);
}

void move(POSITION *pos, short int direction) {
    POSITION oldPosition = *pos;

    switch (direction) {
        case UP:
            // if we can move up, then do so
            if (!isWall((POSITION){pos->x,pos->y-1})) {
                pos->y--;
                moveBlock(oldPosition,*pos);
            }
            break;
        case DOWN:
            // if we can move down, then do so
            if (!isWall((POSITION){pos->x,pos->y+1})) {
                pos->y++;
                moveBlock(oldPosition,*pos);
            }
            break;
        case LEFT:
            // if we can move left, then do so
            if (!isWall((POSITION){pos->x-1,pos->y})) {
                pos->x--;
                moveBlock(oldPosition,*pos);
            }
            break;
        case RIGHT:
            // if we can move right, then do so
            if (!isWall((POSITION){pos->x+1,pos->y})) {
                pos->x++;
                moveBlock(oldPosition,*pos);
            }
            break;
    }
}

void getKeyMasks(short int *keys, short int calc) {
    // find the correct key masks based on which calculator we have
    if (calc == 0) {        // do we have a TI-89
        keys[0] = 0x0001;   // bit 0
        keys[1] = 0x0004;   // bit 2
        keys[2] = 0x0002;   // bit 1
        keys[3] = 0x0008;   // bit 3
    } else {            // then we must have a TI-92+
        keys[0] = 0x0020;   // bit 5
        keys[1] = 0x0080;   // bit 7
        keys[2] = 0x0010;   // bit 4
        keys[3] = 0x0040;   // bit 6
    }
}

// slow the program down
void delay(void) {
    short int loop = 1800, randNum;

    // generate random numbers to slow down the program...
    while (loop-- > 0) {
        randNum = rand() % loop;
    }
}

short int quit(short int calc) {
    if (calc == 0) {    // test for TI-89 ESC key
        if (_rowread(TI89_ESCROW) & TI89_ESCKEY) {
            return 1;
        }
    } else {        // test for TI-92+ ESC key
        if (_rowread(TI92_ESCROW) & TI92_ESCKEY) {
            return 1;
        }
    }

    return 0;
}

short int isWall(POSITION pos) {
    unsigned long int mask = 0x80000 >> pos.x, position = map[pos.y];

    // if mask and position collide, we hit a wall
    if (mask & position) {
        return 1;
    }

    // otherwise, we didn't
    return 0;
}

void drawMap(void) {
    short int row, column;
    unsigned long int mask, position;

    // clear the screen before drawing
    ClrScr();

    // loop through the map array
    for (row = 0; row < MAP_ROWS; row++) {
        // get the positions for this row
        position = map[row];

        // reset the bit mask
        mask = 0x100000;

        // loop through the column to see where in the row we need to draw blocks
        for (column = 0; column < MAP_COLUMNS; column++) {
            // shift the bit mask
            mask >>= 1;

            // check the position, if set, draw the block
            if (position & mask) {
                drawBlock((POSITION){column,row});
            }
        }
    }
}

void _main(void) {
    short int keys[4];
    short int calc = CALCULATOR, key;
    INT_HANDLER interrupt1 = GetIntVec(AUTO_INT_1);
    INT_HANDLER interrupt5 = GetIntVec(AUTO_INT_5);
    POSITION pos = {2,2};

    // replace auto-interrupts 1 and 5 so they don't interfere with keyboard reading
    SetIntVec(AUTO_INT_1,DUMMY_HANDLER);
    SetIntVec(AUTO_INT_5,DUMMY_HANDLER);

    // get the correct key masks based on which calculator we have. The TI-89
    // has a different keyboard mapping than the TI-92+
    getKeyMasks(keys,calc);

    // draw the map on the screen
    drawMap();

    // draw the block on the screen at our initial position
    drawBlock(pos);

    // until the user presses ESC
    while (!quit(calc)) {
        key = _rowread(ARROW_ROW);

        // check for UP arrow
        if (key & keys[UP]) {
            move(&pos,UP);
        }

        // check for LEFT arrow
        if (key & keys[LEFT]) {
            move(&pos,LEFT);
        }

        // check for DOWN arrow
        if (key & keys[DOWN]) {
            move(&pos,DOWN);
        }

        // check for RIGHT arrow
        if (key & keys[RIGHT]) {
            move(&pos,RIGHT);
        }

        // slow the program down
        delay();
    }

    // restore auto-interrupts
    SetIntVec(AUTO_INT_1,interrupt1);
    SetIntVec(AUTO_INT_5,interrupt5);
}

Now create a new C Header File named bitmanip. Modify the file so that it looks like this:

bitmanip.h

#ifndef _BITMANIP_H
#define _BITMANIP_H

/* Constants */
enum MapDimensions {MAP_ROWS = 19, MAP_COLUMNS = 20};
enum BlockConstants {BLOCK_HEIGHT = 5, BLOCK_WIDTH = 8};

enum ArrowKeys {UP,DOWN,LEFT,RIGHT};
enum KeyMatrix {TI89_ESCROW = ~0x0040, TI89_ESCKEY = 0x0001,
        TI92_ESCROW = ~0x0100, TI92_ESCKEY = 0x0040,
        ARROW_ROW = ~0x0001};

/* Structure Definitions */

typedef struct {
    unsigned short int x : 8, y : 8;
} POSITION;

/* Sprite Definitions */

static unsigned long int map[] = {0xFFFFF,0x80001,0x80001,0x80001,0x80401,0x80401,0x80401,0x80401,
                 0x80401,0x87FC1,0x80401,0x80401,0x80401,0x80401,0x80401,0x80001,
                 0x80001,0x80001,0xFFFFF};

static unsigned char block[] = {0xFF,0xFF,0xFF,0xFF,0xFF};

/* Function Proto-types */

inline void drawBlock(POSITION);
inline void eraseBlock(POSITION);
inline void moveBlock(POSITION, POSITION);

void move(POSITION *, short int);

void getKeyMasks(short int *, short int);
void delay(void);
short int quit(short int);

short int isWall(POSITION);
void drawMap(void);

void _main(void);

#endif

Step 7a - Compile and Run the Program

Save the files and build the project. Send the program to TiEmu and run it. It will look something like this:

Step 7b - Program Analysis

This program is very similar to the last one, but we have added a new feature, the background map. This let's us move a sprite around the screen, but keep track of the background area so we know where we can move the sprite, and where we cannot. This would be good for any kind of game that moved a character along a screen, especially if they have some background obstacles the character cannot pass through (mountains, rivers, oceans, etc.)

Since this program is so similar to the last program, we will only work on analyzing the differences in the programs. Let's start in the _main() method, as always.

// draw the map on the screen
drawMap();

The first change is that we have to actually draw the map background on the screen as part of the initialization process. The drawMap() function is the first place we use bit shifting.

void drawMap(void) {
	short int row, column;
	unsigned long int mask, position;

	// clear the screen before drawing
	ClrScr();
	
	// loop through the map array
	for (row = 0; row < MAP_ROWS; row++) {
		// get the positions for this row
		position = map[row];
		
		// reset the bit mask
		mask = 0x100000;
		
		// loop through the column to see where in the row we need to draw blocks
		for (column = 0; column < MAP_COLUMNS; column++) {
			// shift the bit mask
			mask >>= 1;
			
			// check the position, if set, draw the block
			if (position & mask) {
				drawBlock((POSITION){column,row});
			}
		}
	}
}

Okay, the drawMap() function is not too difficult, but it uses some tricks that may not seem so obvious, until you see them in actual code. The draw map uses two counters to loop through all the rows and columns (row x column = map array). Then of course, we have our bit mask and the position. The first thing we do in the outer loop is to grab the position, which is the map row. The mask represents the column position. Since the mask will be shifting before the first check, we set the initial mask to one bit left of the first position. We could have done the shifting after we check the position, it's the same either way. The >>= operator is just like the += or -= or any other ?= operators, it performs the left operator, then assigns the result back to the left side variable. So, mask >>= 1 will shift our bit mask 1 position to the right.

Finally, if our bit mask (properly shifted) and our position (map row) AND together to produce a TRUE result, we draw a block on the screen at the current position. The only odd thing about this is our new use of the cast operator. Remember that C can cast almost anything to anything else. In this case, we want have our two integers for our x and y positions, but the drawBlock() function takes a POSITION structure. So, to get the integer variables into a structure, we can cast them into a structure by using the type cast operator. It's just the same as initializing a structure, but we use the cast operator in front of it. So (POSITION){column,row} will create a POSITION structure on the fly using the data from the column and row variables for the x and y member variables, respectively.

The last difference in the program is in the move() function. Since we have to check to see if we hit walls now, we had to make some minor updates to the program, naturally.

void move(POSITION *pos, short int direction) {
	POSITION oldPosition = *pos;
	
	switch (direction) {
		case UP:
			// if we can move up, then do so
			if (!isWall((POSITION){pos->x,pos->y-1})) {
				pos->y--;
				moveBlock(oldPosition,*pos);
			}
			break;
		case DOWN:
			// if we can move down, then do so
			if (!isWall((POSITION){pos->x,pos->y+1})) {
				pos->y++;
				moveBlock(oldPosition,*pos);
			}
			break;
		case LEFT:
			// if we can move left, then do so
			if (!isWall((POSITION){pos->x-1,pos->y})) {
				pos->x--;
				moveBlock(oldPosition,*pos);
			}
			break;
		case RIGHT:
			// if we can move right, then do so
			if (!isWall((POSITION){pos->x+1,pos->y})) {
				pos->x++;
				moveBlock(oldPosition,*pos);
			}
			break;
	}
}

The function is very similar to the old function, but instead of checking the boundaries of the screen which we did in the old version, we check to see if we hit any walls. Normally, we would have to check for screen boundaries, too, but our particular map for this program has a surrounding barrier on all sides, so we only need to make sure it didn't hit a wall. To do that, we use the isWall() function, which returns 1 (true) if we hit a wall, or 0 (false) if we didn't hit a wall. If the new position will intersect a wall, we don't change the position at all, but if it won't, we change the position and then move the block sprite.

short int isWall(POSITION pos) {
	unsigned long int mask = 0x80000 >> pos.x, position = map[pos.y];

	// if mask and position collide, we hit a wall
	if (mask & position) {
		return 1;
	}
	
	// otherwise, we didn't
	return 0;
}

Okay, the isWall() function tells us is a position is in a wall or not. Our mask variable is our column, and our position is the map row. Since we are checking against the position structure we are given, the map row will be the node in the map array of the Yth position, and the column we need to check will be the bit shift x from our starting position 0x80000. If our mask AND our position intersect, then we hit a wall, so we should return 1 (true), otherwise we return 0 (false).

enum KeyMatrix {TI89_ESCROW = ~0x0040, TI89_ESCKEY = 0x0001,
		TI92_ESCROW = ~0x0100, TI92_ESCKEY = 0x0040,
		ARROW_ROW = ~0x0001};

The last thing I want to show you is our use of the bitwise NOT operator to do the inverted bit masks for our keyboard matrix rows for use with the _rowread() function. The ESC row, which is the 7th row (bit 6) needs to be inverted so we can use it with the _rowread() function. We use the ~ bitwise NOT operator to have it perform the inversion for us. This is just one of the little nice things that C takes care of for us.

Step 8 - Conclusion

Bit operations are one of the most powerful operations in C. They are very useful in checking masks and often provide speed bonuses.

Lesson 8: Bit Manipulation
Questions or Comments? Feel free to contact us.