枚举整数中打开位的最快方法

Question

如何最快地枚举整数并返回打开的每个位的指数？已经看到使用 << 和 Math.Pow 的示例。想知道是否有其他更快的方法。

谢谢。

- Fung

---

ж №жҚ®жҲ‘зҡ„з»ҸйӘҢпјҢMath.Powйқһеёёж…ўгҖӮжҜ”еҰӮиҜҙпјҢжҜ”Math.CosжҲ–Math.SqrtиҝҳиҰҒж…ўеҫ—еӨҡгҖӮе®ғж°ёиҝңжІЎжңүжңәдјҡиғңиҝҮж•ҙ数移дҪҚгҖӮ - Roman Starkov

Answer 1

最快的方法？查找表几乎总是最快的方法。建立一个包含四十亿条目的int[][]数组，每个int一个，包含您想要的数字数组。当然，初始化表格需要一些时间，但查询将非常快速。

我注意到您没有用足够精确的方式说明“最快”的含义，以便任何人都可以回答这个问题。它是指包括启动时间在内的平均最快时间，还是假设启动成本可以忽略不计的边际查找时间？我的解决方案草图假定后者。

显然，具有2亿字节地址空间的32位机器将没有足够的地址空间来存储三十亿字节的数组。给自己弄一台64位机器。如果你想要它变快，你至少需要安装那么多物理内存——否则分页会使你死亡。

我真希望你能够因为每次查找少花几纳秒而值得购买所有这些额外的硬件。或者也许你实际上并不想要最快的方法？

:-)

- Eric Lippert

---

这个回应真是个混蛋...但很好！ :) - user47322

你是漫画书男孩吗？显然，他想要最快的合理方法。 - Blorgbeard

有人需要定义“合理”。一旦你定义了“合理”，你就有了一个性能规范。 “尽可能快”不是一个规范。通过考虑实现最快速度所需的成本，您开始意识到性能从来不是关于“尽可能快”。它是关于在投资上获得合理的性能回报。性能调优很昂贵; 如果没有实际的规范，您可能会花费大量资金尝试达到您实际上不需要的性能水平。 - Eric Lippert

巨大的查找表往往不是实现某些功能最快的方式。由于我们几乎肯定会遇到缓存未命中，因此查找需要数百个时钟周期。任何其他提出的方法都可以轻松击败它。 - Accipitridae

@Majkara Tito：如果他在硬件中构建查找表，那么它不会对RAM造成负担。 - Brian

Answer 2

我认为位运算可能是最快的。没有经过测试，但我认为以下代码应该很快（至少和IEnumerables一样快）。

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

如果你想让它更快，你可以考虑返回一个List<int>。

- lc.

---

我不确定您所说的int32Value的确切含义，但是为了使用ForEach扩展方法，您必须拥有一个IList。如果需要，您可以在IEnumerable上调用ToList()来获取一个IList。如果您愿意，您可以将上述代码制作成一个扩展方法，并调用myInt.GetExponents().ToList().ForEach(...)。 - lc.

你可以尝试在LINQ中使用聚合函数。 - leppie

你的循环不应该从零开始吗？即第一个二进制位表示指数0，第二个二进制位表示指数1，以此类推。（2^0 = 1，2^1 = 2，2^2 = 4等）。 - LukeH

你也可以将其作为扩展方法实现。 - geofftnz

该行代码if (value & 1)无法正常工作，会报错"无法将int转换为bool"，因此我写成了if ((value & 1) == 1)。 - Ray

Answer 3

IEnumerable不会执行。这个主题中的某些示例优化：

第一个示例（最快 - 10M次运行的时间为2.35秒，范围为1..10M）：

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

另一个版本（第二快 - 10M次运行时间为3秒，范围为1..10M）：

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

- tofi9

Answer 4

一个字节位的查找数组应该是在安全的C#代码中可以实现的最快方法。将整数中的4个字节（如有必要，转换为uint）移位并索引到数组中。

查找数组的元素可以是指数数组，或者根据位的操作方式，可能是执行工作的委托。

- Barry Kelly

---

++ 我喜欢这个，除了有效地收集结果成为一个问题。查找表的每个元素可以是指数数组，但是然后您必须将它们连接起来，并将8、16和24添加到每个数组中。不确定需要多少周期。 - Mike Dunlavey

Answer 5

仅仅是为了好玩，这里有一个使用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;
}

- LukeH

Answer 6

给定输入的分布是什么，才能最快地实现？如果通常只设置一个位，则这可能比循环查找设置位更快。

从找到最低有效位的位置的已接受答案中获取，该答案取自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;
        }
    }

它只循环了被设置的位数次。

- Tony Lee

---

一个更简单和更清晰的解决方案是使用一个小的（16或256个条目）查找表。 - Sinan Ünür

lc的答案非常简洁明了，很难超越。 - Tony Lee

Answer 7

我想位移（<<）是最快的。

- Pavel Bastov

Answer 8

如果你不会被一点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;
}

- Mike Dunlavey