迭代通過一個位序列，並找到每個設置位

我的問題或多或少是標題中的內容;我想知道是否有一個快速的方法來通過一系列的位，並找到設置的每一個位。迭代通過一個位序列，並找到每個設置位

更詳細的信息：

我目前正在在代表一組對象的數據結構同步。爲了支持我需要的一些操作，結構必須能夠在內部執行非常快速的子集交集。我提出的解決方案是讓結構超集中的每個子集都由一個「位數組」表示，其中每個位都映射到數組中的一個索引，該索引保存超集的數據。示例：如果位＃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 
    } 
}

有沒有什麼明顯的方法來優化呢？任何有點竅門，使其能夠非常快速地完成？謝謝！

來源

2013-05-09 H.S.

你也許能夠使用的東西從這裏：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

取一個十六個整數的數組，用從0到15的整數設置的位數進行初始化（即0,1,1,2,1,2,2,3,1,2,2,3 ，2，3，3，4）。現在取bitchunk％16，並在int數組中查找結果 - 這是塊的前四位中的設置位數。右移四次，並重復整個操作十五次以上。

您可以使用256個整數和8位子塊的數組來完成此操作。我不推薦使用12位小塊的4096整數數組，這有點荒謬。

int[] lookup = new int[16] {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4}; 
int bitCount = 0; 
for(int i = 0; i < 16; i++) { 
    int firstFourBits = bitChunk % 16; 
    bitCount += lookup[firstFourBits]; 
    bitChunk = butChunk >> 4; 
}

來源

2013-05-10 00:07:49

在INTEL 386+上，您可以使用機器指令BitSearchFirst。以下 - gcc樣本。對於過程64位字來說這是有點棘手的，但無論如何，它都能快速高效地工作。

#include <stdio.h> 
#include <stdlib.h> 
#include <stdint.h> 

int main(int argc, char **argv) { 
    uint64_t val; 
    sscanf(argv[1], "%llx", &val); 
    printf("val=0x%llx\n", val); 
    uint32_t result; 
    if((uint32_t)val) { // first bit is inside lowest 32 
    asm("bsfl %1,%0" : "=r"(result) : "r"(val)); 
    } else {    // first bit is outside lowest 32 
    asm("bsfl %1,%0" : "=r"(result) : "r"(val >> 32)); 
    result += 32; 
    } 
    printf("val=%llu; result=%u\n", val, result); 
    return 0; 
}

此外，在您的使用x64體系結構，你可以嘗試使用bsfq指令，並刪除「的if/else」

來源

2013-08-24 14:27:03 maxihatop

迭代通過一個位序列，並找到每個設置位

回答

相關問題