Самый быстрый способ перечислить через включенные биты целого числа

Замените this на getActivity() и вуаля!

7
задан Chad Grant 8 May 2009 в 03:25
поделиться

8 ответов

Я полагаю, что сдвиг битов будет самым быстрым. Не тестировалось, но я думаю, что следующие действия должны быть быстрыми (по крайней мере, так же быстро, как IEnumerables).

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

Если вы хотите, чтобы это было быстрее, вы можете вместо этого рассмотреть возможность возврата List .

11
ответ дан 6 December 2019 в 04:46
поделиться

Просто для забавы, вот одна строка, использующая 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;
}
3
ответ дан 6 December 2019 в 04:46
поделиться

Самый быстрый, учитывая какой дистрибутив для входных данных? Если обычно установлен только один бит, то это может быть быстрее, чем цикл поиска установленных битов.

Взятие из принятого ответа для нахождения позиции младшего бита , который был взят из ] Bit Twiddling Hacks , это решение циклов, поиск, очистка и возврат позиции каждого последующего младшего бита.

2
ответ дан 6 December 2019 в 04:46
поделиться

IEnumerable не будет работать. Оптимизация некоторых примеров в этой теме:

Первая (самая быстрая - 2,35 секунды для 10M запусков, диапазон 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;
}

Другая версия (вторая самая быстрая - 3 секунды для 10M запусков, диапазон 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;
}
6
ответ дан 6 December 2019 в 04:46
поделиться

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.

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.

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?

:-)

30
ответ дан 6 December 2019 в 04:46
поделиться

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.

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
ответ дан 6 December 2019 в 04:46
поделиться

Думаю, сдвиг бит (<<) - самый быстрый.

1
ответ дан 6 December 2019 в 04:46
поделиться

Если вы не подавитесь небольшим количеством 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;
}
0
ответ дан 6 December 2019 в 04:46
поделиться
Другие вопросы по тегам:

Похожие вопросы: