在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

回答

相關問題