Wednesday, January 16, 2008

A Quick Review of Boolean Math

My dots game core makes heavy use of boolean arithmetic so I am writing a very quick overview of boolean arithmetic. It is fairly technical, and more of a summary than anything. If there is interest (someone emails me or comments) I might go into a more detailed explanation of how boolean math works.

I come from an assembly language background (okay, technically I learned BASIC before learning 6510 assembly language) so dealing with boolean math, while rusty, is fairly simple for me. Java and ActionScript programmers probably are familiar with the boolean type which can be true or false but internally, computers see a single bit as being 0 or 1. Actually, boolean types tend to take up a lot more than a single bit as internally they are stored as bytes or integers. All data in computers is stored as bits with bits being grouped together into bytes. A byte is simply 8 bits. Having additional bits is like having more digits in a decimal number, except each additional digit is only a multiple of 2 instead of 10. Combinations of different bits give you different numbers. Eight bits means that there are 256 combinations, though one bit is used to determine the sign. The simplest way of working out binary is by assigning a value to each bit and simply adding the values together. Here is a power of two table:
Bit Value
0 1
1 2
2 4
3 8
4 16
5 32
6 64
7 128
When working with the bits in a byte, you use 5 basic operations. AND, OR, XOR, Left Shift, and Right Shift. The first three of these operations take two different groups of bits, perform the operation on pairs in the equivalent bit position, and result in a new result. The AND operation returns a 1 if both the bits are 1 (true) otherwise returns a 0. The OR operation returns a 1 if either or both the bits are one and a 0 only if both bits are 0. XOR, which stands for eXclusive OR,is a special type of or in which it returns 1 if one of the two bits are 1, but it returns false if both the bits are the same. The XOR results seem strange but are extremely useful as it essentially acts like a toggle. The left shift and right shift shift the bits to the left or the right respectively. The easiest way of thinking about this is that you are multiplying or diving the number by 2 for each position you shift the number.

No comments: