Understanding Bit masks

Bit masks enable the simultaneous storage and retrieval of multiple values using one variable. This is done by using flags with special properties (numbers that are the powers of 2). It becomes trivial to symbolize membership by checking if the bit at a position is 1 or 0.

How bitmasks works

Masking employs the bitwise OR and AND operations to encode and decode values respectively.

New composite values are created by a bitwise OR of the original composite and the predefined flag. Similarly, the bitwise AND of a composite and a particular flag validates the presence / absence of the flag.

Assuming we start off with decimal values 1,2,4 and 8. The table below shows the corresponding binary values.

Decimal	Binary
0	0000
1	0001
2	0010
4	0100
8	1000

The nice thing about this table is that the four bits allow you to represent all numbers in the range 0 – 15 via combinations. For example, 5 which is binary 101, can be derived in two ways.

5     -> 1 + 4

or

101 -> 0001 | 0100

       -> 0101

7 which is 111 can also be derived in the same form.

Since any number in a range can be specified using these few ‘base’ numbers, we can use such a set to model things in the real world. For example, let’s say we want to model user permissions for an application.

Assuming the base permissions are read, write and execute, we can map these values to the base numbers to derive the table below:

Permissions	Decimal	Binary
None	0	000
Read	1	001
Write	2	010
Execute	4	100

Users of the application will have various permissions assigned to them (think ACL). Thus a potential model for visitor, reader, writer and admin roles with our base permissions is:

Role	Permissions	Decimal	Binary
Visitors	None	0	000
Readers	Read	1	001
Writers	Read + Write	3	011
Admins	Read + Write + Execute	7	111

Noticed a pattern yet?

All the binary values can be obtained by ‘OR-ing’ the base binary values. For example, admins who have read, write and execute permissions have the value obtained when you do a bitwise OR of 1, 2 and 4.

The UNIX model uses the same numbering system. E.g. 777 translates into 111 111 111 which grants owners, groups and others read, write and execute permissions.

Checking Permissions via Bitmasks

Now, the next question is how do you check if a composite value contains a particular flag? Going back to the binary data basics, this means checking if a bit at some position is a 1 or 0.

The bitwise AND operator comes in handy here – it guarantees a 1 when both values sharing the same index are 1 and 0 in all other cases. Thus, ‘AND-ing’ a composite value and the desired flag would reveal the desired outcome. If we get a value greater than zero as the result, then the user has the permission, otherwise a zero means there is no permission.

The admin role has a bitmask value of 111. To check if he really ‘has’ the execute permission we do a bitwise AND of 111 and the execute flag 100. The result is 100 which proves the permission.

More tables! The two tables show how to check for 2 users; one with the read + write + execute (111) permissions and another with the read and execute (101) permissions.

Read + Write + Execute (111)

Permissions	111 bitmask	Binary	Has permission?
Read	111	001	Yes: 111 & 001 → 1
Write	111	010	Yes: 111 & 010 → 1
Execute	111	100	Yes: 111 & 100 → 1

Read + Execute (101)

Permissions	101 bitmask	Binary	Has permission?
Read	101	001	Yes: 101 & 001 → 1
Write	101	010	No: 101 & 010 → 0
Execute	101	100	Yes: 101 & 100 → 1

See? Such a simple way to check without having to make unnecessary calls to the server.

How to apply Bitmasks

This post shows the permission model however bit masks can be applied a wide variety of scenarios. Possible examples include checking membership, verifying characteristics and representing hierarchies.

A possible use in games could be to verify the various power-ups an actor has and to add new ones rapidly. Eliminates the need to iterate, use the bitmask.

Hierarchical models, where higher members encompass lower ones (e.g. the set of numbers) can also be adequately modeled using bitmaps.

Language support for Bitmasks

Explicit language support is not needed to use bitmasks, the rules to know are:

• Use increasing powers of 2 – ensures there is only one flag at the right spot
• Create basic building blocks that are easy to extend and combine
• Remember to watch out for overflows and use values that are large enough to hold all possible bit values. For example, C‘s uint_8 / unsigned char can only hold 8 different flags, if you need more, you’d have to use a bigger value.

Some languages provide extra support for bit mask operations. For, example, C# provides the enum FlagsAtribute which implies that the enum would be used for bit masking operations.

Teaser

Q: Why not base 10? After all, we could use 10, 100, 1000 etc.

A: The decimal system falls short because you can have ten different numbers in one position. This makes it difficult to represent the binary ON/OFF state (which maps well to 0/1).