Bitwise Operations and Why You Might Care

LLWardIII
October 26, 2001

What are bitwise operations?

Most operations in programming happen on chunks of memory that are a byte or larger. For example, when you compare one character to another, you are comparing one byte to one byte. When you compare two ints together, you compare four bytes to four bytes. Sometimes, though, you need to get at specific bits within a sequence of bytes. The bitwise operators in a language (if the language has them) allow you to do just that.

This document discusses how you use bitwise operations and, more importantly, why.

Bitwise operations in Java

Not all languages support bitwise operation. Java, C and C++ do. In fact, these languages all use the same syntax for bit operations. These operations are summarized in the following table. In the examples, A and B are both one byte long.

Sun has some more details about the various logic tables here.

Using bitwise operations to implement flags

One of the primary uses for bitwise operators is to implement "flags". The idea of flags is that you have a single integer that hold a number of options in it at once. The integer will contain as many flags as there are bits in the integer (usually 32).

Suppose you were building software to list all of the hotels in a city. One of the things you might track is what kind of extras were available at each hotel (swimming pool, gym, etc.).

The first thing you would do is define a constant for each kind of extra. But these are not just any constants. To work as flags, the constants must be powers of 2. By making them powers of two, what you are really doing is defining a constant integer that contains exactly one bit that is high (1) and all others turned off (0). The constants might look like this:

static final int NO_EXTRAS    = 0;  // In binary: 00000
static final int HAS_POOL     = 1;  // In binary: 00001
static final int HAS_GYM      = 2;  // In binary: 00010
static final int HAS_LAUNDRY  = 4;  // In binary: 00100
static final int ALLOWS_PETS  = 8;  // In binary: 01000
static final int HAS_INTERNET = 16; // In binary: 10000


You start out with an integer with all flags turned off:

int vFlags = NO_EXTRAS;

You need to be able to do three things:

Set a flag

vFlags = vFlags | HAS_POOL;
// vFlags now has HAS_POOL turned on.

vFlags = vFlags | HAS_GYM;
// vFlags now has HAS_POOL and HAS_GYM turned on.

Clear a flag

vFlags = vFlags & (~HAS_GYM)
// vFlags now only HAS_POOL turned on.

Check a flag

if ( (vFlags & HAS_POOL) == HAS_POOL )

Why use flags?

So, why would you want to do this?

The first reason is that flags done in this way take up much less RAM than if you used a boolean for each flag. For example, say you have a class with ten options that can either be on or off. You could implement those options with ten booleans. Since booleans under many languages actually use 32 bits each, the booleans would add 40 bytes to every instance of the class. Using a single int field that holds flags, those same options are stored with only four bytes.

For an individual class, the RAM savings may not be all that significant, but imagine a list with 100,000 of the above class. Using flags would save 3,800,000 bytes or about 3.6MB of memory.

Another reason to use flags is not as obvious, but tends to be the reason most people use them: they make it easier to add options to your code later. Take an example from the Win32 API: window styles. Using the Win32 API, you can create windows with all kinds of styles, such as having a title bar, border, close box and so on. The main API to make a new window, CreateWindow, takes a dwStyle parameter that is a collection of flags. This allows any combination of flags to be passed in a single parameter.

Think for a moment what problems would result, however, if they used booleans instead of flags in this call. First of all, there would a whole lot of boolean parameters and the function would be even uglier than it is now. More importantly, it would be nearly impossible to add new options. They would have to change the API call to add that new option. But if they did that, what would happen to all the code written to the original version? It would no longer compile.

By using flags here, adding a new window option just means adding an unused flag constant. Much easier.

For another example of flags making future changes easier, say the class mentioned above (the one with the ten options) was serialized to a file called "sample.txt". If implemented using the boolean scheme, each boolean would be serialized individually (e.g. "1,0,0,1,1,1,0,1,0,1" gets written into the file stream).

But what if a new option was added later (as a new boolean)? The code to serialize would then read and write that new boolean, but what happens if someone tries to re-read "sample.txt"? The new serialization code is now expecting a boolean "sample.txt" doesn't have.

If, on the other hand the class was implementing using flags, adding the new option just means adding a new constant. Since the physical structure of the class does not change, neither does the serialization, so files can be read , even if they were written before the new option was added. (Note: for this to work, you have to make sure that unused flags are always set to zero.)

One last benefit of flags is that they let you check if a bunch of options are set with a single comparison. For example, suppose your ideal type of hotel has a pool, a gym and laundry facilities, but you don't care about the other options. You can do this with a single check:

vHotelFlags = hotel.getFlags();
vIdealHotel = HAS_POOL | HAS_GYM | HAS_LAUNDRY;
if ( (vFlags & vIdealHotel) == vIdealHotel )
   return true; // This is my ideal hotel

