Appendix A

Number systems

 

Bases

Fixed Point

Operating on bits

 

Bases

 

Most of you can count to 9.  If so, you probably realize there are in fact 10 unique digits you will come across in this endeavor.  Oddly enough, the numbering system we use on a daily basis is called: base 10.

 

First let us review a few of the details about base 10 that you should already know.

 

1)     10 =     1 * 10

2)     100 =   1 * 10²

3)     1000 = 1 * 10³

 

This ringing any bells? 

 

Unfortunately for us, computers do not use the same numbering system we do.  The reason for this is a simple one.  They only know 2 digits.  Why is this unfortunate for us?

 

It turns out that 90 percent of the time we can ignore the fact that computers use Base 2 because the compilers and tools we use automatically convert our numbers for us.  But, sometimes an understanding of the computer numbering system is crucial to coding.

 

If you do not already know, the base two system is often referred to as Binary.  It consist of the two digits 0 and 1.

 

The binary system works much in the same way as does our own decimal system with the exception that it has fewer digits.  For instance:

 

1)     10      = 1 * 2     = 2

2)     100    = 1 * 2²       = 4

3)     1000   = 1* 2³        = 8

 

As you can probably already tell, it takes a lot more space to write out binary then it does to write decimal.  To combat this, a new base was developed that made numbers easier to handle.  That numbering system is base 16; often referred to as Hexadecimal or Hex.

 

Base 16 means it has 16 unique digits:  0-9 and A-F.  The reason this system is so useful is because conversion from base 16 to base 2 is a rapid and pleasant experience.

 

Here are a few examples of conversions from base 16 to base 2. 

 

 

 

 

Hex	Binary
0	0000
1	0001
2	0010
3	0011
4	0100
5	0101
6	0110
7	0111
8	1000
9	1001
A	1010
B	1011
C	1100
D	1101
E	1110
F	1111

 

Hex	Binary
10	0001 0000
11	0001 0001
12	0001 0010
13	0001 0011
14	0001 0100
15	0001 0101
16	0001 0110
17	0001 0111
18	0001 1000
19	0001 1001
1A	0001 1010
1B	0001 1011
1C	0001 1100
1D	0001 1101
1E	0001 1110
1F	0001 1111

  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

As you can see, there is a direct correlation between the digits of the hex and the 4 bit groupings of binary.

 

Why this is useful has to do with the fact that the computer stores everything in binary.  Sometimes it is useful to be able to work with the bits and since binary is too cumbersome hex is where you go.

 

Say, for instance, you wanted to know the largest number you can fit in a 32 bit unsigned int.  Well that would mean all the bits are set and since there are 8 groups of 4 bits in 32 bits that would mean your number would be FFFF FFFF.   That is much easier to remember than 4,294,967,295 which is that same number in decimal.

 

Also since memory architecture and ram location is aligned based on bits of the address bus the memory addresses generally look better in hex then they do in binary.  It is much easier to recall that the GBA video memory begins at 6000000 hex than 100,663,296 decimal although you could use either one.

 

In C, all numbers are decimal unless you explicitly tell the compiler to use hex.  The way you do this is you add an 0x in front of the number.  0x10 is hex where as 10 would be decimal.

 

To convert from decimal to hex or binary is somewhat of a pain and either involves repeated division or summation.  If you find you need to do this, then simply open windows calculator and switch to scientific mode.  If you really want to know how to do it by hand then:

 

Hex to decimal

 

0xFA123 = 15 * 16⁴ + 10 * 16³ + 1*16² + 2*16 + 3 = 958,755

(recall from above that F = 15 and A = 10)

 

Binary is the same but you use 2 to the power of the place instead of 16.

 

To convert from decimal, repeatedly divide by the base.  The remainder becomes the digit in the new base and then you continue.

 

Decimal to binary

 

27

 

27 / 2 = 13 with a remainder of 1

13 / 2 =  6 with a remainder of 1

6 / 2 =    3 with a remainder of 0

3 / 2 =    1 with a remainder of 1

1 / 2 =    0 with a remainder of 1

 

The binary is the digits of the remainder read from bottom (1 / 2) to top (27 / 2) and is equal to 11011.

 

Fixed Point

 

The normal method for representing a fractional number is through the use of floating point numbers.  A floating point number as defined by computer standards has the following characteristics:

 

 

One bit of the floating number is reserved for sign while 23 hold the data of the number.  The last 8 make up the exponent so to calculate the number looking only at the bits you would do the following.

 

First label the 23 bits that make up the data as the mantissa.  The value stored in the float would be:

 

Mantissa * 2 ^{(exponent – bias)}

 

The bias is simply one half of the maximum exponent, minus 1.  So in the case of an 8 bit exponent, the max is 256 so one half of that is 128, minus 1 and you have 127.  This allows both signed and unsigned exponents.

 

While a 32 bit float can represent very large or very small numbers, it actually has much less precision then the equivalently sized integer.  Floats and doubles have become a mainstay in computer graphics over the years as processors floating point hardware catches up to such a degree that floats are sometimes quicker than integer math.  Nearly all 3D graphics are accomplished through the use of float and double data types. 

 

Is float for us?  The GBA does not even support the divide operation without using software emulation, let alone floating point math.  Although it is quite possible to do floating point operations on the GBA, these procedures will be carried out by software; the performance is barely tolerable for generating look up tables, let alone for use in real time.

 

So the issue becomes: How do we get fractional data without floating point?  Turns out it is simpler then you might think.  Instead of setting aside an area of our data type to represent the exponent and another to represent the mantissa we will instead split our data type in two.  One part will represent the integer portion and one will represent the fractional part.

 

