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

Question

Какой самый быстрый способ перечислить через целое число и вернуть показатель каждого включенного бита? Видел пример использования <<, а другой - Math.Pow. Хотите знать, есть ли что-нибудь еще, что действительно быстро. </p>

Спасибо.

Answer 1

самый быстрый способ? Таблицы поиска почти всегда самый быстрый способ. Создайте массив int [] [] с четырьмя миллиардами записей, по одной для каждого типа int, содержащий массив нужных вам чисел. Конечно, инициализация таблицы займет некоторое время, но поиск будет невероятно быстрым.

Хочу заметить, что вы не сказали, что означает «самый быстрый», с достаточной точностью, чтобы кто-нибудь мог ответить на вопрос. Означает ли это самое быстрое амортизированное время, включая время запуска или минимальное время поиска, при условии, что затратами на запуск можно пренебречь? Мой эскиз решения предполагает последнее.

Очевидно, что 32-битной машине с 2 миллиардами байтов адресного пространства не хватит адресного пространства для хранения тридцати миллиардов байтов массивов. Получите себе 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 не собирается выполнять. Оптимизация некоторых примеров в этой теме:

Первый (самый быстрый - 2,35 секунды для бега на 10 м, диапазон 1,10 м):

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 секунды для бега на 10 м, диапазон 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 при необходимости) и внесите указатель в массив.

Элементы массива поиска могут быть массивом экспонент или, в зависимости от того, что вы делаете с битами, возможно, делегатами, которые работают.

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

Answer 6

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

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

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

Он зацикливается столько раз, сколько установлены биты.

Answer 7

Полагаю, что битовое смещение (<<) - самое быстрое. </p>

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