如何高效地检查位掩码？

Question

我正在使用inotify，并希望高效地检查报告的位掩码事件（请参见inotify手册页面）。

现在，我可以暴力检查每个事件上的每个位，但这将极为粗略，甚至愚蠢，因为每次我都会有N个条件语句。或者，是否调用

( bitmask & mask ) == mask

对于已经非常高效的每个掩码？

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

- alex

---

请问您能否澄清一下输入和输出是什么（特别是输入是什么）？ - barak manos

如果您想为每个掩码设置不同的行为，您需要逐个检查每个掩码。如果您想知道一组掩码是否匹配，可以使用 | 运算符。 - Ari

同时，(bitmask & mask) == mask 有点多余。如果掩码位为真，它将简化为 true == true。 - Ari

@Ari 你需要与掩码进行比较，否则当掩码为0时会得到不正确的结果。 - didito

Answer 1

如果您想检查一个比特掩码 one，那么

if ((value & mask) == mask)

会给你一个精确匹配（即“掩码”中的所有位），并

if ((value & mask) != 0)

会提供一个宽松的匹配（“掩码中的任何一位”）。编译器将进一步优化对零的检查。

如果您有多个位掩码，您希望从每个时间域的检查中提取最大信息（一个极端情况：如果您得到的所有值都肯定是奇数，则根本不需要检查第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个状态，每个状态都映射到一个比特位，并且每次只能设置一个比特位——最简单的情况——则“串行”序列将是一个接一个地进行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架构、分支预测等方面的考虑可能会胜过您可能尝试进行的任何优化。

除非您有一个非常复杂的设置或其他限制（例如嵌入式设备），否则我担心分析、构建、调试和维护“优化”与“暴力”检查之间的成本很可能会超过您可以从前者中挤出的任何优势。

- LSerni

---

"...分析、构建、调试和维护“优化”与“暴力”检查的成本很可能会超过前者所能带来的任何优势。" 这非常令人放心。我想我会坚持采用更易读的方法。谢谢你的出色回答！ - alex

Answer 2

检查掩码的多个位时，我使用循环。如果你使用的是一个好的编译器，它应该会相当优化代码。除非你有显著的性能问题，否则不值得手动优化，因为我所知道的所有CPU都实现了单指令逻辑位测试或位与运算。所以你有两个指令：逻辑指令和每个位的CPU分支条件指令。要运行的代码量并不大，而且据我所知，不可能超越。（注意，由于掩码宽度为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;
        }
    }
}

- Evil Dog Pie

---

我希望我能够接受多个答案......最终我使用了您的存根变体来解决我的实际问题（inotify），但@lserni的答案非常全面地回答了我的一般性问题，所以功劳归功于他。但请放心，您至少是我今天的英雄！;) - alex

Answer 3

如果只有一个位被设置，并且您的代码不需要具备可移植性，您可以使用指令集来获取已设置位的位置，然后在switch语句中使用结果。

例如，对于gcc可以这样操作：

__builtin_ffs

- MikeMB

Answer 4

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

- Codor