The use of the == vIdealHotel portion of the if statement is very important. In Java, you have to have an == in the if statement, but C the following code will compile:

if (vFlags & vIdealHotel) // don't do this
   return true;

This code, however, does not do the same thing as the previous code does. This if statement will be true if any of the flags vIdealHotel are set vFlags, not just if all of them are set.

Using Masks

Bitwise operations also allow you to use "masks". A mask is a collection of bits that let you pay attention to some parts of a number, but not others. The previous section actually used a mask when checking for an ideal hotel.

For example, continuing the previous situation, say your ideal hotel is one that has a pool, a gym and laundry facilities but does not allow pets. The code the previous section would not let you check for this situation with a single comparison, but you could do so using a mask, like so:

vHotelFlags = hotel.getFlags();
vMask = HAS_POOL | HAS_GYM | HAS_LAUNDRY | ALLOWS_PETS;
vIdealHotel = HAS_POOL | HAS_GYM | HAS_LAUNDRY;
if ( (vFlags & vMask) == vIdealHotel )
   return true; // This is my ideal hotel

In this code, vMask contains all of the flags you want to check, while vIdealHotel contains result you want to see. Using the bitwise and with the mask, all flags that are not part of the mask get completely removed. The result is a number with just the states of those flags the mask.

Masks are also useful even when you are not using flags. You can, for example, use them to extract specific bytes from a number. Say, for example, you have a 32-bit long, but are only interested the lower half of the number (the "low word"). You could do this:

static final int LOW_MASK = 0x0000FFFF;
int lowWord( int theNumber )
{
   return (theNumber & LOW_MASK);
}

How about if you want the high word instead? This is possible, but is slightly more complex because you have to shift the bits as well as use the mask, like so:

static final int HI_MASK = 0xFFFF0000;
int hiWord( int theNumber )
{
   int vHigh = theNumber & HI_MASK;
   return (vHigh >>> 16);
}

Bit Manipulation

The bitwise operations are also very good for just moving bits around. This is particularly important for most encryption algorithms, where rotating and mixing bits is common. Outside of encryption, a typical use is changing the byte order of an integer.

Most computer systems use "big endian" numbers, meaning that, say, the four bytes of an integer are stored in memory with the most significant byte first: AABBCCDD. Intel processors, on the other hand, use "little endian" numbers, with the little end of the bytes first: DDCCBBAA.

Sometimes in cross-platform products (usually when people dump memory to disk or store integer values a binary file stream), you need to swap the byte order. This can be done with bitwise operations. Here is one such implementation (don't use it though, as it is pretty slow and a bit of a hog):

int swapLong( int target )
{
   int b1 = (target & 0xFF000000) >>> 24;
   int b2 = (target & 0x00FF0000) >> 8;
   int b3 = (target & 0x0000FF00) << 8;
   int b4 = (target & 0x000000FF) << 24;
   return (b1 | b2 | b3 | b4 );
}

XOR Magic

The exclusive or (xor) operation allows some really funky things. An exclusive or returns true if either one thing or the other is true, but not both. It can be used to "overlap" two numbers. For example, say you store the result of A ^ B. Later, when you retrieve this result, if you have either A or B, you can reconstruct the number you don't have! Try it out. This forms the basis of a common (and very easy to break) encryption system.

XOR is also found in a mental puzzle: you have two memory locations; can you swap the contents of these memory locations without using any other memory? Using XOR, the answer is yes (say the memory locations are A and B):

A = A ^ B;
B = A ^ B;
A = A ^ B;

Don't believe me? Check it:

Drawbacks of bitwise operations

The main problem with bitwise operations is that not every language offers them. The most glaring example of this is SQL. SQL has no way of performing bitwise operations in where clauses. This, unfortunately, makes using flags stored database fields problematic.

Basically, if you ever need to run a conditional query on a option, you can't store that option inside an integer containing flags. Sucks.

On the other hand, if you don't mind not being able to conditionally query the options, they can be stored in a single flag field. This is often true for things like settings and so on, where the settings affect code but not queries.

Alternatives

Most decent object oriented languages provide some alternatives to bitwise operators that are a little easier to use. Java for example, has the BitSet object.

The standard template library (STL) for C++ also defines a bitset object. Cool versions of STL also provide a special override for the vector<bool> template the uses bits internally.

Using these objects have the following benefits:

• Handles arbitrary numbers of bits, rather than just the 32 in an integer.
• Easier to use. For example telling the object to "set bit 12" is a bit easier to wrap your brain around than "let's see, a constant to set the 12th bit would be... uh... 2048?".
• Usually provides additional useful stuff, such as toString.

Conclusion

Bitwise operations can allow some cool things, but make sure you understand their limitations.

Back to Wordman's Writing page.