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?

Solution 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();
    }
}

Solution 2

I use bitwise operators for security in my applications. I'll store the different levels inside of an Enum:

[Flags]
public enum SecurityLevel
{
    User = 1, // 0001
    SuperUser = 2, // 0010
    QuestionAdmin = 4, // 0100
    AnswerAdmin = 8 // 1000
}

And then assign a user their levels:

// Set User Permissions to 1010
//
//   0010
// | 1000
//   ----
//   1010
User.Permissions = SecurityLevel.SuperUser | SecurityLevel.AnswerAdmin;

And then check the permissions in the action being performed:

// Check if the user has the required permission group
//
//   1010
// & 1000
//   ----
//   1000
if( (User.Permissions & SecurityLevel.AnswerAdmin) == SecurityLevel.AnswerAdmin )
{
    // Allowed
}

Solution 3

I don't know how practical, solving a sudoku you consider to be, but let's assume it is.

Imagine you want to write a sudoku solver or even just a simple program, that shows you the board and lets you solve the puzzle yourself, but ensures the moves are legal.

The board itself will most probably be represented by a two-dimensional array like:

uint [, ] theBoard = new uint[9, 9];

Value 0 means the cell is still empty and values from the range [1u, 9u] are the actual values in the board.

Now imagine you want to check if some move is legal. Obviously you can do it with a few loops, but bitmasks allow you to make things much faster. In a simple program that just ensures the rules are obeyed, it doesn't matter, but in a solver it could.

You can maintain arrays of bitmasks, that store information about the numbers that are already inserted in each row, each column a and each 3x3 box.

uint [] maskForNumbersSetInRow = new uint[9];

uint [] maskForNumbersSetInCol = new uint[9];

uint [, ] maskForNumbersSetInBox = new uint[3, 3];

The mapping from the number to the bitpattern, with one bit corresponding to that number set, is very simple

1 -> 00000000 00000000 00000000 00000001
2 -> 00000000 00000000 00000000 00000010
3 -> 00000000 00000000 00000000 00000100
...
9 -> 00000000 00000000 00000001 00000000

In C#, you can compute the bitpattern this way (value is an uint):

uint bitpattern = 1u << (int)(value - 1u);

In the line above 1u corresponding to the bitpattern 00000000 00000000 00000000 00000001 is shifted left by value - 1. If, for example value == 5, you get

00000000 00000000 00000000 00010000

At the beginning, the mask for each row, column and box is 0. Every time you put some number on the board, you update the mask, so the bit corresponding to the new value is set.

Let's assume you insert value 5 in row 3 (rows and columns are numbered from 0). Mask for row 3 is stored in maskForNumbersSetInRow[3]. Let's also assume that before the insert there were already numbers {1, 2, 4, 7, 9} in row 3. The bit pattern in the mask maskForNumbersSetInRow[3] looks like this:

00000000 00000000 00000001 01001011
bits above correspond to:9  7  4 21

The goal is to set the bit corresponding to the value 5 in this mask. You can do it using bitwise or operator (|). First you create a bit pattern corresponding to the value 5

uint bitpattern = 1u << 4; // 1u << (int)(value - 1u)

and then you use the operator | to set the bit in the mask maskForNumbersSetInRow[3]

maskForNumbersSetInRow[3] = maskForNumbersSetInRow[3] | bitpattern;

or using shorter form

maskForNumbersSetInRow[3] |= bitpattern;

00000000 00000000 00000001 01001011
                 |
00000000 00000000 00000000 00010000
                 =
00000000 00000000 00000001 01011011

Now your mask indicates that there are values {1, 2, 4, 5, 7, 9} in this row (row 3).

If you want to check, if some value is in the row, you can use operator & to check if corresponding bit is set in the mask. If the result of that operator applied to the mask and a bit pattern, corresponding to that value, is non-zero, the value is already in the row. If the result is 0 the value is not in the row.

For example, if you want to check if value 3 is in the row, you can do that this way:

