寻找在位列“1的有效位置 [英] Finding position of '1's efficiently in an bit array

问题描述

我布线，测试了一套开路或短路的电线的方案。该程序，它运行在一个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 LT;≤（（B）8％））
 ＃定义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））的
 ＃定义BITNSLOTS（NB）（（NB + 8  -  1）/ 8）
 

只是为了进一步说明如何检测开路。预计数据：0b00000010，接收到的数据：0b00000000（该线没有拉高）。 0b00000010 ^ 0b00000000 = 0b0b00000010 - 线2是开放

请注意：我知道测试的300线是不是内部的AVR兆丰1281就可以搞定，这就是为什么我会分裂成集团这个微小的RAM，即测试50线，比较，显示结果，然后向前

解决方案

许多架构提供了定位的第一套位在一个字，或用于计数设置位的数量具体说明。通常编译器对这些操作提供内部函数，这样你就不必编写内联汇编。 GCC，例如，提供 __ builtin_ffs ， __ builtin_ctz ， __ builtin_popcount 等，其中每一个应该映射到目标结构适当的指令，利用位级并行

如果目标体系结构不支持这些，高效的软件实现是由编译器发出的。在软件测试位向量位的幼稚的做法是不是很有效。

如果你的编译器不实现这些，你仍然可以使用的德布鲁因序列。

I'm wiring a program that tests a set of wires for open or short circuits. The program, which runs on an AVR, drives a test vector (a walking '1') onto the wires and receives the result back. It compares this resultant vector with the expected data which is already stored on an SD Card or external EEPROM.

Here's an example, assume we have a set of 8 wires all of which are straight through i.e. they have no junctions. So if we drive 0b00000010 we should receive 0b00000010.

Suppose we receive 0b11000010. This implies there is a short circuit between wire 7,8 and wire 2. I can detect which bits I'm interested in by 0b00000010 ^ 0b11000010 = 0b11000000. This tells me clearly wire 7 and 8 are at fault but how do I find the position of these '1's efficiently in an large bit-array. It's easy to do this for just 8 wires using bit masks but the system I'm developing must handle up to 300 wires (bits). Before I started using macros like the following and testing each bit in an array of 300*300-bits I wanted to ask here if there was a more elegant solution.

 #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)

Just to further show how to detect an open circuit. Expected data: 0b00000010, received data: 0b00000000 (the wire isn't pulled high). 0b00000010 ^ 0b00000000 = 0b0b00000010 - wire 2 is open.

NOTE: I know testing 300 wires is not something the tiny RAM inside an AVR Mega 1281 can handle, that is why I'll split this into groups i.e. test 50 wires, compare, display result and then move forward.

解决方案

Many architectures provide specific instructions for locating the first set bit in a word, or for counting the number of set bits. Compilers usually provide intrinsics for these operations, so that you don't have to write inline assembly. GCC, for example, provides __builtin_ffs, __builtin_ctz, __builtin_popcount, etc., each of which should map to the appropriate instruction on the target architecture, exploiting bit-level parallelism.

If the target architecture doesn't support these, an efficient software implementation is emitted by the compiler. The naive approach of testing the vector bit by bit in software is not very efficient.

If your compiler doesn't implement these, you can still code your own implementation using a de Bruijn sequence.

这篇关于寻找在位列“1的有效位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！