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

What's the fastest way to enumerate through an integer and return the exponent of each bit that is turned on? Have seen an example using << and another using Math.Pow. Wondering if there is anything else that's really fast.

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

Thanks.

8 个解决方案

#1

I imagine bit-shifting would be the fastest. Untested, but I think the following ought to be fast (as fast as IEnumerables are at least).

我认为位移是最快的。未经测试,但我认为以下应该是快速的(至少与IEnumerables一样快)。

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

If you want it to be faster, you might consider returning a List<int> instead.

如果您希望它更快,您可以考虑返回List 。

#2

The fastest way? Lookup tables are almost always the fastest way. Build an int[][] array with four billion entries, one for each int, containing an array of the numbers you want. Initializing the table will take some time, of course but the lookups will be incredibly fast.

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

I note that you have not said what "fastest" means with sufficient precision for anyone to actually answer the question. Does it mean fastest amortized time including startup time, or marginal lookup time assuming that startup costs can be neglected? My solution sketch assumes the latter.

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

Obviously a 32 bit machine with 2 billion bytes of address space will not have enough address space to store thirty billion bytes of arrays. Get yourself a 64 bit machine. You'll need at least that much physical memory installed as well if you want it to be fast -- the paging is going to kill you otherwise.

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

I sure hope the couple of nanoseconds you save on every lookup are worth buying all that extra hardware. Or maybe you don't actually want the fastest way?

我当然希望你在每次查找时节省的几纳秒都值得购买所有额外的硬件。或许你真的不想要最快的方式?

:-)

#3

The IEnumerable is not going to perform. Optimization of some examples in this topic:

IEnumerable不会执行。优化本主题中的一些示例:

First one (fastest - 2.35 seconds for 10M runs, range 1..10M):

第一个(最快 - 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;
}

Another version (second fastest - 3 seconds for 10M runs, range 1..10M):

另一个版本(第二快 - 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;
}

#4

A lookup array for one byte's worth of bits ought to be close to the fastest you can do in safe C# code. Shift each of the 4 bytes out of the integer (casting to uint as necessary) and index into the array.

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

The elements of the lookup array could be an array of exponents, or, depending on what you're doing with the bits, perhaps delegates that do work.

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

#5

Just for fun, here's a one-liner using LINQ.

只是为了好玩,这是一个使用LINQ的单线程。

It's certainly not the fastest way to do it, although it's not far behind the other answers that use yield and iterator blocks.

它当然不是最快的方法,尽管它与使用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);

For a speedier solution I would probably return a plain collection rather than using an iterator block. Something like this:

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

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

#6

Fastest given what distribution for the input? If typically only one bit is set, then this could be faster than looping through looking for set bits.

最快的给出输入的分布?如果通常只设置一个位,那么这可能比寻找设置位的循环更快。

Taking from the accepted answer for finding the position of the least significant bit, which took from Bit Twiddling Hacks, this solutions loops, finding, clearing and returning the position of each consecutive 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;
        }
    }

It only loops as many times as there are bits set.

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

#7

I guess bit shifting (<<) is the fastest.

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

#8

If you won't choke on a little C++:

如果你不想扼杀一点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;
}

#1