7

枚举整数并返回打开的每个位的指数的最快方法是什么？看过一个使用 << 的例子和另一个使用 Math.Pow 的例子。想知道是否还有其他真正快速的东西。

谢谢。

4

8 回答 8

30

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

我注意到你没有足够精确地说明“最快”的含义，让任何人都可以真正回答这个问题。这是否意味着包括启动时间在内的最快摊销时间，或假设启动成本可以忽略的边际查找时间？我的解决方案草图假设后者。

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

我当然希望您在每次查找时节省的几纳秒值得购买所有额外的硬件。或者，也许您实际上并不想要最快的方式？

:-)

于 2009-05-08T06:09:08.810 回答
11

我想位移将是最快的。未经测试，但我认为以下应该很快（至少与 IEnumerables 一样快）。

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

如果您希望它更快，您可以考虑返回 a List<int>。

于 2009-05-08T03:34:10.570 回答
6

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;
}
于 2009-05-09T07:52:56.530 回答
5

一个字节的位值的查找数组应该接近您在安全 C# 代码中可以做到的最快速度。将 4 个字节中的每一个从整数中移出（必要时转换为 uint）并索引到数组中。

查找数组的元素可以是指数数组，或者，根据您对位所做的操作，可能是有效的委托。

于 2009-05-08T03:48:31.923 回答
3

只是为了好玩，这里有一个使用 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;
}
于 2009-05-08T10:21:52.697 回答
2

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

从接受的寻找最低有效位位置的答案（取自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;
        }
    }

它仅循环与设置的位相同的次数。

于 2009-05-08T04:14:51.720 回答
1

我猜位移 (<<) 是最快的。

于 2009-05-08T03:29:58.520 回答
0

如果你不会被一点 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;
}
于 2009-05-10T21:48:27.030 回答