在位数组中有效地找到’1’的位置
我正在连接一个测试一组电线的程序，用于开路或短路。 该程序在AVR上运行，将测试向量（步行’1’）驱动到导线上并接收结果。 它将此结果向量与已存储在SD卡或外部EEPROM中的预期数据进行比较。
这是一个例子，假设我们有一组8条线，所有这些线都是直通的，即它们没有连接点。 因此，如果我们驱动0b00000010，我们应该收到0b00000010。
假设我们收到0b11000010。 这意味着线7,8和线2之间存在短路。我可以通过0b00000010 ^ 0b11000010 = 0b11000000检测我感兴趣的位。 这告诉我显然线7和8有故障，但我如何在一个大的位arrays中有效地找到这些’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线，比较，显示结果然后向前移动。
许多体系结构提供了用于定位字中的第一个设置位或用于计数设置位数的特定指令。 编译器通常为这些操作提供内在函数，因此您不必编写内联汇编。 例如，GCC提供__builtin_ffs ， __builtin_ctz ， __builtin_popcount等，每个应该映射到目标体系结构上的适当指令，利用位级并行性。
如果目标体系结构不支持这些，则编译器会发出有效的软件实现。 在软件中逐位测试矢量的天真方法效率不高。
如果您的编译器没有实现这些，您仍然可以使用de Bruijn序列编写自己的实现。
你经常发生故障吗？ 如果你不经常发现它们，那么优化“存在故障”的情况似乎毫无意义 – 对于速度而言真正重要的唯一部分是“无故障”情况。
要优化无故障情况，只需将实际结果与预期结果进行异或，并input ^ expected == 0 test以查看是否设置了任何位。
您可以使用类似的策略来优化“少数故障”情况，如果您进一步预期故障的数量通常很小 – 当它们存在时 – 屏蔽input ^ expected以获得前8位，只是第二位8位，依此类推，并将每个结果与零进行比较。 然后，您只需要搜索不等于零的设置位，这应该将搜索空间缩小到可以很快完成的事情。
您可以使用查找表。 例如，255字节的log-base-2查找表可用于查找字节中最重要的1位：
uint8_t bit1 = log2[bit_mask];
其中log2的定义如下：
uint8_t const log2[] = { 0, /* not used log2[0] */ 0, /* log2[0x01] */ 1, 1 /* log2[0x02], log2[0x03] */ 2, 2, 2, 2, /* log2[0x04],..,log2[0x07] */ 3, 3, 3, 3, 3, 3, 3, 3, /* log2[0x08],..,log2[0x0F */ ... }
在大多数处理器上，这样的查找表将转到ROM。 但是AVR是哈佛机器并且将数据放置在代码空间（ROM）中需要特殊的非标准扩展，这取决于编译器。 例如，IAR AVR编译器需要使用扩展关键字__flash。 在WinAVR（GNU AVR）中，您需要使用PROGMEM属性，但它比这更复杂，因为您还需要使用特殊的宏来从程序空间读取。
我认为只有一种方法可以做到这一点：
- 创建一个“outdata”数组。 例如，arrays的每个项目对应于8位端口寄存器。
- 在电线上发送outdata。
- 将此数据读回“indata”。
- 将indata存储在与outdata完全相同的数组中。
- 在循环中，将outdata的每个字节与indata的每个字节进行异或。
我强烈建议使用内联函数而不是那些宏。
为什么你的MCU不能处理300线？
300/8 = 37.5字节。 圆形到38.它需要存储两次，outdata和indata，38 * 2 = 76字节。
你不能节省76个字节的RAM？
我想你错过了穿过树林的森林。 好像是一张钉床测试。 首先测试一些假设：1）您知道每个测试/通电的引脚应该有哪些引脚。 2）您将步骤1中的网表翻译成sd上的文件
如果您在字节级别和位上操作，则可以简化问题。 如果激活引脚，则文件中会存储预期的模式。 首先找到不匹配的字节; 识别字节中不匹配的引脚; 最后存储带有错误引脚编号的通电引脚。
您不需要用于搜索或结果的数组。 大概的概念：
numwires=300; numbytes=numwires/8 + (numwires%8)?1:0; for(unsigned char currbyte=0; currbyte