uint bitpattern = 1u << 2; // 1u << (int)(value - 1u)
bool value3IsInRow = ((maskForNumbersSetInRow[3] & bitpattern) != 0);

00000000 00000000 00000001 01001011 // the mask
                 |
00000000 00000000 00000000 00000100 // bitpattern for the value 3
                 =
00000000 00000000 00000000 00000000 // the result is 0. value 3 is not in the row.

Below are methods for setting a new value in the board, maintaining appropriate bitmasks up to date and for checking if a move is legal.

public void insertNewValue(int row, int col, uint value)
{

    if(!isMoveLegal(row, col, value))
        throw ...

    theBoard[row, col] = value;

    uint bitpattern = 1u << (int)(value - 1u);

    maskForNumbersSetInRow[row] |= bitpattern;

    maskForNumbersSetInCol[col] |= bitpattern;

    int boxRowNumber = row / 3;
    int boxColNumber = col / 3;

    maskForNumbersSetInBox[boxRowNumber, boxColNumber] |= bitpattern;

}

Having the masks, you can check if the move is legal like this:

public bool isMoveLegal(int row, int col, uint value)
{

    uint bitpattern = 1u << (int)(value - 1u);

    int boxRowNumber = row / 3;
    int boxColNumber = col / 3;

    uint combinedMask = maskForNumbersSetInRow[row] | maskForNumbersSetInCol[col]
                        | maskForNumbersSetInBox[boxRowNumber, boxColNumber];

    return ((theBoard[row, col] == 0) && ((combinedMask & bitpattern) == 0u);
}

Solution 4

Dozens of bit twiddling examples here

The code is in C, but you can easily adapt it to C#

Solution 5

If you ever need to communicate with hardware you'll need to use bit twiddling at some point.

Extracting the RGB values of a pixel value.

So many things

View more solutions

Comments

[phuclv]

Real world use cases of bitwise operators

[C.J.]

whoops, I just now saw you tagged this C#, I thought it was C++. ... must read slower ... :)

[Alex Gordon]

@justin, thank you very much. can you please explain this User.Permissions = SecurityLevel.SuperUser | SecurityLevel.AnswerAdmin;

[Dave]

These are just flagged enums.

[Justin Niessner]

@jenny - Added clarification in the code comments.

[Justin Niessner]

@Dave - Exactly. But when you use Flagged Enums, you are using Bitwise Operators to do the checks against the values. Handy and fairly simple. In my opinion, exactly what the OP asked for.

[Justin Niessner]

Technically, bit-shift operators can't be considered bit-wise operators. Check out the bit-shift section of the Wikipedia article as to why: en.wikipedia.org/wiki/Bitwise_operation

[Reed Copsey]

@Justin: Though now obsolete, given Enum.HasFlag: msdn.microsoft.com/en-us/library/system.enum.hasflag.aspx

[Justin Niessner]

@Reed - True. It's still useful as an example (since I'm guessing the implementation of Enum.HasFlags does this internally).

[Dave]

@Justin: of course, I just should have specified that I was talking to OP, who evidently didnt look into anything I linked too :)

[NotMe]

@Dave: you had links in your post? ;)

[Mark]

Really interesting stuff but kinda blew over my head a bit. Seems like maybe a little build out of what is going on here might be in order (some comments with bit examples). The bit shift in building the mask and such is a little boggling to me. Just asking since you clearly put some time into the answer.

[Dave]

@Chris: yea if u didn't notice :-P

[Grozz]

+1, beautiful xor swap. Thank you.

[snemarch]

+1 for the xor-list approach, hadn't seen that before.

[Alex Gordon]

interesting that this was labelled not constructive :)

[Davos]

"when you want to confuse the inexperienced" +1 for nailing the MO of way too many senior devs / architects. I truly thought that with experience would come humble pragmatism, but alas no. Brogrammers have taken over and the world is worse for it.

[Davos]

and this +1000 "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." Why is code golf so prevalent in real code?