For Great Justice

The Lost Art of Bitmasks

September 30, 2008 – 8:00 pm

In this article, I will attempt to explain the so-called bitmasks, and the application of the binary operators (such as &, |, << and >>) found in pretty much every programming language. I myself have been in my education for four years now, but only last year or so did I encounter a practical application for using them. The title is as such perhaps just personal, seeing that I don’t really know the level of most modern-day programmers or whether they’re familiar with binary operations, but in my own experience, more emphasis is put on high-level structures and techniques, compared to low-level data storage, management and manipulation. This article will provide an introduction to binary operators, as well as how and when they can be applied - in a basic fashion, I’m sure that a lot more advanced applications for these techniques can be thought up.

I’m fairly sure that every beginning programmer will read through the introductionary text of a new programming language and encounter several operators whose function remains unknown - I’m referring to the &, |, << and >> operators, which are present in pretty much every programming language. These operators are the binary AND, binary OR, and the left and right bitshift operators. Some will research further and, if they’re familiar with binary numbers (i.e. how numbers are represented in a processor, on the lowest level, with ones and zeroes), might also discover what it is they do exactly on a value.

However, a practical application for those doesn’t always make itself apparent. For me personally, it took three years (or four, dunno exactly) before I finally encountered an application for it. This was whilst I was working on Clan Arena / the C4 engine, whose code contains a relatively large amount of binary operators and functionality.

In C4, the application of these operators is numerous, but it often boils down to one thing - setting and reading properties of an object, for example a renderable 3D model. One property of a model was how it was rendered - render its wireframe, textures, shadow, specific shadow mode, and I dunno what else. Those are just examples btw, I’m not actually sure how they were really used.

The point with that particular application was that you could assign several settings to a model, whilst internally, each setting was stored in just a single, numerical variable. This means that you could set a number of ‘flags’, as they’re also referred to, to a single object.

The easiest comparison is with booleans. Pretty much everyone knows the boolean true / false logic, so that shouldn’t need any more explanation. Let’s say you’re writing a 3D engine and you’re at the part where to decide which part of a model to render - wireframe, texture, shadow, etc. A model, in this case, can indicate what it wants the engine to render, i.e. the model has a set of properties - let’s call em renderWireframe, renderTexture, and renderShadow, all boolean variables.

For each rendering pass, the engine will check these three variables and render accordingly. Simple enough.

Now, with bitmasks and binary operators, you could store these three (and many more, up to 32 or 64) variables into just one single variable, an integer. This is a prime example of data encapsulation in OOP environments - from the outside, the renderable object has a few methods, say, getRenderShadow(), getRenderWireframe(), and getRenderTexture(), but on the inside, these three booleans are all stored into a single variable.

The easiest way to picture this is to rotate the three booleans to a horizontal orientation. Let’s say the number 1 is the boolean true, and 0 is the boolean false (which, btw, is perfectly applicable to C/C++ and other languages in that order). You’d get some vars like:

bool renderWireframe = 0;
bool renderTexture = 1;
bool renderShadow = 1;

In this example, we want to render the model’s texture and shadow, but not the wireframe. When you take the values, rotate them horizontally, you’d get the following value:

011

A binary number which, if you happen to know binary, can also be interpreted as the number 3, thus reducing the amount of variables used to store the rendering information from 3 to 1. You may think that this isn’t a major improvement, but imagine you have to send the rendering variables through a Message, as I’ve described in an earlier post: Next to the Model object’s three variables, you’d also get a Message object with the same three variables.

In the default C4 implementation, this’ll take a few minutes to create. When you reduce the amount of variables in the Model to 1, you also get a Message with just 1 variable to send - which takes less time to write , and reduces the overhead of packing / unpacking the message by a factor 3 at most (probably a lot less, seeing that the original booleans took up just 3 bits in memory, compared to the 32 or 64 bits an integer would take up). Multiply this saving by the amount of times the message is sent back and forth, and you’ll notice a major improvement (logically speaking, that is, it’ll probably save amounts that can only be measured in nanoseconds, something you’ll hardly notice)

This particular example is probably easy to imagine, but can easily be converted to the inner workings of a program itself - Objects send each other messages all the time, in the form of method invocations and the passing of other Objects. Reduce the amount of variables, and you get less method invocations, less memory access overhead, etcetera.

