c - 在位数组中有效地查找 '1' 的位置

Question

我正在连接一个测试一组电线开路或短路的程序。该程序在 AVR 上运行，将测试 vector (行走的“1”)驱动到电线上并接收返回结果。它将生成的 vector 与已存储在 SD 卡或外部 EEPROM 上的预期数据进行比较。

这是一个例子，假设我们有一组 8 根电线，所有这些电线都是直通的，即它们没有连接点。因此，如果我们驱动 0b00000010，我们应该收到 0b00000010。

假设我们收到 0b11000010。这意味着 7,8 号线和 2 号线之间存在短路。我可以通过 0b00000010 ^ 0b11000010 = 0b11000000 检测到我感兴趣的位。这清楚地告诉我 7 号线和 8 号线有问题，但我如何在大型位数组中有效地找到这些“1”的位置。使用位掩码仅对 8 条线执行此操作很容易，但我正在开发的系统必须处理多达 300 条线(位)。在我开始使用如下宏并测试 300*300 位数组中的每一位之前，我想在这里询问是否有更优雅的解决方案。

 #define BITMASK(b) (1 << ((b) % 8))
 #define BITSLOT(b) ((b / 8))
 #define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
 #define BITCLEAR(a,b) ((a)[BITSLOT(b)] &= ~BITMASK(b))
 #define BITTEST(a,b) ((a)[BITSLOT(b)] & BITMASK(b))
 #define BITNSLOTS(nb) ((nb + 8 - 1) / 8)

只是为了进一步展示如何检测开路。预期数据:0b00000010，接收数据:0b00000000(电线未拉高)。 0b00000010 ^ 0b00000000 = 0b0b00000010 - 电线 2 开路。

注意:我知道测试 300 根电线不是 AVR Mega 1281 内的微型 RAM 可以处理的，这就是为什么我将其分成几组，即测试 50 根电线，比较，显示结果，然后继续。

Answer 1

许多体系结构都提供了特定的指令来定位字中的第一个设置位，或者计算设置位的数量。编译器通常为这些操作提供内部函数，因此您不必编写内联汇编。例如GCC，提供了__builtin_ffs、__builtin_ctz、__builtin_popcount等，每一个都应该映射到目标架构上合适的指令，利用位级并行性。

如果目标体系结构不支持这些，则编译器会发出高效的软件实现。在软件中逐位测试 vector 的简单方法效率不高。

如果您的编译器没有实现这些，您仍然可以使用 de Bruijn sequence 编写您自己的实现代码.