Levereging the power of flags in function arguments

I bet you have called functions like these at some point in your life. They seemingly accept parameters that are separated by the pipe (or bitwise OR) operator. PHP's file() function, for instance, accepts an optional third parameter that can have one or more values. It's not uncommon for me to call it with the FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES flags.

But how do they actually work under the hood ?

It turns out that it's only a matter of simple bitwise operations. Yes, the pipe operator was a dead giveaway but still. Let's try to implement a simple example to demonstrate how it works. I'll be using D in the code below, but the same rules apply to languages that support bitwise arithmetic. If your language of choice doesn't support them then I recommend that you stop using Brainfuck.

Here's a problem that sounds like it could have some real world applications. Imagine that you're making a run of the mill RPG game where the main character can move horizontally, vertically or diagonally. The goal is to write code that implements a character's movement. There is more than one way to solve this problem, but let's adopt a flag-based approach to explain how it works.

Let's define a few constants for the possible directions :

enum Direction
{
 UP = 1 << 0,
 DOWN = 1 << 1,
 LEFT = 1 << 2,
 RIGHT = 1 << 3
}

The << operator simply shifts a number N bits to the left. In this case, Direction.LEFT has a binary value of 100 (or 4 in decimal) because 1 was shifted 2 bits to the left. The particularity of these values is that we can store all the possible combinations in a four bit wide integer, even though we'll really need to use two values at a time in our situation. A couple examples to drive the point home : Direction.UP | Direction.LEFT results in a binary value of 0001 | 0100 = 0101. Direction.LEFT | Direction.RIGHT results in 1100, but since it doesn't make sense for a character to move both left and right, we'll simply ignore it.

Back to the task at hand : right now we're able to store the state of the D-pad in an integer.

How do we extract the state of the individual directions from it ? To do so, we can use the bitwise AND operator. In the previous example, both the UP and LEFT buttons were pressed, which resulted in a value of 0101. So if we AND this value with one of the aforementioned constants, we'll be able to tell if that specific bit is set : 0101 & 0100 is not equal to 0 because the third bit is set, we can deduce that the LEFT button is pressed. We can also deduce that the UP button is pressed if we follow same method. However, the DOWN button isn't pressed because 0101 & 0010 is equal to zero. Furthermore, we can get creative and check the state of multiple buttons by ORing them together then ANDing the result against the state of the buttons : 0101 & (0100 | 0001)

Now that that's taken care of, we can write a function that moves the character. Assuming that the character has X and Y coordinates, our function might look like this :

alias Point = Tuple!(int, "x", int, "y");
Point move(Point position, Direction direction)
{
 if(direction & Direction.UP)
  position.y--;
 if(direction & Direction.DOWN)
  position.y++;
 if(direction & Direction.LEFT)
  position.x--;
 if(direction & Direction.RIGHT)
  position.x++;
 return position;
}

I took the liberty of adding a tuple to make it easier to reason about the X and Y coordinates. You can think of it as an ad-hoc structure with x and y fields.

A nice side-effect of the code above is that it handles diagonal movement in addition to horizontal and vertical movement. As such, if you call move(tuple(30, 30), Direction.UP | Direction.LEFT), the resulting position will be tuple(29, 29). Opposing directions will cancel each other out, and so move(tuple(30, 30), Direction.UP | Direction.DOWN) will return tuple(30, 30). Here are a few more (compile-time) unit tests for the move function :

unittest
{
 enum Point position = tuple(30, 30);
 static assert(position.move(Direction.UP) == tuple(30, 29));
 static assert(position.move(Direction.DOWN) == tuple(30, 31));
 static assert(position.move(Direction.LEFT) == tuple(29, 30));
 static assert(position.move(Direction.RIGHT) == tuple(31, 30));

 static assert(position.move(Direction.UP | Direction.LEFT) == tuple(29, 29));
 static assert(position.move(Direction.DOWN | Direction.RIGHT) == tuple(31, 31));
 static assert(position.move(Direction.LEFT | Direction.DOWN) == tuple(29, 31));
 static assert(position.move(Direction.RIGHT | Direction.UP) == tuple(31, 29));

 static assert(position.move(Direction.UP | Direction.DOWN) == tuple(30, 30));
 static assert(position.move(Direction.DOWN | Direction.UP) == tuple(30, 30));
 static assert(position.move(Direction.LEFT | Direction.RIGHT) == tuple(30, 30));
 static assert(position.move(Direction.RIGHT | Direction.LEFT) == tuple(30, 30));
}
And that's all there is to it !

Commentaires

Posts les plus consultés de ce blog

Writing a fast(er) youtube downloader

Decrypting .eslock files

My experience with Win by Inwi