Welcome to the first episode of How I Programmed That, a blog and video series where I’ll teach how to program by example, sharing real programming problems I encounter and how I solved them. I’ll be using C/C++ syntax, and in this instance you’ll only need basic programming knowledge to follow along.

Today we start with something simple.

In my 2D grid-based game, I have a function I use a lot called OffsetToDirection. It takes a cardinal unit vector (i.e. one that can only be (1, 0), (0, 1), (-1, 0) or (0, -1)) and returns which of the four cardinal directions it points to (0, 1, 2, or 3, corresponding to right, up, left, or down, respectively).

In other words,

• if the input is (1, 0) the output should be 0,
• if the input is (0, 1) the output should be 1,
• if the input is (-1, 0) the output should be 2,
• if the input is (0, -1) the output should be 3.

So, how do you program that? Obviously I can just do a few ifs:

if      (input == {1,  0}) { return 0; }
else if (input == {0,  1}) { return 1; }
else if (input == {-1, 0}) { return 2; }
else if (input == {0, -1}) { return 3; }

However, since this function is used a lot in core parts of the game, it should be as fast as possible. So, we’d like to find an expression that arrives at the right answer without conditional branches.

The best solution for this kind of problems with a limited number of small inputs and outputs is usually truth tables. Truth tables are tables that show all the possible combinations of inputs and outputs. We’ll make a truth table for our problem to help us arrive at an expression that computes the correct result. In addition to the decimal values of our two inputs (x and y) and our output (dir), I’ll include the binary values of the two relevant bits on each of these variables. Separating the values into their bits will make it easier to find bitwise expressions that result in our desired output bits, which we’ll then merge together to arrive at the final output.

x_0 represents bit 0 of x, x_1 represents bit 1 of x, and so on for the others. I haven’t included higher bits, because they will always be the same as bit 1 for x and y, and they will always be 0 for dir, so they don’t give us any additional information, as you can see here:

This assumes 2’s complement binary representation, which is basically what all computers use for signed integers. Make sure to read about that if you didn’t know. All that matters for now is that, in 2’s complement, the value of -1 corresponds to all bits being set to 1.

Now we just have to come up with an expression that always computes the correct value of the first bit of dir given the input bits, and another that does the same for the second bit. Then we’ll merge the two together and we’ll have an expression that always computes the correct output value. I’ll focus on bitwise operations, but note that we could also try to use arithmetic and comparative operations, which are typically equally fast on modern CPUs.

The first thing I notice is that our input y_0 mimics dir_0 exactly, so for our first bit of dir, our work is already done; we’ll just take the first bit of y. Here’s the truth table again, and I’ve highlighted the two columns y_0 and dir_0 so that you can clearly see they are indeed the same:

For the second bit, we’ll have to create some combination of the other bits using bitwise operators to arrive at our desired output. For example, we can use an OR of x_1 and y_1. I’ve now highlighted x_1, y_1 and dir_1 so that you can confirm that the values of dir_1 correspond to (x_1 | y_1).

Now that we have an expression for dir_0 and an expression for dir_1, we have to combine them together. To write this in code, we just have to write the expressions with our variables, mask the expressions with an & operator and a numeric literal to clear the bits we don’t care about, and OR the two expressions together.

int dir = (y & 0x1) | ((x | y) & 0x2);

If you got lost, let me break this down:

int dir = (y & 0x1) | ((x | y) & 0x2);

We’re computing dir, which is the output of our function. y is the y value of our input. & 0x1 sets all bits of the value of y to 0 except for the first bit (bit 0). Therefore, (y & 0x1) will result in the correct value for our output at bit 0 (as proven previously with the truth table) and zeroes on all the other bits. Likewise, (x | y) combines our inputs x and y along with our knowledge from the truth table, to set the second bit (bit 1) to the correct output value. However, the other bits will be unwanted values, so we use & 0x2 to set the other bits to zero. Therefore, ((x | y) & 0x2) will result in the correct value for our output at bit 1 and zeroes on all the other bits. Finally, | ORs together our correct value on bit 0 and our correct value on bit 1.

It just so happens that the bit patterns we wanted fell right into the correct bit positions. Otherwise we would have had to use some bit shifts to put them in the right place before ORing the different bits together.

So, here’s the final function as seen in my code:

s32 OffsetToDirection(v2s offset){
    // Truth table:
    // x   y   dir |  x1   x0   y1   y0   dir1 dir0
    // 1   0   0   |  0    1    0    0    0    0
    // 0   1   1   |  0    0    0    1    0    1
    // -1  0   2   |  1    1    0    0    1    0
    // 0   -1  3   |  0    0    1    1    1    1
    //
    // dir0 = y0
    // dir1 = x1 | y1
    // dir = (y & 0x1) | ((x | y) & 0x2)

    s32 result = (offset.y & 0x1) | ((offset.x | offset.y) & 0x2);
	
    return result;
}

Confirmation

Now we should confirm the outputs just to make sure. It’s easy to make mistakes with these things. We’ll substitute each of the possible inputs on our final expression and compute the result.

(1, 0), should output 0:

(y & 0x1) | ((x | y) & 0x2)
(0 & 0x1) | ((1 | 0) & 0x2)
0         | (1       & 0x2)
0         | 0
0

(0, 1), should output 1:

(y & 0x1) | ((x | y) & 0x2)
(1 & 0x1) | ((0 | 1) & 0x2)
1         | (1       & 0x2)
1         | 0
1

(-1, 0), should output 2:

(y & 0x1) | ((x  | y) & 0x2)
(0 & 0x1) | ((-1 | 0) & 0x2)
0         | (-1       & 0x2)
0         | 0x2
0x2
2

(0, -1), should output 3:

(y  & 0x1) | ((x |  y) & 0x2)
(-1 & 0x1) | ((0 | -1) & 0x2)
0x1        | (-1       & 0x2)
0x1        | 0x2
0x3
3

And indeed, the truth table never lies.