GM:S 1.4 Bitwise operations and their uses

Discussion in 'Tutorials' started by Paolo Mazzon, Aug 4, 2016.

  1. Paolo Mazzon

    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.
    [​IMG]
    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.
    [​IMG]
    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: Aug 4, 2016
  2. BlessHayGaming

    BlessHayGaming Member

    Joined:
    Jun 20, 2016
    Posts:
    83
    Well written and worth bookmarking - good job :)
     
  3. Paolo Mazzon

    Paolo Mazzon Guest

    Thanks!
     
  4. Nocturne

    Nocturne Friendly Tyrant Forum Staff Admin

    Joined:
    Apr 13, 2016
    Posts:
    6,901
    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....
     
  5. Paolo Mazzon

    Paolo Mazzon Guest

    Can't say I've thought of that before. Will add this bit for sure.
     
  6. Nocturne

    Nocturne Friendly Tyrant Forum Staff Admin

    Joined:
    Apr 13, 2016
    Posts:
    6,901
    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... :) )
     
    Paolo Mazzon likes this.
  7. Galladhan

    Galladhan Member

    Joined:
    Jul 1, 2016
    Posts:
    119
    Paolo Mazzon likes this.
  8. Ariak

    Ariak Member

    Joined:
    Jun 20, 2016
    Posts:
    91
    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
     
  9. Ariak

    Ariak Member

    Joined:
    Jun 20, 2016
    Posts:
    91
    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...
    [​IMG]
    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;
     
  10. Ariak

    Ariak Member

    Joined:
    Jun 20, 2016
    Posts:
    91
    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 ^^
     
  11. Nocturne

    Nocturne Friendly Tyrant Forum Staff Admin

    Joined:
    Apr 13, 2016
    Posts:
    6,901
    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).
     
    Lonewolff likes this.
  12. zendraw

    zendraw Member

    Joined:
    Jun 20, 2016
    Posts:
    1,366
    what about a 48x48 grid? is it ok to shift by 5.5?
     
  13. Ariak

    Ariak Member

    Joined:
    Jun 20, 2016
    Posts:
    91
    @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....
     
  14. zendraw

    zendraw Member

    Joined:
    Jun 20, 2016
    Posts:
    1,366
    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.
     
  15. Salvakiya

    Salvakiya Member

    Joined:
    Jul 17, 2016
    Posts:
    84
    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: Aug 4, 2016
  16. Ariak

    Ariak Member

    Joined:
    Jun 20, 2016
    Posts:
    91
    @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.

    [​IMG]

    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....
     
  17. Paolo Mazzon

    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
     
  18. Ariak

    Ariak Member

    Joined:
    Jun 20, 2016
    Posts:
    91
    Thank you for your comprehensive answer!

    So bitshift is really faster, but not for Game Maker even with the YoYo Compiler.
     
  19. Salvakiya

    Salvakiya Member

    Joined:
    Jul 17, 2016
    Posts:
    84
    just make it an int before you bitshift?
     
  20. Paolo Mazzon

    Paolo Mazzon 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.
     
    Nocturne and Ariak like this.
  21. Salvakiya

    Salvakiya Member

    Joined:
    Jul 17, 2016
    Posts:
    84
    but since all numbers are doubles in GM then you really should not ever bitshift if you dont have to?
     
  22. jazzzar

    jazzzar Member

    Joined:
    Jun 29, 2016
    Posts:
    514
    nice tutorial @Paolo Mazzon i knew everything about binary,hexadecimal, and all this base stuff (all learnt at university) and didn't know what to use this things for, so thanks so much :)
     
    Paolo Mazzon likes this.
  23. GMWolf

    GMWolf aka fel666

    Joined:
    Jun 21, 2016
    Posts:
    3,443
    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)
     
  24. Paolo Mazzon

    Paolo Mazzon Guest

    I don't know if that works in GM, so I was just playing it safe for the tutorial.

    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.
     
  25. GMWolf

    GMWolf aka fel666

    Joined:
    Jun 21, 2016
    Posts:
    3,443
    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...
     
  26. Paolo Mazzon

    Paolo Mazzon Guest

    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.
     
  27. dphsw

    dphsw Member

    Joined:
    Oct 19, 2016
    Posts:
    82
    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;
    
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice