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

Question

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

谢谢.

Answer 1

该最快的方法是什么？查找表几乎总是最快的方式.构建一个包含40亿个条目的int [] []数组,每个int一个,包含所需数字的数组.当然,初始化表需要一些时间,但查找速度将非常快.

我注意到你还没有说出"最快"的含义是否足以让任何人真正回答这个问题.假设启动成本可以忽略,这是否意味着最快的摊还时间,包括启动时间或边际查询时间？我的解决方案草图假设后者.

显然,具有20亿字节地址空间的32位机器将没有足够的地址空间来存储300亿字节的数组.给自己一台64位机器.如果你想让它快速,你至少需要安装那么多的物理内存 - 否则分页会杀了你.

我当然希望你在每次查找时节省的几纳秒都值得购买所有额外的硬件.或者,也许你并不真正需要的最快方法是什么？

:-)

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>.

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

Answer 4

一个字节的位的查找数组应该接近安全C#代码中最快的速度.将4个字节中的每个字节移出整数(根据需要转换为uint)并索引到数组中.

查找数组的元素可以是指数数组,或者,取决于您对这些位执行的操作,也许是可以执行的委托.