practical applications of bitwise operations

Question

1. What have you used bitwise operations for?
2. why are they so handy?
3. can someone please recommend a VERY simple tutorial?

Answer 1

Although everyone seems to be hooked on the flags usecase, that isn't the only application of bitwise operators (although probably the most common). Also C# is a high enough level language that other techniques will probably be rarely used, but it's still worth knowing them. Here's what I can think of:

---

The << and >> operators can quickly multiply by a power of 2. Of course, the .NET JIT optimizer will probably do this for you (and any decent compiler of another language as well), but if you're really fretting over every microsecond, you just might write this to be sure.

Another common use for these operators is to stuff two 16-bit integers into one 32-bit integer. Like:

int Result = (shortIntA << 16 ) | shortIntB;

This is common for direct interfacing with Win32 functions, which sometimes use this trick for legacy reasons.

And, of course, these operators are useful when you want to confuse the inexperienced, like when providing an answer to a homework question. :)

In any real code though you'll be far better off by using multiplication instead, because it's got a much better readability and the JIT optimizes it to shl and shr instructions anyway so there is no performance penalty.

---

Quite a few curious tricks deal with the ^ operator (XOR). This is actually a very powerful operator, because of the following properties:

• A^B == B^A
• A^B^A == B
• If you know A^B then it's impossible to tell what A and B are, but if you know one of them, you can calculate the other.
• The operator doesn't suffer from any overflows like multiplication/division/addition/subtraction.

A couple of tricks I have seen using this operator:

Swapping two integer variables without an intermediary variable:

A = A^B // A is now XOR of A and B
B = A^B // B is now the original A
A = A^B // A is now the original B

Doubly-linked list with just one extra variable per item. This will have little use in C#, but it might come in handy for low level programming of embedded systems where every byte counts.

The idea is that you keep track of the pointer for the first item; the pointer for the last item; and for every item you keep track of pointer_to_previous ^ pointer_to_next. This way you can traverse the list from either end, yet the overhead is just half that of a traditional linked list. Here's the C++ code for traversing:

ItemStruct *CurrentItem = FirstItem, *PreviousItem=NULL;
while (  CurrentItem != NULL )
{
    // Work with CurrentItem->Data

    ItemStruct *NextItem = CurrentItem->XorPointers ^ PreviousItem;
    PreviousItem = CurrentItem;
    CurrentItem = NextItem;
}

To traverse from the end you just need to change the very first line from FirstItem to LastItem. That's another memory saving right there.

Another place where I use the ^ operator on a regular basis in C# is when I have to calculate a HashCode for my type which is a composite type. Like:

class Person
{
    string FirstName;
    string LastName;
    int Age;

    public int override GetHashCode()
    {
        return (FirstName == null ? 0 : FirstName.GetHashCode()) ^
            (LastName == null ? 0 : LastName.GetHashCode()) ^
            Age.GetHashCode();
    }
}