我的問題或多或少是標題中的內容;我想知道是否有一個快速的方法來通過一系列的位,並找到設置的每一個位。迭代通過一個位序列,並找到每個設置位
更詳細的信息:
我目前正在在代表一組對象的數據結構同步。爲了支持我需要的一些操作,結構必須能夠在內部執行非常快速的子集交集。我提出的解決方案是讓結構超集中的每個子集都由一個「位數組」表示,其中每個位都映射到數組中的一個索引,該索引保存超集的數據。示例:如果位#1設置在子集中,則超集數組中索引爲1的元素出現在子集中。
每個子集包含一個足夠大的ulong數組,以便有足夠的位來表示整個超集(如果超集包含256個元素,則數組大小必須爲256/64 = 4)。爲了找到2個子集S1和S2的交集,我可以簡單地遍歷S1和S2的數組,並找到每個索引處的按位和在兩個位之間。
現在回到我的問題的實質: 爲了返回一個子集的數據,我必須遍歷子集的「位數組」中的所有位並找到設置的位。這是我如何做到這一點:
/// <summary>
/// Gets an enumerator that enables enumeration over the strings in the subset.
/// </summary>
/// <returns> An enumerator. </returns>
public IEnumerator<string> GetEnumerator()
{
int bitArrayChunkIndex = 0;
int bitArrayChunkOffset = 0;
int bitArrayChunkCount = this.bitArray.Length;
while(bitArrayChunkIndex < bitArrayChunkCount)
{
ulong bitChunk = bitArray[bitArrayChunkIndex];
// RELEVANT PART
if (bitChunk != 0)
{
int bit = 0;
while (bit < BIT_ARRAY_CHUNK_SIZE /* 64 */)
{
if(bitChunk.BitIsSet(bit))
yield return supersetData[bitArrayChunkOffset + bit];
bit++;
}
}
bitArrayChunkIndex++;
bitArrayChunkOffset += BIT_ARRAY_CHUNK_SIZE;
// END OF RELEVANT PART
}
}
有沒有什麼明顯的方法來優化呢?任何有點竅門,使其能夠非常快速地完成?謝謝!
你也許能夠使用的東西從這裏:HTTP://graphics.stanford .edu /〜seander/bithacks.html – ElKamina 2013-05-10 00:00:21
這是什麼應用程序,取決於您何時需要數據,您可以在不同的時間獲取數據 – aaronman 2013-05-10 03:03:46
這個問題有很多技術可以適應您的內部循環。 http://stackoverflow.com/questions/757059/position-of-least-significant-bit-that-is-set我自己使用bsf/bsr。 – rlb 2013-05-10 10:56:41