在32位字查找“边缘”bitpattern

我试图找到最有效的算法来计算位模式的“边缘”。边缘表示从0到1或从1到0的变化。我每250 us对每个位进行一次采样，并将其转换为32位无符号变量。在32位字查找“边缘”bitpattern

这是我的算法迄今

void CountEdges(void) 
{ 
    uint_least32_t feedback_samples_copy = feedback_samples; 
    signal_edges = 0; 

    while (feedback_samples_copy > 0) 
    { 
     uint_least8_t flank_information = (feedback_samples_copy & 0x03); 

     if (flank_information == 0x01 || flank_information == 0x02) 
     { 
      signal_edges++; 
     } 

     feedback_samples_copy >>= 1; 
    } 
}

它需要至少2或3倍的速度。

来源

2009-10-27 Erik

有一点可能会帮助的是预先计算所有可能的8位值的边缘计数（512条目查找表，因为必须在每个值之前包括该位），然后总计计数1个字节在一次。

// prevBit is the last bit of the previous 32-bit word 
// edgeLut is a 512 entry precomputed edge count table 
// Some of the shifts and & are extraneous, but there for clarity 
edgeCount = 
    edgeLut[(prevBit << 8) | (feedback_samples >> 24) & 0xFF] + 
    edgeLut[(feedback_samples >> 16) & 0x1FF] + 
    edgeLut[(feedback_samples >> 8) & 0x1FF] + 
    edgeLut[(feedback_samples >> 0) & 0x1FF]; 

prevBit = feedback_samples & 0x1;

来源

2009-10-27 13:32:57

为什么和与0x1F的？你忽略了每字节3比特这种方式 – Toad 2009-10-27 13:40:34

我必须在你阅读的时候编辑它; - ] – 2009-10-27 13:42:09

我比我的影子显然更快评论; ^） – Toad 2009-10-27 13:44:03

创建一个查找表，让你可以在一杆一字节或16位值中的转换 - 那么所有你需要做的是看看字节之间的“边缘”位的差异（或16位值）。

来源

2009-10-27 13:33:04

Argh，双忍者。 – 2009-10-27 13:34:12

您在每次迭代期间只查看2位。
最快的算法可能是为所有可能的值构建一个哈希表。由于有2^32的值不是最好的想法。
但是你为什么不一步就看3,4,5 ......位呢？您可以预先计算所有4位组合的边数。只需照顾碎片之间可能的边缘。

来源

2009-10-27 13:34:27 tanascius

你总是可以使用比如8位的查找表在时间这样你得到的约8倍

的速度可提高别忘了在这8位之间的检查位，但。这些必须手动检查

来源

2009-10-27 13:34:31 Toad

您应该能够将它们按位异或以获得表示翻转位的位模式。然后使用此页面上的位计数技巧之一：http://graphics.stanford.edu/~seander/bithacks.html来计算结果中有多少个1。

来源

2009-10-27 13:35:11

这个解决方案的另一个链接：http://tekpool.wordpress.com/category/bit-count/ – Guillaume 2009-10-27 13:36:33

我不认为它会反对查找表。对于极端的内存限制设备，它可能是解决方案。虽然我不希望有人在这种情况下编写C代码，但转而使用汇编代替 – Toad 2009-10-27 13:38:46

请原谅我的无知，但XOR如何给出“边缘”？您可以计算设置的位数，但我理解这一点的方式是，您需要00011101011为5（或7，如果您计算边界）并且1111100001111为3. – Abel 2009-10-27 13:40:27

我的建议：

您输入的值复制到一个临时变量，留下的一个
转移复制LSB您输入YOUT临时变量
XOR的两个值。结果值中设置的每个位代表一个边。
使用this algorithm来计数设置的位数。

这可能是第3个步骤的代码：

uint32 input; //some value 
uint32 temp = (input << 1) | (input & 0x00000001); 
uint32 result = input^temp; 

//continue to count the bits set in result 
//...

来源

2009-10-27 14:02:28

+1。我正要写类似的东西。我的第一个想法是'temp =（intput >> 1）^（input＆0x7FFFFFFFu）;但是返回countBits（temp）;'。 – sellibitze 2009-10-27 14:39:57

在32位字查找“边缘”bitpattern

回答

相关问题