Algorithm to determine if a combination of state is set

Introduction

An algorithm to determine if a combination of state is set by storing a single value using binary arithmetic.

Background

There are times when we need to check if a particular state is set or not for an entity where the entity can be associated with any combination of states. This can be done using binary arithmetic by storing a single value representing the combination of different states and checking against this value to determine if a particular state is set or not.

Sample Use Case

Imagine that your application allows several tags to be associated to a Folder entity. A Folder can have any combination of Tags set. One way to do this will be to store keys for both Folder and its Tags in a table. When we need to query if a particular tag is set for a Folder we check in this table if there are any records existing for the combination. A relational table structure would look like this:

Folders{FolderID, FolderName}
Tags{TagId, TagName}
FolderTags{Id, FolderId, TagId}

Solution

Give unique values to the tags in the sequence of 1, 2, 4, 8, 16 etc. (i.e. powers of 2) and store the tag combination as the BitWiseOr for the particular Folder. To determine if a folder has particular tag the BitWiseAnd operation should give back the same tag value. The tables would look like:

Folders{FolderID, FolderName, Tags}
Tags{TagId, TagName, TagValue}

Example

Assume the following tags:

When a new folder is created we have an entry such as follows:

"Confidential" tag is added, the row becomes

"Offical" tag is added, the row becomes (BitWiseOr - 2 | 8)

Check if the folder has "Official" tag:

10 & 8 (BitWiseAnd gives 8 this implies folder has this tag)

Check if the folder has "Personal" tag:

10 & 4 (BitWiseAnd gives 0 this implies folder doesn't have this tag)

Points of Interest

This uses some simple binary arithmetic to check the inclusion or exclusion of defined flags. The pros are, we only need to store the combination of statues as a single field and the inclusion of exclusion can be checked with a single query. The con is, this approach will work well if the number of tags is less, going above 63 tags could reach the limits of long integer.