Binary representation and dynamic Flags

Flags are great for representing multiple information in a single digit.

For example, I could define the numbers 1, 2, 4, and 8 to have the semantics:

1: Coffee
2: Sugar
4: Milk
8: Icecream

Here the number 5 would represent Coffe and Milk. The number 8 would represent Coffe and Icecream. Now, the beauty of this is that using base 2 digits Coffee would look like this:

1

If I added sugar, it would now look like this:

11

And if I added Icecream it would now look like this:

1011

I.e. reading from the right to the left: Coffe, Sugar, No milk, but including Icecream.

In other words – it will be very performant to determine from an integer, even if the integer is a bit large, which integer flags it is based on. In order to do this in .NET, however, one has to be able to (1) convert from decimal to base 2 binary, and (2) to convert the single bits to integers.

Two short extension methods are helpful here:


public static class Int32Extensions
{
  public static Boolean[] ToBinary(this Int32 dec)
    {
      List lst = new List();
      while (dec > 0)
      {
        lst.Add(dec % 2 != 0);
        dec /= 2;
      }
    return lst.ToArray();
  }

  public static List GetFlagValues(this Int32 flagRepresentation)
  {
    List lst = new List();
    Boolean[] bs = flagRepresentation.ToBinary();
    for (Int32 i = 0; i < bs.Length; i++)
      if (bs[i]) lst.Add((Int32)Math.Pow(2, i));
    return lst;
  }
}

Now, the implementation can be used like this:


Int32 i = 1000000000;
Boolean[] s = i.ToBinary();
foreach (Int32 f in i.GetFlagValues())
{
  Console.WriteLine(f);
}

In the console this will displayed as:

Obviously, since the value doubles for each additional flag, there is a natural limit to the possible number of flags. However, this limit can be extended by using a datatype like BigInteger in C# 4.0 (remember to reference System.Numerics).

With 10.000 different flags, my pc will calculate each flag within 156 milliseconds. However, please be aware that calculations on such large numbers can be a thread to scalability. 20.000 different flags still perform within half a second (on my pc), but 100.000 flags will perform within 13 seconds – with noticeable impact on other processes on the pc.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s