Taking a Byte Out of BitMasks

BitMasking is a technique that allows you to store multiple values in a single Byte. Yes, you read that right – more than one property value in a single byte of memory.

“How does this work?” you may ask. Well, it all has to do with how math works with Bits. As you probably know all the Bits in a Byte are 0s or 1s. When you add two 0s the result is 0 when you add two 1s the answer is also 0 but the next bit is set to 1. Add a 1 and a 0 and – you guessed it – the result is a 1.

The really cool thing is that because each byte is mapped to only one power of 2 you can reliably identify if a unique byte value is included in a byte. You can “pack” a byte with more than 1 byte def and then “test” if that value is included in the “packed byte.”

So What

I usually use this technique to store multlple Enums in a single Enum property of an object. In order for this to work you must define your Enum as powers of 2.

Uh … 2 Divisions? We can’t do that… Can we?

Suppose you want to maintain what division an Employee works in or manages. First you define a Enum to identify the Divisions.

public enum Divisions
{
       NotAssigned = 0,
       PersonalProducts = 1,
       Industrial = 2,
       Childrens = 4,
       Experimental = 8,
       TopSecret = 16
 }
Note how the Enums are specifically declared as powers of 2

Next you create your Employee class and create the Division property which is defined as your Enum type.

public Divisions Division { get; set;}

Now in your code you can assign and test what Division the Employee has been assigned to using your tidy Enum.

_employees.Add(new Employee() { Name = "Karl", Division = Divisions.TopSecret });
_employees.Add(new Employee() { Name = "Carol", Division = Divisions.Industrial });

Nice, right?

But wait! What happens if Carol is promoted and becomes the manager of the TopSecret Division while still maintaining her position in the Industrial Division?

One solution might be to create Boolean flags within the Employee class that represent each Division. Maybe you could create a Hash with the Division as the Key and a bool as the Value? Furthermore, what happens when new Divisions are created? You would have to update the Hashes or add new properties. Yuck!

You get the picture. Is there a way to do it without adding new properties? Well the answer is “Yes!” It turns out that you can “add” multiple Divisions to the Employee.Division property and still be able to determine the unique Divisions for the Employee.

A Bit of Math

If Carol is currently in the Industrial Division her Employee.Division = 2. That’s because we defined the Divisions Enum as Powers of 2 and explicitly set Industrial = 2.

The TopSecret Division has a value of 16, so if we add that to Carol’s current Division value she ends up with Division = 18. (16 + 2)

So think about this for a sec – If we know that the max value of the Divisions Enum == 16 and Carol.Division > 16, Carol must be in more than one Division. In fact, since we used only powers of 2 in our definitions there is only one combination of Divisions that totals a value of 18!

  • This assumes that a Division can be only added once to an Employee.
    Ex. Employee.Division = 6 should not be Industrial 3 times!

Here’s how it works under the covers –

Industrial 2 0000 0010
Top Secret 16 0000 1000
added/combined 18 0000 1010

The way you add the bytes is by using one of the “Bitwise” operators.

Divisions division = Divisions.Industrial | Divisions.TopSecret;

To add 2 bytes you use the bitwise OR – |. This makes sense when you think about it because you are trying to get 00 | 00 = 00, 01 | 00 = 01, 00 | 01 = 01 and 01 | 01 = 11.

Not surprisingly you can also subtract a byte. To do this you use the EXCLUSIVE-OR – ^ operator which only returns 1 (true) if only 1 of the operands is true.

00 ^ 00 = 00, 01 ^ 00 = 01, 00 ^ 01 = 01 and  01 ^ 01 = 00.

division = division ^ Divisions.TopSecret;   // would “remove” TopSecret
Combined Division 18 0000 1010
Top Secret 16 0000 1000
^ (notice the result is Industrial ) 2 0000 0010

Now this is the really awesome part. You can use the AND – & bitwise operator to apply the “mask” of the value you are looking for. The bitwise & returns true only when both operands are true. This quality of & can be used to check if the bits you are looking for are currently set!

00 & 00 = 00, 01 & 00 = 00, 00 & 01 = 00 and 01 & 01 = 01

// Carol is in the Top Secret Division if true! 
if ((Carols.Division & Divisions.TopSecret) == Divisions.TopSecret)
Combined Division 18 0000 1010
Looking for Top Secret 16 0000 1000
& (notice the result is TopSecret ) 16 0000 1000
Combined Division 18 0000 1010
Looking for Industrial 2 0000 0010
& (notice the result is Industrial ) 2 0000 0010
Combined Division 18 0000 1010
Looking for Personal Products 1 0000 0001
& (notice the result is NOT Personal Products ) 19 0000 1011