Legacy GM Bitwise operations and their uses

P

Paolo Mazzon

Guest
GM Version: Studio and up
Target Platform: All
Download: N/A
Links: The documentation on bitwise operations

Summary:
An in depth tutorial to teach you how to use binary operators to your benefit for beginners.

Tutorial:
First of all, I created a tool to let you easily test bitwise operations. You can download it here (Single runtime executable -- not installer). If you are new bitshifting, I recommend you download it to make visualizing and testing a tad easier.
If you don't want to use my program, the windows 10 calculator has a nifty little screen that allows you to play with the binary in programmer mode.
Anyway, onto the tutorial. I believe one of the least known topics to beginners is bitwise operations and their uses. I don't think I've ever seen a tutorial on such a thing, so I aim to make one. Since most people find binary and bitwise operations confusing, I'll try and keep it as simple as possible.

Before we go into the operators themselves, a few notes
  • You need to know how binary works before going over this tutorial
  • It would be very helpful if you knew all the major logic gates
  • All numbers in GML are equivalent to the C double; thus they are 64 bytes
  • Gamemaker numbers are floats, so they behave quite strange when decimals are pressent
Bitwise Operators
All bitwise operators work by changing the value of a variable at their binary level. In GM, there are 5 operators: and (&), or (|), xor (^), shift right (>>), and shift left (<<). We will be going over each separately.

AND (&) Operator
This operator works by comparing the bits of one number to another and AND comparing them. For the result bit to be true, the two input bits must also be true. This means that if you provide the two inputs
0 0 0 1 0 1 1 0 (22)
1 0 0 1 0 0 1 0 (146)

The result would be
0 0 0 1 0 0 1 0 (18)
This is because only at position 1 and 4 are both of the two input bits equal to 1.

OR (|) Operator
OR is the same as AND, except only one of the two input bits need to be 1 for the output bit to be 1. Given the same two bytes, but with an OR instead of AND,
0 0 0 1 0 1 1 0 (22)

1 0 0 1 0 0 1 0 (146)
The result would then be
1 0 0 1 0 1 1 0 (150)


XOR (^) Operator
This one is a little bit more complicated to understand, but is much the same as the others. With this operator, one of the two input bits must be 1 for the output to be 1, but if both of the input bits are 1 then the output is false. Going off the same example
0 0 0 1 0 1 1 0 (22)

1 0 0 1 0 0 1 0 (146)
Would produce
1 0 0 0 0 1 0 0 (132)

The bits at position 1 and 4 are both true and because of that they output a 0.

Bitshift left (<<) Operator
This one as well as bitshift right are much easier to comprehend than the others; fret not. This one does what it sounds like, moves all the bits left by a certain amount. This is very easily displayed

0 0 0 1 0 1 1 0 (22)
becomes this when left shifted by 2
0 1 0 1 1 0 0 0 (88)
As you can clearly see, the ones were just shifted over 2 places. One thing to note, however, is that bits do not "wrap," so if you bitshift left by one and there is a bit at the very end, it will not loop back to the start, it will be gone.

Bitshift right (>>) Operator
Much like bitshift left, this one just shifts the bits, but to the right. The same example but to the right should suffice for this portion
0 0 0 1 0 1 1 0 (22)

becomes this when right shifted by 2
0 0 0 0 0 1 0 1 (5)


Uses of bitwise operators
In modern games, especially 2D, there are not too many purposes for this. That said, there are purposes.

One of the most common purposes is to use it for flags or options. SDL frequently uses them. How it works is quite simple -- you OR together several options into a single variable that you can then use AND to determine the options. In code, it looks something like this
Code:
PlayerCreate(x, y, PLAYER_TALL | PLAYER_ORC);
This is quite simple to set up, you just need to make sure all the options equal n ^ 2. This might look like
Code:
PLAYER_TALL = 1;
PLAYER_BLACKSMITH = 2;
PLAYER_ORC = 4;
PLAYER_MAGE = 8;
When you OR together tall and orc, you get
0 0 0 0 0 1 0 1 (5)
Which later you can use to test the options. To see if the option PLAYER_ORC was chosen, all you need to do is
Code:
if (playerFlags & PLAYER_ORC > 0) {
    // They flagged orc
}
This is very useful if there are several options to choose from that would mean you would need many arguments; you can turn several arguments into one using flags.

Another use commonly used in the early game programming days was bitshift left and right by 1, since bit shifting left by 1 is the same as multiplying by 2, and bit shifting right by one is the same as dividing by 2; also without risking dividing by 0 problems. This was only really used, however, because the hardware back then was very weak and bitshifting is faster than multiplication and division. At this same time, storing several bool values is one byte was commonly used since ram was so scarce and a boolean value only requires one bit yet uses 8. If you had 80 bytes worth of boolean variables, you could turn that into 10 bytes with some bitwise operations.