In a follow-up article, I’ll explain how I’ve used this technique for an access control system for a PHP-based website / application. For now though, I’ll try to explain how to use the system described above.

Usage

There’s basically three operations you’ll need to know in order to work with binary variables / bitmasks: Reading, writing, and deleting / unsetting. Reading involves checking a variable if it’s got a certain value - in the above example, for example, you’ll want to check whether to render textures or not, and in a later stage, whether to render shadows or not. Writing is also important, since you’ll have to set the value at some point. Finally, unsetting involves removing a value from the variable.

We’ll start by setting a flag / bitmask in a variable.

First, you’ll have to declare a variable that contains the information. In this case, we’ll use C/C++ datatypes, but this technique applies to pretty much every programming language. We’ll initialize it to 0.

int var = 0;

Note that the binary representation of this number is 00000000 in an 8-bit system (we’ll use just 4 bits for this example purpose, in a modern-day system this’ll probably be 16, 32, 64 or even 128 bits).

Second, we’ll have to have a base value for all possible settings that can be set. As in, we’ll want to declare a few constant values that represent the settings. These constants, and this is important, have to be a power of 2, like 1, 2, 4, 8, 16, 32, 64, 128, etcetera. If you translate those to binary, you get sequences like 0001, 0010, 0100 and 1000 - note that each binary number has just one 1 set, the rest is 0. We’ll define the constants as such:

const int renderWireframe = 1;
const int renderTexture = 2;
const int renderShadow = 4;

In C/C++ and most other languages, you can simplify this action by using the bitshift operator (<<). This will basically move all 1’s in a binary number one space to the left, so that 0001 << 1 (bitshift 0001 with 1 space) will result in 0010, as shown in the example below. This however doesn’t work in all languages - PHP, for example, has problems with assigning the outcome of an operator to a constant. You can just use the notation above, the result is the same.

const int renderWireframe = 1 << 0; // 1
const int renderTexture = 1 << 1;   // 2
const int renderShadow = 1 << 2;// 4

In this case, you won’t have to manually calculate the power of 2 yourself, which, at least for higher numbers, is convenient - and you don’t want to risk miscalculations, not even with one number, since it’ll cause unexpected results.

I’ll explain the reasoning behind this in a bit, if you don’t get it by then. First though, we’ll write a value into our integer variable we declared earlier.

Assignment

To assign a value to a binary variable, you’ll need to use the binary OR operator - the single | character, like so:

var = var | renderTexture;

(note that some languages also have the |= operator, which can also be used instead.) The OR operator basically says something like: ‘For each number in the binary representation of the resulting variable, set to 1 if either var or renderTexture also has a 1 at that position’. A calculus notation will clarify (I hope):

0000
0010
---- |
0010

0 OR 0 = 0
0 OR 0 = 0
0 OR 1 = 1
0 OR 0 = 0

(feel free to replace 0 and 1 with false and true, and the | operator with the || operator, which compares the variables on a true/false level, a step higher than the binary level)

We’ve added renderTexture to the var, indicating we’ll want to render the texture. Let’s also add the renderShadow one:

var = var | renderShadow;

Which looks like

0010
0100
---- |
0110

0 OR 0 = 0
0 OR 1 = 1
1 OR 0 = 1
0 OR 0 = 0

Hopefully, the reasoning behind assigning only powers of 2 to the constants become clear now - assign anything but a power of 2, and you could get multiple flags set in the variable, which isn’t what you intend. Unless you do, of course.

Now, our variable called var has a value of 0110, which, translated back to the decimal system, is 6. Note that 6 is neither the value of the renderTexture constant, nor the value of the renderShadow constant - it’s a combination of the two. It also isn’t a power of 2. Because of this, you can’t compare the value with one of the constants using the == operator directly - you’ll have to extract the value from the variable, or, to be more precise, check if the value you’re checking for is contained in the variable.

Querying

To do this, we use the binary AND operator, &, on both the var and the constant, and check if the result is anything but 0. Let’s check if our variable has the renderShadow flag set. Note that AND works the same as OR, with the exception that the resulting binary number is only set to 1 if both the first AND the second binary number at the position is 1.

