c++ - 如何有效地检查位掩码？

Question

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

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

( bitmask & mask ) == mask

对于每个 掩码已经 super 有效？

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

Answer 1

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

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 架构、分支预测等的考虑可能会胜过您可能尝试进行的任何优化。

除非你有一个非常复杂的设置，或一些其他限制(例如嵌入式设备)，否则我担心分析、构建、调试和维护“优化​​”与“蛮力”的成本check 可能不仅仅是平衡你可以从前者中挤出的任何优势。