At the beginning of the computer era, binary and hex (hexadecimal) were a way of life, probably because high level languages (such as BASIC) were simply too slow. These days however, with the power of even the most average PC, you no longer have to know any of this and you can do things the long way, since the speed of the machine and its more complex CPU construction will make up for any short comings this approach has.
As a very simple example, in the past multiplying by 32 might have taken several CPU cycles to execute, while a simple binary operation to do the same thing would have taken only 1. As machines have gotten more complex, they have also reduced the time many complex instructions take to run so that now, a 32x32 bit multiply might well only take 1 cycle - same as the binary operator. This is great news of course, since it means that you no longer have to optimise every line of code you write, but if this is the case - should you really care about binary at all?
The answer is definitely "yes, you should". While it's true you can still get some speed ups - and sometimes these can be significant - using binary and hex leads to you knowing the CPU better and can also lead to writing better code, being able to pack data better, and making some tasks a lot simpler. This page is going to explain a bit about what binary is as well as how it can be used when making your games.
So let's look at the most basic binary theory first - how numbers are created. Take a look at this table:
000 = 0
001 = 1
010 = 2
100 = 4
Each 1 or 0 represents a single bit of data, and as you can see this means that in binary, 10 equals 2! Each bit is 2 times the previous value with the first bit being equal to 1. So bit 2 = 2, bit 3 = 4, bit 4 = 8 and so on (as shown below in this byte table - a byte being a collection of 8 bits):
00000001 = 1
00000010 = 2
00000100 = 4
00001000 = 8
00010000 = 16
00100000 = 32
01000000 = 64
10000000 = 128
That's fine if you want numbers that are a power of 2, but how do we create more complex numbers? Well a single binary number can only store a 0 or 1, and that's it, so for more complex numbers we need to add bits together. If for example we wanted to make 6, we would add 4 and 2 together like so.
00000010 = 2
00000100 = 4
00000110 = 6
This is true of all binary numbers, and how the computer makes up any number internally. Let's take a slightly more complicated number as a further example: 23. The number 23 is actually made up of 1+2+4+16 or 00010111. How about a much more complex example: 196? Well, that's made from 128+64+4 or 11000100. So actually not that complex really. If we start doing values outside of the range of a byte (which can store numbers from 0 to 255), it does start to get a little harder to track. For example, 217,361 is 110101000100010001 in binary. Or, 1+16+256+etc... The rules are the same no matter what the value being expressed is - each number is created from adding multiple bits together.
Now what does this mean in binary? Well, let's say you want to store a true or false as a value. Usually compilers will use an INT (an INT is usually defined as a signed 32bit number) and then simply assign it to 0 or 1. However, having only 2 states, a true / false value is ideal to store in a bit, and if we did this we could store 32 true / false bits for each INT rather than just one.
How would we do this? Well pretty easily it turns out:
flags = flags | 1;
The "|" operator is a bitwise OR, and this means the above instruction ORs 1 into flags. If you remember from earlier, using a 1 will set the first bit. If we wanted to set the second bit, we would do this:
flags = flags | 2;
We OR in 2, because the bit pattern 00000010 is equal to 2. So what exactly does the binary OR operator do? Well, it merges all the bits together into a single value, like this:
010110100
110011001
110111101
Here's what's known as a truth table for the OR operator:
00 | 00 = 00
00 | 01 = 01
01 | 01 = 01
01 | 00 = 01
So where there is a value with 2 zeros, it'll stay zero. The advantage of using BITS as a true/false state, is they you can set several flags in one operation, something you simply couldn't do with a normal Boolean value. For example, let's say bit 1 is an "active" flag, and bit 3 is a "visible" flag. We could set both by doing this:
flags = flags | 5;
This is because 5 is 00000101 in binary, and following the rule above, the variable "flags" will get both these 2 bits merged with its own. So even if bit 1 was already set, the operation still works and bit 3 will now also be set.
What about clearing flags? Well this is where the binary AND operation comes in. When you AND something you the bits that are set in the mask are kept, while the bits that are clear in the mask, are removed - like this:
01110010101
00110000100
00110000100
As you can see, where there is a bit in each value, the bit is kept, and where there is a mix or 0's and 1's these are reset to 0. Here's the truth table for ANDing:
00 & 00 = 00
01 & 00 = 00
00 & 01 = 00
01 & 01 = 01
So, only when there is a bit in each place will it be kept. What this means, is that just as you are able to set multiple flags at once, you can also clear multiple flags at once. For example, let's take the case above, but this time clear them. We want to clear bits 1 and 3 (giving us the value 5), but in remembering the truth table above, what we want to do is keep all the other bits, and clear bits 1 and 3. This would be a binary "mask" of 11111111111111111111111111111010 (32bits). This mask keeps all bits currently set, but clears the two bits we actually want cleared. So if had a value of 1000111011 and I wanted to clear bits 1 and 3 using the mask above, I would end up with this...
00000000000000000000001000111011
11111111111111111111111111111010
00000000000000000000001000111010
This is great, but if we had to work this out every time we needed to clear flags, it would become tiresome. What we need is a way to flip bits easily (and preferably without CPU cost). Fortunately there is an easy way of doing this by using the NOT operator.
The NOT operator is just what it says - NOT those bits. Here's a truth table for NOT.
~00 = 11
~01 = 10
~10 = 01
~11 = 00
This operator makes removing flags very simple, and better yet, it's usually a compile time optimisation meaning if you're using a constant number (i.e. not a variable) then the compiler will flip the bits automatically for you. Take this statement where we want to clear bits 1 and 3 again:
a = a & ~5;
This will actually compile down to just "a & 11111111111111111111111111111010". This makes life pretty simple in terms of clearing flags.
The last operator we want to look at is EOR (Exclusive OR, sometimes called XOR), this operator flips the bits set in both values. Here's the EOR truth table:
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
This is a curious one, but incredibly useful. For example, let's say we want a counter that simply counts from 0 to 1 and back to 0 (toggling between 0 and 1), we could add one and do an IF to see if it's gotten to 2, and then reset it back to 1. Or...we could add 1 and then AND it with 1 (since 01+01 = 10, and 10 & 01 = 0) or we can do this:
a = a ^ 1;
What this does, is first time through is 0 ^ 1 = 1, then the second time 1 ^ 1 = 0, thereby toggling things back and forth from 0 to 1.
So - OR (|), AND(&), NOT(~) and EOR(^) let us manipulate bits with relative ease, allowing us, at the simplest level, to control multiple bits at once. We can obviously use these operations for other things when developing our games, like masking sprites, doing integer MOD operations (using AND) or doing nice looping counters.
How does a computer add? Well let's look at a very simple example 1+1.
00000001
00000001
00000010
Just like normal additions, we add numbers together and then we overflow into the next column, but unlike a normal decimal addition, we can only go to 1, not 9. So adding a 1+1 means we overflow into 10. So let's look at a more complex example.
01011011 = 91
00101101 = 45
10001000 = 136
It's obviously harder to see here, but the overflows ripple along until there are no ones in a column - or 2 at which point an overflow bit makes 3 and it stays there. Fortunately, you don't ever have to worry about this unless you want to add very large numbers together (like 2x128bit numbers). It's also worth noting, that computers can only add (or subtract, multiply or divide) 2 numbers at once, even SIMD is based on 2 calculations at once, but doing multiple calculations in parallel. Take 19 + 19 + 19. Being human, we can add all the 9's together, carry the 2 and then on we go! But computers can't do that - what they can do is this: (19 + 19) + 19. So they'll do each calculation in blocks of 2.
The binary calculations that are of interest to us, and of great use, are multiplication and division. Computers only multiply in 2s, and to do more it'll break a number apart, and then add all the results together. Let's take some very simple examples first. 4 * 2 = 8. Now to multiply by 2 in binary, we shift all the bits to the LEFT by one. Like this:
00000100 * 2 = 00001000 = 8
All the bits in this case have moved to the left by one, making it move from the 3rd bit, to the 4th, and changing the value from 4 to 8. How about a larger number?
101 = 01100101 * 2 = 11001010 = 202
Again, all the bits move on one, and that multiples by 2. So, how about a multiple by 4? Easy, we shift everything left by 2, rather than one. So how about 16, or 128? This would require a left shift of 4 bits, or 7 bits respectively. This is incredibly useful; it means we can do simple multiplications by simply moving bits around. To do this, we use the SHIFT operator <<. Here are some examples:
00000001 << 1 = 000000010 = 2
00000001 << 2 = 000000100 = 4
00000001 << 3 = 000001000 = 8
00000001 << 4 = 000010000 = 16
00000001 << 5 = 000100000 = 32
00000001 << 6 = 001000000 = 64
00000001 << 7 = 010000000 = 128
00000001 << 8 = 100000000 = 256
Now, aside from being very useful for fast/simple multiplications, it's also very useful for setting specific BITs, without having to figure out the bit value. Let's say we wanted to set bit 27, what number is that? (67108864 by the way!), well we can use the syntax above to easily set flags like this:
A = A | (1<<27)
Okay... so actually this would be bit 26 the way I've been describing things so far (as bits have been starting at one), but actually... bits start at bit 0, and go upwards, not at bit 1. So while there are 32 bits in an INTEGER, the bits range from 0 to 31, not 1 to 32. This is actually pretty useful, as we can now set up CONSTANTS for bit numbers.
So let's say Bit 27 is an active flag, and bit 0 is an exploding flag. How can we set both?
ACTIVE= 27;
BOOM = 0;
A = A | (1<<ACTIVE) | (1<<BOOM);
This may look like a lot of code, but if these numbers are constants, the compiler will pre-compile these operations into a single value so that we end up with this as actual code.
A = A | 13421772;
Clearing these bits (as we saw above) is simply a matter of using the NOT modifier, like this:
A = A & ~((1<<ACTIVE) | (1<<BOOM));
So this happily lets us set and clear any bits we'd like, and it also lets us compress out data structures massively. Compressing data structures is a good thing, because if you use less memory, you get less cache misses, and your code just runs faster. Put it this way, what's quicker, copying 32Mbytes or data, or 4Mbytes? Well, quite clearly 4 is. So if you can pack all yours flags down into a single memory access, this is good!
Let's take a quick look at how you do division, and why it's going to be so useful. Let's take a simple number - 64 - and divide by 32:
64 / 32 = 01000000 >> 5 = 00000010
So there you shift the single bit down by 5 (which is the number of shifts required for 32 – look above), which gives us 2. But what happens if here are other bits in there? Well let's take a look:
68 / 32 = 01000100 >> 5 = 00000010
So there you go…. It's exactly the same. The bits we shift down are simply lost. This is actually really useful, because when dividing down if we need the remainder, there's an even easier way to get it, which we'll get to in a moment. But first, let's take a practical example. I have an X and Y position, and I want to get the grid cell this falls in, where the grid is 32x32 in size. This method allows is to store objects, collisions, flags – all manner of things, and access them very quickly. So here we go:
var X_index = x>>5;
var Y_index = y>>5;
cell_data = mygrid[# X_index,Y_index];
This is quick, very quick. This avoids the need to do a floating point divide, and then a floor( ) calculation – which all adds up.
So, what if we wanted the remainder? Perhaps this remainder is used as some kind of order or something, whatever the reason, getting a remainder is as simple as doing an AND:
var r = x & 31
var X_Index = x>>5;
Now, the sharp-sighted amongst you might have noticed we've used both here (as is so often the case), but this is still only a couple of instructions. But why the 31? Well, as bit 5 is 32, then all the bits below would be 31, and that's the maximum remainder so that's what we AND with (we could also use ((1<<5)-1) which would make 32-1 = 31. Now, if I were to do this without understanding binary, it would look like this:
var r = x mod 32;
var X_Index = floor(x/32);
So why is this much worse? Well, in order to divide by 32, we have to execute a floating point divide – which obviously takes time, but in order to do the mod 32, you actually have to do another one! If we were doing this in assembler, we actually get BOTH values in one divide, but you don't get this in high level languages (well… not very often), and so you have to do all the work twice. This adds up, especially if you're doing a tight loop with lots of calculations like this. Integer divides as shown above really help optimising your game.
Since this can be quite a complex concept to grasp and then apply to real-world programming situations, you can find below a series of short examples that could be applied to any game made with GameMaker Studio 2.
GameMaker Studio 2 devs often use the function place_free(), and then when a collision is found, try to slowly move the object out by either looping around an x or y position (or something) while continuing to execute that function, or by using the move_outside_all() function.
So, what's the faster way to do this? Well, if we use proper power-of-2 tiles, then we have a very simple method that's also lightning fast. If we are moving right, and we've moved into a collision block, then as we know everything is aligned to 32, so we need to also align the sprite to a 32 pixel boundary - preferably the one to the left - so the sprite is moved OUT of the collision. This is really easy, knowing the rules we've used above to get the remainder, and knowing how to get the inverse of bits, we can simply do this:
x = x&~31;
That's right, that's ALL that it takes to align to a 32 pixel boundary. By changing the 31 we can align to anything we like – as long as it's a power of 2. (This is the equivalent of dividing by 32, then multiplying by 32, thereby removing the lower bits.)
If we wanted to align to the right, then we'd do the above, but then add 32 to move it into the next tile. Simple. All this makes the whole collision code monumentally faster, and lets you spend the CPU time where you really need it.
Say you have a level with a few doors, and a key for each. How can you easily mark a key for a key? Well, normally you'd just assign an ID to the key and the door. So what if you wanted a key to open 2 or 3 doors? Easy. You use a MASK. The door would have a single "bit" assigned like so door_id=1 (0001), another with door_id=2 (0010), door_id=4 (0100),door_id=8 (1000) and so on. If we wanted the key to open door 1 and 3, then the key would have the MASK of 5 (which is 101 in binary). If we perform an AND of this, and it comes out "not zero", then we know if the key can open the door. You could also have keys that opened nothing by having a MASK of 0. See the code below for the actual check:
if( (key_id & door_id) !=0 ) { opendoor(); }
Let's say we want a simple animation counter, counting from 0 to to 15 (as we have 16 frames of animation), now we can either do an increment, and then do an IF, or we can use our knowledge of binary and remove the IF completely. IF's are slow, and if we don't need them, we should remove them.
counter = (counter+1)&15;
Since 16 frames is a power of 2 number, and since 0 is included in the counter, we can reduce the POW2 number by 1 and use it as a MASK, and using that we can use it to wrap our counter. If the counter moves from 15 to 16, we end up with bit pattern 10000, and if we then AND with 15 (bit pattern 01111) we end up with 0. This means the above code is incredibly useful for wrapping counters - as long as you use POW2 frame numbers.
What if you wanted to check to see if something was a power of 2? Well, here's a neat little trick.. This will return TRUE if argument0 is a power of 2.
return (argument0&(argument0-1))==0;
So if we had the number 51 (110011) what does this do? Well, we get this... 110011 & 110010, which obviously leaves us with FALSE, as there are lots of "bits" left after the AND. If we had 64 1000000, then it becomes this... 1000000 & 0111111 which DOES leave us 0, so it's TRUE.
Here's a quick bit of code to align to power of 2 numbers. (1,2,4,8,16 and so on). This can be very useful for memory allocation, or making sure you write data to proper boundaries.In this example, argument0 needs to be aligned to argument1 bytes, where argument1 is a power of 2 number. This little script rounds UP to the next boundary of the desired number.
return (argument0 + (argument1-1)) & ~(argument1-1);