0110
0100
---- &
0100

0100 is not 0, so we can safely say that the renderShadow flag is set inside the variable. I said earlier to see if the variable is simply ‘anything but 0′, but the above example indicates that the result is actually equal to the renderShadow constant - why not compare it with that? There’s a number of reasons for that, actually, the primary one being that it’s a lot simpler. What’s easier to type:

if ((var & renderShadow) != 0)

or

if ((var & renderShadow) != renderShadow)

?

The result is in both cases the same - true in this particular example - but the former is a lot easier to write. In fact, in a lot of languages that are either typeless or semi-loosely typed, in which a regular int can, for example, also be interpreted as a boolean, such as C/C++, you could also just do

if (var & renderShadow)

and leave out the comparison entirely - in C/C++ and PHP (haven’t tried this in other languages yet), anything but 0 is interpreted as a boolean true, when used in an if-statement.

However, it’s considered bad practice to use it in this way, since it may cause confusion and doesn’t work this way in all languages. Not only that, but it confuses one type with another - whilst an integer can be interpreted and used as a boolean, they’re logically speaking two entirely different things. I made a mistake when I tried to put the result of one of these operations into a variable - instead of the result (a boolean true or false), the variable was set to the numerical value of the result (4 in the above example), producing odd, unexpected results.

Querying multiple masks

You should note however that you can only check for one value at a time using this method (using the comparison to 0), even though you’ve learned how to combine two binary values with each other earlier using the OR operator. The reason is that, when comparing a variable AND-ed with a combination of two values, the resulting value will be a non-0 value even when just one of the two flags is set. This can be prevented by comparing the resulting variable with the combination value instead of checking if it’s not 0 . An example:

var = 0;
var = var | renderTexture; // set var to 0010

// check if var is set to both renderTexture and renderShadow
if ((var & (renderTexture | renderShadow) != 0)

First we combine the two constants:

0010 // renderTexture
0100 // renderShadow
---- |
0110

Then we do the comparison:

0110 // renderTexture | renderShadow
0010 // var
---- &
0010

0010 is 2, is not 0, so the comparison would return true - even though renderShadow wasn’t set. Compare it with the combination of the two instead of ‘higher than 0′, and you’ll get the right result:

if ((0010 & 0110) == (renderTexture | renderShadow))

0010 & 0110 = 0010
0010 & 0100 = 0110

Or, in full

if ((var & (renderTexture | renderShadow)) == (renderTexture | renderShadow))

0010 is not equal to 0110, so the above comparison returns false, which is what we expected. You’ll have to do some more typing to get this to work though, and do the or-ing of the two constants twice (unless you place the or-ed version in a local variable or, if you do the combined comparison a lot, a constant on its own).

int cmp = (renderTexture | renderShadow);
if ((var & cmp) == cmp) {}

Unsetting

The third and final operation we’ll want to be able to perform, is to unset a flag from the variable. To do this, we AND the variable with the inverse of the mask. Previously, we did the AND-operator, that turned 0100 and 0110 into 0100, since only the second 1 was set and both numbers have to be 1 in order to have a 1 in the same position in the result. To unset a variable however, we’ll want the inverse to happen - set the value to 0 if both numbers are 1, i.e. the position in the variable has to be set to 0 at the position where the flag is 1.

If we have a value 0110, and a mask 0100, and we want to unset the mask from the value (i.e. remove the second 1 in the value), we use the inverse of the mask and AND that with the value.

We take the mask 0100 and we inverse it, which can be done with the ~ operator in most languages (bitwise NOT). The inverse of 0100, ~0100, is 1011. ANDing that with the value 0110, and we get:

0110
1011
---- &
0010

or the value minus the flag value.

(another use of the binary NOT operator is to get the maximum value an integer can have - simply echo ~0, the binary NOT of 0, and you get a binary value of all 1’s, or the maximum integer value)

That’s about all there is to binary operators. As I said in the beginning, I’ll attempt to describe an application of this technique with a real-world example, by using the bitmask technique to define roles for users, and permissions belonging to those roles. The major advantage of using bitmasks in such a manner is that of database storage - you only need one database column to describe everything a user having a role can do. But more on that in the follow-up.

Tags: bitmasks