神刀安全网

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 it 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 Access

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.

Usage

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

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).

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Understanding Bit masks

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址