The example mentioned by Nocturne is very practical in many games. In the case that you have a grid that is power of 2 in size, instead of dividing then flooring x/y coordinates, you can simply right bit shift.
Code:
// For this example, an 8 * 8 grid -- which means we can use >> 3 to divide by 8 and automatically floor
if (myGrid[# player.y >> 3, player.y >> 3] == 5) {
    // stuff here
}
This is also a very flexible solution. If you had a 16 * 16 grid, you could bitshift right by 4.

There are other uses such as string encoding, but that would require a fair bit of code to display and are easily found via a Google search. Anyway, I hope this was of some help to you and may possibly help you in the future.
 
Last edited by a moderator:

Nocturne

Friendly Tyrant
Forum Staff
Admin
I would suggest that you add a wee bit about using bit-shifting to floor and expand values for using in something like an inventory or a grid based collision system. For example, imagine I have a game where everything is based on an 8x8 grid, so I create a ds_grid and want top add everything in the room to it... using bitshifting it would be as simple as doing:

Code:
grid[# x >> 3, y >> 3] = id;
whereas you'd normally have to do:

Code:
grid[# floor(x / 8) * 8, floor(y / 8) * 8] = id;
I use this system ALL the time....
 
P

Paolo Mazzon

Guest
I would suggest that you add a wee bit about using bit-shifting to floor and expand values for using in something like an inventory or a grid based collision system. For example, imagine I have a game where everything is based on an 8x8 grid, so I create a ds_grid and want top add everything in the room to it... using bitshifting it would be as simple as doing:

Code:
grid[# x >> 3, y >> 3] = id;
whereas you'd normally have to do:

Code:
grid[# floor(x / 8) * 8, floor(y / 8) * 8] = id;
I use this system ALL the time....
Can't say I've thought of that before. Will add this bit for sure.
 

Nocturne

Friendly Tyrant
Forum Staff
Admin
Cool... It's a great everyday use of bit shifting that is really fast and easy on the processor. :)

(PS: Great little tutorial, btw! I never said in the previous post... :) )
 

Ariak

Member
Here's another use for binary and grids:
Assume you have a 32x32 grid - we want to determine the nearest snappoint of a given coordinate - say 756

Code:
x=x&~31;  //31 is not a mistake here! its cell_dimension -1;
will return 736 - so the left hand side intersection with the grid, as this will always "round" down to the nearest value fully divideable by 32.

Tech Blog on Bitwise by Mike Dailly:
http://www.yoyogames.com/blog/46
 

Ariak

Member
I've got a question of my own regarding this, as in all the testing ive done I cant seem to get the expected performance boost by the basic bitshifts...
Is it because of me using the 'div' function thats just really optimized?

I mean in that case a grid might as easily be determind by [# xx div cell_dim, yy div cell_dim] which prevents the need to add another macro for the power of 2 of the grid. 32: 2^5. for xx >> 5; yy >> 5;
 

Ariak

Member
If im seeing this correctly the bitwise is actually slower, as it takes up 2,5% more time. And a loop of 10000 is pretty large i think ^^
 

Nocturne

Friendly Tyrant
Forum Staff
Admin
Test using the YYC (can't use the debugger then, but throw some get_timer and show_debug:_message in and you can get results easily).
 

Ariak

Member
@Nocturne , i will try after my exam ;) - maybe the yyc will change things up.

@blacklemon : no, im pretty certain it needs to be an integer value! and 48 is not a power of 2. 32=2^5, 64=2^6; 48=2^5.5849....
 

zendraw

Member
i know its not a power of 2 thats why im asking, overall whats the situation when you dont use a power of 2 grid or pretty much anything.
 
S

Salvakiya

Guest
i know its not a power of 2 thats why im asking, overall whats the situation when you dont use a power of 2 grid or pretty much anything.
simple... grab the larger nearest power of 2 grid then set the max position of the player so it does not go larger than that grid

so in your case the nearest max power of 2 grid would be 64. you bitshift by 6. if the players x or y comes out to be larger than that 48x48 set their position to 48x48.

Surfaces in GM work the same way. the size of them in memory must be a power of 2. so depending on the size the player states the surface will be it actually puts that surface onto another which is rounded to the nearest largest power of 2
 
Last edited:

Ariak

Member
@Paolo Mazzon , @Nocturne - the results are in!
I tested this using the the show debug message, aswell as by compiling the .exe with the YoYo Compiler for Windows and having the ouptut displayed on the GUI - both yield the same results.


Gotta say: atleast for grid calculations im gonna stick with div. Dont need an extra macro variable for the power of 2 ;D

I really wonder how this is possible....
 
P

Paolo Mazzon

Guest
@Ariak
GML is interpreted, and all numbers are doubles. I don't know if you know how floating point numbers work, but they don't work in such a way that allows them to be bitshifted like that. If you put these 3 lines of C++ into a C++ compiler, you will get an error telling you that you cannot bitshift a floating point number.
Code:
int intNumber = 32;
double floatNumber = 32;
cout << "Int: " << (intNumber >> 3) << "\nFloat: " << (floatNumber >> 3) << endl;
MSVC 14 gives the error "Error C2296 '>>': illegal, left operand has type 'double'." This means you must cast it to an integer and then back; essentially nullifying any performance gain provided by the operator. Since you now make me curious, I made a test in C++ to find out what kind of numbers we are talking about.
1st run
Code:
Bitshift time on float: 4802094
Div time on float     : 4669335
Bitshift time on int  : 3674793
Div time on int       : 5102870
2nd run
Code:
Bitshift time on float: 4671262
Div time on float     : 4674080
Bitshift time on int  : 3379228
Div time on int       : 4231229
3rd run
Code:
Bitshift time on float: 4621754
Div time on float     : 4648834
Bitshift time on int  : 3376624
Div time on int       : 4949846
Averages
Code:
Bitshift time on float: 4698370
Div time on float     : 4664083
Bitshift time on int  : 3476882
Div time on int       : 4761315
(The C++ source, I used MSVC 14 with debug mode so no compiler optimizations)
As you can see, bitshifting floats is marginally more expensive than dividing, while bitshifting ints is clearly much faster than dividing them.

EDIT: Result time is in microseconds to save you a trip to the source
 

Ariak

Member
Thank you for your comprehensive answer!

GML is interpreted, and all numbers are doubles.
This means you must cast it to an integer and then back; essentially nullifying any performance gain provided by the operator
So bitshift is really faster, but not for Game Maker even with the YoYo Compiler.
 
S

Salvakiya

Guest
Bit shifting floating point numbers is heavier than dividing no matter what.


That is the part that slows it down, bit shifting a floating point number is heavier than dividing it, no matter how you slice it.
but since all numbers are doubles in GM then you really should not ever bitshift if you dont have to?
 
P

Paolo Mazzon

Guest
Can i ask why this could not be shortened to
Code:
if (playerFlags & PLAYER_ORC) { // They flagged orc}
(i havent tested, but it seems like it would still work to me)
I don't know if that works in GM, so I was just playing it safe for the tutorial.

but since all numbers are doubles in GM then you really should not ever bitshift if you dont have to?
For cheap little hacks, you are right to some extent. While all numbers are doubles and thus it is faster to divide, division/multiplication is not the only reason you bitshift. Bitshifting moves bits over in a direction, and I also made the example of string encoding, which often requires bitshifting.
 

GMWolf

aka fel666
For cheap little hacks, you are right to some extent. While all numbers are doubles and thus it is faster to divide, division/multiplication is not the only reason you bitshift. Bitshifting moves bits over in a direction, and I also made the example of string encoding, which often requires bitshifting.
Im not sure if bitshifting strings is possible in GM. i havent tried, but i think itl give you an error.
A solution would be to extract each character out of the string, but GM string manipulation is horendously slow...
 
P

Paolo Mazzon

Guest
Im not sure if bitshifting strings is possible in GM. i havent tried, but i think itl give you an error.
Not what I'm talking about? If for some reason you needed to use UTF-16 or some other arbitrary ISO standard, you would have to read a string character by character and possibly decode it if strings are stored as UTF-8 internally (I don't know about that one). More of an obscure example, but the point remains.
 

dphsw

Member
This tutorial doesn't actually mention how to switch flags off once you've switched them on. If you know they're on you could switch them off with the bitwise XOR operator (^), which was mentioned. But if you want to switch some flags off, without knowing whether it they were previously switched on, you would use the unary bitwise negation operator (~), along with an AND.
Code:
0 0 0 1 0 1 1 0 (22)
1 0 0 1 0 0 1 0 (146)
0 1 1 0 1 1 0 1 (~146)(with some more ones to the left)
0 0 0 0 0 1 0 0 (22 & (~146)) (now any bits that were on in the 146, have been switched off in the 22)
So to deactivate the player's tallness, you could write:
Code:
playerFlags = playerFlags & (~PLAYER_TALL);
I thought it worth pointing out, because although this thread is 6 months old, it was the top Google search result for bitwise operators in GameMaker (the official documentation was only the third highest result!) when I was trying to confirm what the unary bitwise inversion operator was in GML.

BTW, just as instead of writing 'speed = speed + 3', you can just write 'speed += 3', you can do the same with the bitwise operators.
So these two lines of code are equivalent:
Code:
playerFlags = playerFlags | PLAYER_ORC;
playerFlags |= PLAYER_ORC;
 
Top