0

我的问题或多或少是标题中的内容；我想知道是否有一种快速的方法来遍历一系列位并找到设置的每个位。

更详细的信息：

我目前正在研究代表一组对象的数据结构。为了支持我需要的一些操作，该结构必须能够在内部执行非常快速的子集交集。我想出的解决方案是让结构超集的每个子集由一个“位数组”表示，其中每个位映射到数组中保存超集数据的索引。示例：如果在子集中设置了位 #1，则超集数组中索引 1 处的元素存在于子集中。

每个子集由一个足够大的 ulong 数组组成，足以表示整个超集（如果超集包含 256 个元素，则数组的大小必须为 256 / 64 = 4）。要找到 2 个子集 S1 和 S2 的交集，我可以简单地遍历 S1 和 S2 的数组，并在每个索引处找到 ulong 之间的按位与。

现在回到我的问题的真正意义：为了返回子集的数据，我必须遍历子集的“位数组”中的所有位并找到设置的位。这就是我目前的做法：

 /// <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
     }
 }

有什么明显的方法可以优化这个吗？有什么技巧可以让它很快完成吗？谢谢！

4

2 回答 2

1

在 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-24T14:27:03.423 回答
0

取一个包含 16 个整数的数组，使用为从 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-10T00:07:49.207 回答