Bitwise Operations: Examples

One post that I’ve always loved on stackoverflow is this post by Hugoware which contains some useful extension methods for bitwise operations.

Bitwise operations can be used to perform all kinds of useful calculations. Below are some examples to whet your appetite for knowledge.

1) List of Integers trickery

You may have seen this question somewhere in some form or another: “Given a list of integers of unknown size where all but one integer occurs an even number of times, find the odd integer.”  This is usually a part of some algorithm coding-for-fun puzzle.  When I first came across this question, I tried a number of different ways to loop through a list, none of which were optimal.  In the end, I realized you can use XOR bitwise operations to do this.

First, create a list of integers and set your control integer to 23:

List<int> items = new List<int>();
for (int i = 0; i < 100; i++) {
  items.Add(i);
  if(i == 23) { items.Add(i); }
}

Then, create a value to keep watch, and perform an XOR on every value:

int found = 0;
foreach (int item in items) {
  found ^= item;
}

Finally, output to console or inspect the found variable to be sure it contains the number 23.

Why this works

The complexity of this algorithm is O(n)–one operation per n items. It doesn’t get any easier than that. If you were to add more loops or extra data structures to maintain values, you degrade performance.

If you’ve read my previous post about bitwise operations, you may remember that an XOR toggles the bits. When you start at zero, all even occurrences will be zero when the loop is completed. The only bits left will be the bits from the odd occurrence of an integer (in other words, 0 ^ 23 = 23).

Cool, huh?

2) Division by 2 or 3

This is one of the few things I remember from my Information Systems class at VCU (sorry, Dr. Wynne). My professor work on a project many years ago, trying to debug a performance issue. When running through certain calculations, the application performance would reduce by orders of magnitude. The problem was with how the application was performing division. Sorry, I don’t remember the exact details because I think it was being done in Assembly (I guess I don’t even remember this story from VCU!). The solution was to perform bitwise division on the value. For example:

List<int> items = new List<int>();
for (int i = 0; i < 1000; i+=2) {
	items.Add(i);
}

foreach (int item in items) {
	Console.WriteLine("{0} / 2 = {1}", item, item >> 1);
}

Why this works

Let’s look at a single number, 6. The bits for 6 look like:

0 1 1 0

This means the 2 bit and the 4 bit are set. If you use the right-shift operator (‘»’), you’re moving all of the bits that many positions to the right. So, if you perform ‘6 » 1’, you get:

0 0 1 1

Sure enough, that’s 3!

Now, you may be thinking “How often do I need to divide by 2?” Well, this doesn’t just work for the number 2. You can lop off any number of bits.

x » 2 is the same as x / 4 ( or x / (2^2) ).

x » 3 is the same as x / 8 ( or x / (2^3) ).

And so on…

What if I want to divide by an odd number?!

Then do something like: x / 3. Seriously. If you’re interested, you can take a look at this post on stackoverflow.

What you do in this case is use a magic number which causes the left-most 32bits in a 64bit result to be equal to the result of dividing by 3. Then you shift those 32 insignificant bits off. Be careful, though, because you can easily overflow your value type. Here’s an example:

Console.WriteLine("300 / 3 = {0}", (300L * 1431655766) >> 32 );

If you look at the binary for that magic number (1431655766), you’ll see:

0101 0101 0101 0101 0101 0101 0101 0110

You don’t need to memorize this magic number. You can easily build it:

int result = 0;
for(int i = 1; i<=8; i++) {
   result = (result << 4) ^ 5;
}
result += 1;

This takes the binary representation of 5 (0101) and buffers that nibble until it fills 32 bits, then adds 1 which basically moves the last bit. That’s the magic. We’ve created a magic number which is 6 (110) preceded by alternating 1’s and 0’s.

To see what this is doing in something a little simpler like 6/3=2, you can run this bit of code and inspect the binary displayed.

long tester = 6L * 1431655766;
Console.WriteLine(Convert.ToString(tester, 2).PadLeft(36, '0'));

Notice that I used 36 digits to pad because I know 6/3 is 2 and I only need 4 extra bits to show that. In the binary below, instead of separating each by by a space, I’ve separated the 32 bits we’ll lop off from the end result.

0010 00000000000000000000000000000100

When you shift this result by 32 bits, you’re left with the answer: 2.

Why does this work?

Binary Multiplication.

Take, for example, the magic number multiplied by 243 = 347892351138.

Our answer should be: 243/3 = 81.

01010101010101010101010101010110
            x                         11110011
______________________________________________
              01010101010101010101010101010110
            0 10101010101010101010101010101100
           00 00000000000000000000000000000000
          000 00000000000000000000000000000000
         0101 01010101010101010101010101100000
        01010 10101010101010101010101011000000
       010101 01010101010101010101010110000000
      0101010 10101010101010101010101100000000
______________________________________________
      1010001 00000000000000000000000010100010

As you can see, the end result (the last line) is the binary representation of 81!

3) Obfuscation

You can use XOR or any other bitwise operation to obfuscate a string. The idea is to take a single character, XOR all characters in a sentence with your secret to obfuscate. To deobfuscate, you XOR all characters in your obfuscated string and the result should be your original string!

Here’s a quick example:

char key = '*';
string sentence = "Would you like to play a game?!";
Console.WriteLine("Original string: '{0}'", sentence);

string obfuscated = String.Empty;
foreach (var item in sentence) {
	obfuscated += (char)(item ^ key);
}
Console.WriteLine("obfuscated string: {0}", obfuscated);
string deobfuscated = String.Empty;
foreach (var item in obfuscated) {
	deobfuscated += (char)(item ^ key);
}
Console.WriteLine("deobfuscated string: {0}", deobfuscated);

The output should look something like (non-printing characters are not displayed, so you may see something slightly different):

Original string: 'Would you like to play a game?!'
obfuscated string: }E_FN
SE_
FCAO
^E
ZFKS
K
MKGO
deobfuscated string: Would you like to play a game?!