以二進制跳轉段

我的問題是，有沒有一種方式在C＃中有一個起始位的位置，以找到下一個二進制數字的指定值爲0或1的字節中沒有迭代（尋找最高的性能選項）。作爲一個例子，如果你有10011並從第一位開始（最右邊）並搜索第一個0，它將是從右到左的第三個地方。如果你在第三名開始並想找到下一個，那麼它將位於第五名（最左邊）。以二進制跳轉段

感謝您的任何幫助，並隨時讓我知道，如果我需要進一步提供任何東西。

編輯：這是我目前的代碼。

private int GetBinarySegment(uint uiValue, int iStart, int iMaxBits, byte bValue) 
{ 
    int r = 0; uiValue >>= iStart; 
    if (uiValue == 0) return iMaxBits - iStart; 
    while ((uiValue & 1) == bValue) { uiValue >>= 1; r++; } 
    return r; 
}

來源

2013-06-13 Mythics

@STLDeveloper只有各種形式的迭代。我剛剛開始移動，直到最右邊的位發生變化，並記錄位移＃直到位位置0改變。如果我需要指定一個「開始」位置，我會在運行循環之前移動該量。因爲它都是二元的，所以我希望有一個更優雅的選擇。 – Mythics

你對結果做什麼？有沒有可能直接用掩碼錶示這個位或是否真的必須是索引？ – harold

@harold我想要獲得信息，我應該更願意給它。我正在研究一種做多維填充的方法來識別遊戲的標量場/體素地形環境中的所有固體物體。我相信有一些類似的技巧，我可以比典型的迭代方法填充更好地得到更好的結果。 – Mythics

有一些方法，但它們很醜，因爲沒有_BitScanForward或等效的內在。不過，實際上，您可以高效地計算這個東西，而不需要一張大桌子。

第一步：創建一個數字，在您搜索的位置上有1，而在其他地方爲0。

如果搜索1，表示x & -x。如果搜索0，請使用~x & (x + 1)。

然後，使用多種方法之一來模擬bitscan（現在只有一個設置位，所以它不會影響你搜索哪一邊）。有些方法可以做到這一點here（不是用C＃，但可以轉換它們）。

來源

2013-06-13 07:44:53 harold

由於性能方面的原因，我不得不問，因爲性能的原因，訪問2D Jagged Array的速度不會比你提供的選項快（考慮到我仍然需要一個日誌功能或查找表更可能）？當然沒有那麼優雅，但表現確實是我的主要意圖。 – Mythics

可能不是，這意味着取消引用兩個依賴指針（如果它們在L1中不是太糟糕，否則就不好），而您可以通過強制轉換來計算日誌以加倍和重新解釋這些位。如果你打算使用一個表格，將其設置爲一維數組和一些數學運算來獲得索引（並使用「不安全」訪問）。如果有更大的字大小是合理的，應該只與mask/bitscan選項相結合，表會變得太大（它們可能適合內存，但最後一級緩存未命中需要大約百週期） – harold

使用查找表。也就是說，預先計算按字節值和當前位置索引的二維數組。你可以做一個零和一個單獨的表，或者你可以組合它。

因此，對於您的示例，您從數字19的位0開始。這恰好是1.因此，如果您查找nextBit[19][0]，它應該返回1，依此類推。以下是組合查找表的樣子。它顯示了兩個0和1下位：

nextBit[19][0] = 1 // 1 
nextBit[19][1] = 4 // 1 
nextBit[19][2] = 3 // 0 
nextBit[19][3] = 4 // 0 
nextBit[19][4] = 0 // 1 
nextBit[19][5] = 6 // 0 
nextBit[19][6] = 7 // 0

顯然，是第7位沒有「下一個」，如果「下一個」返回0，沒有更多的特定位。

我可能錯誤地解釋了您的問題，但可以修改此技術以適合您的目的。我最初以爲你想瀏覽所有的1位或0位。如果您想跳過連續的1位，那麼您只需以這種方式安排您的表格。或者事實上，你可以在每個位置都有一個'下一個'0和1。

來源

2013-06-13 04:00:41 paddy

以二進制跳轉段

回答

相關問題