Abusing C++ exceptions

Java and C# programmers use exceptions all over the place in their programs. C++ programmers have always been rather shy when it comes to exceptions. I’m not a particularly big fan of exceptions, but I find them helpful in getting me out of recursion trees!

The following snippet shows a typical recursive function that aims to find a target value by brute force. I’ve left out the details in order to highlight the most important feature : breaking out of the recursion tree once the value is found.

void go(int i)
{
   if(i == n)
   {
      // Perform calculation
     
      if (resultFound)
      {
         // This breaks out of the entire recursion 
         // tree and goes back to main!
         throw 1;
      }
   }
   else
   {
      state[i] = value1;
      go(i+1);
      state[i] = value2;
      go(i+1);
   }
}

int main()
{
   try {
      go(0);
   } catch(...) {}

   return 0;
}

The magic of bitmasks

Consider the simple problem of iterating over all the subsets of a given set. For years I’ve been using recursion to do this, until I came across this neat trick. The magic is contained in the fact that every integer has a binary form, and we can use the individual bits to represent elements in a set. Confused? Have a look at these numbers :

0, 1, 2, 3, 4, 5, 6, 7

Still doesn’t make sense? Let’s write them out in binary :

000, 001, 010, 011, 100, 101, 110, 111

See something now? Aha! If we use the position of the 1s to correspond to a particular element in a 3-element subset, we have just generated all of it’s subsets by just running through a list of increasing numbers! Well, not quite. There is still the simple matter of using the information in these binary numbers to do the actual listing.

We can check if a particular bit is set by using the bitwise-AND operator. By looking at which bits are set and displaying the element only if it’s corresponding bit is set, we can write a simple subset listing program :

#include <iostream>
using namespace std;

int main()
{
   char arr[] = "abc";

   for(int i=0 ; i<8 ; i++)
   {
      for(int j=0 ; j<3 ; j++)
         if(i & (1<<j))
            cout << arr[j];
      cout << endl;
   }

   return 0;
}

This is a small example that works on a set of 3 elements. How about larger sets? No problem! However, you are bounded by the size of the integer that you use. So if you use a 32-bit integer, you cannot use this trick on sets with more than 31 elements.

Also, keep in mind that a set with N elements has 2^N subsets (including the null subset).

Let’s put this idea into a program that works on strings of variable length :

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
   char arr[50];

   cout << "Enter string : ";
   cin >> arr;

   int len = strlen(arr);

   if(len >= 8 * sizeof(int))
   {
      cout << "String too long!\n";
      return 1;
   }

   for(int i=0 ; i < (1<<len) ; i++)
   {
      for(int j=0 ; j < len ; j++)
         if(i & (1<<j))
            cout << arr[j];
      cout << endl;
   }

   return 0;
}

Gnuplot Cheat Codes

1. Disabling the X-axis

unset xtics

2. Disabling the Y-axis

unset ytics

3. Disabling the border

unset border

4. Plotting a circle

set parametric
plot sin(t), cos(t)

5. Ensuring that both axes use the same scale

set size square

6. Getting rid of legends

plot something notitle