使用位掩码进行计数

Question

我希望找到一种列举符合特定位掩码的值的方法。

例如，我想枚举所有包含模式0xb5的字节。

一个简单的C程序可以实现这个功能：

#include <stdio.h>
#include <stdint.h>

/* prints out b5, b7, bd, bf, f5, f7, fd, ff */
int main(int argc, const char ** argv) {    
    const uint8_t mask = 0xb5;
    uint8_t i = 0;

    while(true) {
        if((i & mask) == mask) printf("%x\n", i);
        if(i == UINT8_MAX) break;
        i++; /* Replace by something smarter. */
    }    
    return 0;
}

无论使用什么掩码，这个循环都会迭代UINT8_MAX次。有没有一个巧妙的位操作技巧可以自动将i增加到满足掩码的下一个值？

- Philippe

---

你可以确定掩码中有多少个零位，然后按需分配位数进行计数。虽然这肯定不会比朴素的解决方案更快。 - Oliver Charlesworth

你至少应该使用 i = mask 而不是 i = 0。 - Steen

你的程序出现了无限循环！ - Oliver Charlesworth

@OliverCharlesworth 谢谢！非常感谢您尝试修复我的一位偏差错误。 - Philippe

Answer 1

你可以仅通过“通配符位”进行计数，如下所示：

（您需要使用“通配符位”来进行计数）

x = (x + 1) | pattern;

假设您从pattern（通配符位全部为零）开始。

这里的想法是“模式位”为1，因此当您加1时，进位（如果有）会通过它们传递到“通配符位”的下一部分。当然，当进位经过时，会将“模式位”置为0，所以它们被放回去。

- harold

---

谢谢，这正是我在寻找的。比我担心的要简单得多。 - Philippe

Answer 2

你可以使用 i = ((i << 1) | 1); 替代 i++

- Logicrat

---

他第一次匹配的地址将是0xb5。使用您的公式，下一个i应该是0x16B，并且会错过与掩码匹配的0xf5。 - Christophe

我是否误解了问题？在我看来，i会取值1、3、7、15、31、63、127、255，因此每次迭代只需打开一个更多的位。 - Logicrat

@Logicrat 应该是 b5、b7、bd、bf、f5、f7、fd、ff。 - harold

Answer 3

对@harold所说的主题有轻微变化，表述得很好。

while (1) {
  printf("%x\n", i);  // no need for mask test
  if (i == UINT8_MAX)
    break;
  do {
    i++;
   } while ((i & mask) != mask);
}

- chux - Reinstate Monica

---

我认为那并没有真正回答这个问题。 - harold

更新帖子，将i++替换为“更智能的东西”。 - chux - Reinstate Monica