通过打开整数位进行枚举的最快方法

我认为钻头移动最快。未经测试,但我认为以下内容应该很快(至少和IEnumerable一样快)。

IEnumerable<int> GetExponents(Int32 value)
{
    for(int i=0; i<32; i++)
    {
        if(value & 1)
            yield return i;
        value >>= 1;
    }
}

如果您希望它更快,您可以考虑返回 List<int> 相反。

这个 最快的 方式?查找表几乎总是最快的方法。构建一个包含40亿个条目的int[]数组,每个int对应一个条目,其中包含一个所需数字的数组。当然,初始化表需要一些时间,但是查找速度非常快。

我注意到,你还没有说“最快”是什么意思,并且没有足够的精确性让任何人能够真正回答这个问题。它是指包括启动时间在内的最快摊余时间,还是假设启动成本可以忽略的边际查找时间?我的解决方案草图假定后者。

显然,一台具有20亿字节地址空间的32位机器将没有足够的地址空间来存储300亿字节的数组。给自己买一台64位的机器。如果您希望它运行得更快,那么您至少还需要安装那么多的物理内存——否则分页会使您丧命。

我当然希望您在每次查找中节省的几纳秒值得购买所有额外的硬件。或者也许你没有 事实上 想要 最快的 方式?

-)

这个 IEnumerable 不会表演的。优化本主题中的一些示例:

第一个(最快-10米跑2.35秒,范围1到10米):

static uint[] MulDeBruijnBitPos = new uint[32] 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};

static uint[] GetExponents(uint value)
{
    uint[] data = new uint[32];
    int enabledBitCounter = 0;

    while (value != 0)
    {
        uint m = (value & (0 - value));
        value ^= m;
        data[enabledBitCounter++] = MulDeBruijnBitPos[(m * (uint)0x077CB531U) >> 27];
    }

    Array.Resize<uint>(ref data, enabledBitCounter);
    return data;
}

另一个版本(第二快-10米跑3秒,范围1到10米):

static uint[] GetExponents(uint value)
{
    uint[] data = new uint[32];
    int enabledBitCounter = 0;

    for (uint i = 0; value > 0; ++i)
    {
        if ((value & 1) == 1)
            data[enabledBitCounter++] = i;
        value >>= 1;
    }

    Array.Resize<uint>(ref data, enabledBitCounter);
    return data;
}

在安全的C代码中,一个字节值的查找数组应该尽可能快。将4个字节中的每一个从整数中移出(根据需要强制转换为uint),并索引到数组中。

查找数组的元素可以是一个指数数组,或者,取决于您对位的处理方式,可能是可以工作的委托。

只是为了好玩,这里有一个使用LINQ的一行程序。

这当然不是最快的方法,尽管它并不落后于其他答案 yield 和迭代器块。

int test = 42;

// returns 1, 3, 5
//   2^1 + 2^3 + 2^5
// =   2 +   8 +  32
// = 42
var exponents = Enumerable.Range(0, 32).Where(x => ((test >> x) & 1) == 1);

对于更快的解决方案,我可能返回一个普通的集合,而不是使用迭代器块。像这样:

int test = 2458217;

// returns 0, 3, 5, 6, 9, 15, 16, 18, 21
//   2^0 + 2^3 + 2^5 + 2^6 + 2^9 +  2^15 +  2^16 +   2^18 +    2^21
// =   1 +   8 +  32 +  64 + 512 + 32768 + 65536 + 262144 + 2097152
// = 2458217
var exponents = GetExponents(test);

// ...

public static List<int> GetExponents(int source)
{
    List<int> result = new List<int>(32);

    for (int i = 0; i < 32; i++)
    {
        if (((source >> i) & 1) == 1)
        {
            result.Add(i);
        }
    }

    return result;
}

最快的输入分配是什么?如果通常只设置一个位,那么这可能比循环查找设置位更快。

从已接受的答案中找出 position of the least significant bit 从 Bit Twiddling Hacks ,这个解决方案循环、查找、清除和返回每个连续的最低有效位的位置。

   static int[] MulDeBruijnBitPos = new int[32] 
    {
      0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
      31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
    };

    static IEnumerable<int> GetExponents(UInt32 v)
    {
        UInt32 m;

        while( v != 0 ) {
          m = (v & (UInt32) (-v));
          yield return MulDeBruijnBitPos[((UInt32) (m * 0x077CB531U)) >> 27];
          v ^= m;
        }
    }

它的循环次数与位集的循环次数相同。

我想比特移位(<<)是最快的。

如果你不会在一个小C++上窒息:

 void func(int i, int& n, int a[]){
  n = 0;
  if (i < 0) a[n++] = 31;
  i <<= 1;
  if (i < 0) a[n++] = 30;
  i <<= 1;
  if (i < 0) a[n++] = 29;
  i <<= 1;

  ...

  if (i < 0) a[n++] = 0;
}