How to efficiently check against bitmask?

Question

I am using inotify and want to efficiently check against the reported bitmask event (see inotify man page).

Now I could brutely check against every bit on every event, but that would be extremely crude, if not stupid, as I would have N conditionals every time. Or is calling

( bitmask & mask ) == mask

for each mask already super efficient?

Since the resulting bitmask is basically just a well defined number, I should be able to use basic arithmetic operations for this. But before I think up something myself, I wanted to ask if there is a well-known, efficient way to check against a given bitmask. So, is there?

Answer 1

If you want to check against one bitmask, then

if ((value & mask) == mask)

will give you an exact match ("all bits in the mask"), and

if ((value & mask) != 0)

will supply a loose match ("any bit in the mask"). The compiler will further optimize the check against zero.

If you have several bitmasks, you want to extract the maximum information out of each check in the time domain (an extreme case: if all the values you get are certainly odd, you needn't check the 0th bit at all. It will always be 1). Ideally you need to identify a first round of bits that have a 50% probability of being 1.

In both groups you then identify a subgroup (probably not the same in the two cases) with the same chance.

if ((value & SPECIAL_MASK_1) == SPECIAL_MASK_1) {
    if ((value & SPECIAL_MASK_2) == SPECIAL_MASK_2) {
        ...
    } else {
        ...
    }
} else {
    if ((value & SPECIAL_MASK_3) == SPECIAL_MASK_3) {
        ...
    } else {
        ...
    }
}

If you had, say, 32 states, each mapped to one bit, and only one bit can be set at each call - the easiest case - the "serial" sequence would be one of 32 checks one after the other

if ((mask & 0x00000001) == 0x00000001) {
} else if ((mask & 0x00000002) == 0x00000002) {
}
...

and a first simple optimization would to place the checks for the most frequent occurrences first. Say that one case out of three the seventh bit is set; you put the check for the seventh bit first.

This way you will end up doing only one check 33% of the time; then maybe two checks another 20% of the time, ..., and in the end on average you might run, say, seven checks.

Another possibility is

if (mask & 0x0000FFFF) {
    // The bit is in the LSW
    if (mask & 0x0000FF00) {
        // MSB of LSW
        if (mask & 0x0000F000) {
            ...
        } else {
        }
    }
} else {
}

This will run every time exactly five checks. At that point, however, considerations about the CPU architecture, branch prediction etc. are likely to trump any optimization you might attempt to do.

Unless you have a very complex setup, or some other constraint (e.g. embedded device), I fear that the cost of analyzing, building, debugging and maintaining an "optimized" versus "brute force" check is likely to more than balance any advantage you could squeeze out of the former.