如何有效地检查位掩码？

Question

我正在使用 inotify 并希望有效地检查报告的位掩码事件（参见 inotify man page）。

现在我可以粗暴地检查每个事件的每一点，但如果不是愚蠢的话，那将是非常粗鲁的，因为我每次都会有 N 个条件。或者正在打电话

( bitmask & mask ) == mask

for each mask 已经超级有效了吗？

由于生成的位掩码基本上只是一个明确定义的数字，我应该能够为此使用基本的算术运算。但在我自己想出一些东西之前，我想问一下是否有一种众所周知的、有效的方法来检查给定的位掩码。那么，有没有？

Answer 1

如果需要检查每个位掩码，除了显式检查之外别无他法。但是，如果已知具体的位掩码，则可以进行按位检查，从而有效地排除每一步中一半可能的位掩码。

Answer 2

如果你想检查一个位掩码，那么

if ((value & mask) == mask)

将为您提供完全匹配 ("all bits in the mask")，而

if ((value & mask) != 0)

将提供松散匹配 ("any bit in the mask")。编译器将进一步优化对零的检查。

如果你有多个位掩码，你想从时域中的每个检查中提取最大信息（极端情况：如果你得到的所有值都是肯定奇数, 你根本不需要检查第 0 位。它总是 1)。理想情况下，您需要确定第一轮有 50% 概率为 1 的位。

然后在这两个组中，您以相同的机会确定一个子组（在这两种情况下可能不相同）。

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 {
        ...
    }
}

如果你有，比方说，32 个状态，每个都映射到一位，并且每次调用只能设置一位 - 最简单的情况 - "serial" 序列将是 32 个检查之一另一个

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

第一个简单的优化是首先检查最频繁出现的情况。假设设置了三分之一的第七位；你先检查第七位。

这样你最终会在 33% 的时间内只做一次检查；然后也许还有 20% 的时间进行两次检查，...，最后平均你可能运行，比方说，七次检查。

另一种可能是

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

这将运行每次检查五次。然而，到那时，关于 CPU 体系结构、分支预测等的考虑可能会胜过您可能尝试进行的任何优化。

除非你有一个非常复杂的设置，或一些其他限制（例如嵌入式设备），否则我担心分析、构建、调试和维护一个"optimized" 与 "brute force" check 相比，check 可能会平衡你可以从前者中挤出的任何优势。

Answer 3

为了检查掩码的多个位，我使用了一个循环。如果您使用的是一个不错的编译器，它应该相当不错地优化代码。除非您有严重的性能问题，否则不值得手动优化，因为我所知道的所有 CPU 都在一条指令中实现逻辑位测试或按位 AND 操作。所以你有两条指令：逻辑指令和每个位的 CPU 分支条件指令。运行的代码量并不大，而且据我所知，这是无法击败的。（请注意，由于 mask 是 32 位宽，如果您运行宁在 16 位内核 CPU 上，将会有更多的指令来测试两半。）

void processEvents(uint32_t events)
{
    uint32_t bitToTest;
    // Check each bit in turn
    for(bitToTest = 1; bitToTest < events; bitToTest << 1)
    {
        // Check which bit is set.  If none then the default case is used.
        switch(bitToTest & events)
        {
            case IN_ACCESS:
                // Handle the IN_ACCESS event flag here.
                break;
            case IN_ATTRIB:
                // Handle the IN_ATTRIB event flag here.
                break;
            // Et cetera...
            default:
                // No flag was set, so do nothing.
                break;
        }
    }
}

Answer 4

如果只设置了一个位并且您的代码不需要可移植，则可以使用内在函数为您提供设置位的位置，然后在 switch 语句中使用结果。对于 gcc，例如成为

__builtin_ffs

如何有效地检查位掩码？

How to efficiently check against bitmask?

c++

c

bit

bitmask