在位阵列中有效地找到'1'的位置

Question

我正在连接一个测试一组电线的程序,用于开路或短路.该程序在AVR上运行,将测试向量(步进'1')驱动到导线上并接收结果.它将该结果向量与已存储在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等，其中每个都应该映射到目标体系结构上的适当指令，利用位级并行性。

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

如果您的编译器没有实现这些，您仍然可以使用de Bruijn 序列来编写自己的实现。