How much for each, you might ask?  It depends on the application.  If you are using it to get a bit finer control of object placement on the screen then 24 bits integer and 8 bits fraction general work best.  If it is a Sin or Cos look up table where you know the maximum value is 1 and minimum is -1 then you may assign all but 2 bits to the fractional part.

 

Generally you will see the form of fixed point numbers written as:

 

24.8   = 24 bits integer 8 bits fraction

16.16 = 16 bits integer 16 bits fraction

8.8     = 8 bits integer 8 bits fraction

 

To convert an integer to fixed you shift the number left the same number of places that you would like to use as your fractional part.

 

int a = 10;

 

a = a << 8;

 

a is now a 24.8 fixed point number.  The last 8 bits are now used to store fractional changes in a.  Those changes can be in 1/2⁸ or 1/256 increments.

 

The nice thing about fixed point numbers is that addition and subtraction work the same as always.

 

An 8.8 fixed number plus an 8.8 fixed number will be an 8.8 fixed number (ignoring any carryover).

 

But multiplication and division are slightly different.  Just like in decimal where the decimal shifts during multiplication and division, so does it shift for fixed point.

 

For example:

 

0.1 * 0.1 = 0.01

 

You will notice that the decimal place has shifted to the left during multiplication.  What this means for fixed point is that, if you multiply a 24.8 by a 24.8 you will end up with a 16.16.

 

This leads to two major problems.  First, your code, normally is set up to handle one or two types of fixed point at most, will not like this new format of fixed point.  Second, where you had 24 bits of precision before, you now only have 16; you have to worry about your result not fitting into the new format.

 

To solve the first problem, we simply shift the data back to the right by enough to place it back in the proper format.

 

For instance if we have a 16.16 that we need as a 24.8 we simply shift right by 8.  Again keep in mind you will loose those top 8 bits during this operation.  One way to avoid this would be to shift both numbers prior to the multiply.

 

(24.8 >> 4)    *   (24.8 >> 4)

(28.4)            *    (28.4)             =  24.8

 

This tends to keep more precision, although now you loose data on the fractional side.  How you shift will depend on the situation.  If you know your numbers have a small integer side and will not overflow, then shift after the multiply.   It is tempting to make wrapper functions or macros to handle all these details; it certainly makes your code more readable.  I am not going to do this because my use of fixed point numbers will be limited and proper functionality for fixed point math is too much for me to squeeze into these pages.

 

To divide is the reverse of multiplication. Just like .1 / .1 is 1.0, fixed point division results in a shift to the right. 24.8 / 24.8 leaves us with a 32.0 which is a normal int (by this I mean 24.8 and 32.0 as the number format not as actual numbers). To convert back, just shift left by 8. Again when you shift depends on the data you will be using. Shifting half before gives the best general results. Shifting after the division means that you will loose the entire 8 bits of fractional data so is not really an option. Normally the division shift is done by shifting the numerator to the right by 8 then doing the division leaving your data in the correct format. Again, this results in the top 8 bits of your numerator being lost so care must be taken. Often you will find that multiplication and division of fixed point are carried out in asm so that larger register sizes can be used to hold the result allowing the shift to be applied without an unnecessary loss in precision. Again, this is a topic that is beyond the scope of this tutorial. Our use of fixed point math will be limited only to that which is necessary for 2D games.

 

Fortunately, to multiply or divide a fixed point by an integer requires no conversion because the decimal is not shifted.  24.8 * 32.0 = 24.8

 

Occasionally, you will be working with two differently formatted fixed point numbers.  Just count your decimal places and shift to put them back where you desire.

 

Operations on bits

 

Knowing how to manipulate bits is an important skill for console development because much of the hardware is controlled via specific bits of specific registers.

 

Bitwise Operators

 

&	Takes two operands and ANDs the bits together.
|	Takes two operands and ORs the bits together.
^	Takes two operands and XORs the bits together.
~	Takes a single operand and negates all the bits.

 

 

Truth tables

 

AND &

 

OR |

 

XOR ^

 

NOT ~

 

 

AND is useful for checking the status of bits.  For instance to see if the first bit of a register is set simply AND the register with the value 1.  The result can only be 1 if the first bit of the register is also 1.

 

   1101 0100 1101 1101

   

0000 0000 0000 0001

 

It is also good for clearing bits.  If you want the lower 8 bits of a number cleared to 0 simple AND the value with a number that has all the other bits set to 1.  This is where hex comes in very handy.

 

 

 

OR is good for setting bits.  To set a bit, simply OR the register with a value that has that bit and that bit only set.

 

    1101 0100 1101 1101

|   0000 0010 0000 0000

   --------------------------------

     1101 0110 1101 1101

 

XOR is great for flipping between states. In the above example, if an XOR was used in the place of an OR then the bit would be set if it was clear and it would be cleared if it were set. This is great for flipping between the front buffer and back-buffer in the bitmap modes as well as being very useful anytime you need certain bits to alternate states every frame.

 

 

Finally we have the shift operators.

 

<< and >>

 

<< shifts the binary digits the requested number of places to the left.

 

101011 << 2 = 101100.  This has the same effect as multiplying the number by 2ⁿ where n is the number specified.  The shift operator is slightly faster than multiply so it is best to use when multiplying by powers of two and certainly use >> when dividing by powers of two.

 

One last trick that can be done with the binary shift operator is one useful for setting bits.

 

If you know you want bit 7 set (bit 7 is actually the 8^th bit from the right starting at 0) you simply combine what we learned about the OR operator and the << operator.

 

Register |= (1<<7)

 

One think to keep in mind is that the shift operators are very weakly binding.  This means that just about everything will take precedence over them.

 

2 << 4 + 1;  will shift 2 by 5 not shift by 4 then add one like you might think.  Overuse parentheses when dealing when shift operators.