Подсчет общих битов в последовательности беззнаковых длин

Question

Я ищу более быстрый алгоритм, чем приведенный ниже, для следующего. Для заданной последовательности 64-битных целых чисел без знака верните счетчик числа раз, которое каждый из шестидесяти четырех битов установлен в последовательности.

Пример:

4608 = 0000000000000000000000000000000000000000000000000001001000000000 
4097 = 0000000000000000000000000000000000000000000000000001000000000001
2048 = 0000000000000000000000000000000000000000000000000000100000000000

counts 0000000000000000000000000000000000000000000000000002101000000001

Пример:

2560 = 0000000000000000000000000000000000000000000000000000101000000000
530  = 0000000000000000000000000000000000000000000000000000001000010010
512  = 0000000000000000000000000000000000000000000000000000001000000000

counts 0000000000000000000000000000000000000000000000000000103000010010

В настоящее время я использую довольно очевидный и наивный подход:

static int bits = sizeof(ulong) * 8;

public static int[] CommonBits(params ulong[] values) {
    int[] counts = new int[bits];
    int length = values.Length;

    for (int i = 0; i < length; i++) {
        ulong value = values[i];
        for (int j = 0; j < bits && value != 0; j++, value = value >> 1) {
            counts[j] += (int)(value & 1UL);
        }
    }

    return counts;
}

Answer 1

Небольшое улучшение скорости может быть достигнуто, если сначала ИЛИ объединить целые числа, а затем использовать результат, чтобы определить, какие биты нужно проверить. Вам все равно придется перебирать каждый бит, но только один раз за биты, где нет 1 с, а не values.Length раз.

Answer 2

Я считаю, что это должно дать хорошее улучшение скорости:

  const ulong mask = 0x1111111111111111;
  public static int[] CommonBits(params ulong[] values)
  {
    int[] counts = new int[64];

    ulong accum0 = 0, accum1 = 0, accum2 = 0, accum3 = 0;

    int i = 0;
    foreach( ulong v in values ) {
      if (i == 15) {
        for( int j = 0; j < 64; j += 4 ) {
          counts[j]   += ((int)accum0) & 15;
          counts[j+1] += ((int)accum1) & 15;
          counts[j+2] += ((int)accum2) & 15;
          counts[j+3] += ((int)accum3) & 15;
          accum0 >>= 4;
          accum1 >>= 4;
          accum2 >>= 4;
          accum3 >>= 4;
        }
        i = 0;
      }

      accum0 += (v)      & mask;
      accum1 += (v >> 1) & mask;
      accum2 += (v >> 2) & mask;
      accum3 += (v >> 3) & mask;
      i++;
    }

    for( int j = 0; j < 64; j += 4 ) {
      counts[j]   += ((int)accum0) & 15;
      counts[j+1] += ((int)accum1) & 15;
      counts[j+2] += ((int)accum2) & 15;
      counts[j+3] += ((int)accum3) & 15;
      accum0 >>= 4;
      accum1 >>= 4;
      accum2 >>= 4;
      accum3 >>= 4;
    }

    return counts;
  }

Демонстрация: http://ideone.com/eNn4O (требуется больше тестовых случаев)

Answer 3

Другим подходом, который может быть выгодным, будет создание массива из 256 элементов, который кодирует действия, которые вам нужно предпринять при увеличении массива count.

Ниже приведен пример таблицы из 4 элементов, в которой 2 бита вместо 8 бит.

int bitToSubscript[4][3] =
{
    {0},       // No Bits set
    {1,0},     // Bit 0 set
    {1,1},     // Bit 1 set
    {2,0,1}    // Bit 0 and bit 1 set.
}

Затем алгоритм вырождается в:

• выбрать 2 правые биты числа.
• Используйте это как маленькое целое число для индексации в bitToSubscriptArray.
• В этом массиве выведите первое целое число. Это количество элементов в массиве count, которое необходимо увеличить.
• Основываясь на этом количестве, перебирайте оставшуюся часть строки, увеличивая количество, основываясь на индексе, который вы извлекаете из массива bitToSubscript.
• Как только этот цикл будет завершен, сдвиньте исходное число на два бита вправо ... Промыть Повторите при необходимости.

Теперь есть одна проблема, которую я проигнорировал в этом описании. Фактические подписки являются относительными. Вы должны отслеживать, где вы находитесь в массиве count. Каждый раз, когда вы делаете цикл, вы добавляете два к смещению. К этому смещению вы добавляете относительный индекс из массива bitToSubscript.

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

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

Доброй охоты.

Evil.

Answer 4

const unsigned int BYTESPERVALUE = 64 / 8;
unsigned int bcount[BYTESPERVALUE][256];
memset(bcount, 0, sizeof bcount);
for (int i = values.length; --i >= 0; )
  for (int j = BYTESPERVALUE ; --j >= 0; ) {
    const unsigned int jth_byte = (values[i] >> (j * 8)) & 0xff;
    bcount[j][jth_byte]++; // count byte value (0..255) instances
  }

unsigned int count[64];
memset(count, 0, sizeof count);
for (int i = BYTESPERVALUE; --i >= 0; )
  for (int j = 256; --j >= 0; ) // check each byte value instance
    for (int k = 8; --k >= 0; ) // for each bit in a given byte
      if (j & (1 << k)) // if bit was set, then add its count
        count[i * 8 + k] += bcount[i][j];

Answer 5

Лучшее, что я могу здесь сделать, - это просто проявить глупость и развернуть внутренний цикл ... кажется, он сократил производительность вдвое (примерно 4 секунды, а не 8 в вашем, чтобы обработать 100 ulongs 100 000 раз) ... Я использовал приложение командной строки qick для генерации следующего кода:

for (int i = 0; i < length; i++)
{
    ulong value = values[i];
    if (0ul != (value & 1ul)) counts[0]++;
    if (0ul != (value & 2ul)) counts[1]++;
    if (0ul != (value & 4ul)) counts[2]++;
    //etc...
    if (0ul != (value & 4611686018427387904ul)) counts[62]++;
    if (0ul != (value & 9223372036854775808ul)) counts[63]++;
}

это было лучшее, что я могу сделать ... Согласно моему комментарию, вы потратите некоторое количество (я не знаю, сколько) запуска этого в 32-битной среде. Если вы обеспокоены производительностью, может выгодно вам сначала преобразовать данные в uint.

Сложная проблема ... может даже помочь вам перенести ее в C ++, но это полностью зависит от вашего приложения. Извините, я не могу помочь, может кто-то еще увидит что-то, что я пропустил.

Обновление, еще несколько сеансов профилировщика, показывающих стабильное улучшение на 36%. пожимает плечами Я пытался.

Answer 6

Хорошо, позвольте мне попробовать еще раз: D

изменить каждый байт в 64-битном целом на 64-битное, сдвинув каждый бит на n * 8 в lef

например

10110101 -> 000000010000000000000001000000010000000000000001000000000000010000000000000001 (используйте таблицу поиска для этого перевода)

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

Вы должны сделать 8 * (количество 64-битных целых) суммирований

Код в c

//LOOKTABLE IS EXTERNAL and has is int64[256] ;
unsigned char* bitcounts(int64* int64array,int len)
{  
    int64* array64;
    int64 tmp;
    unsigned char* inputchararray;
    array64=(int64*)malloc(64);
    inputchararray=(unsigned char*)input64array;
    for(int i=0;i<8;i++) array64[i]=0; //set to 0

    for(int j=0;j<len;j++)
    {             
         tmp=int64array[j];
         for(int i=7;tmp;i--)
         {
             array64[i]+=LOOKUPTABLE[tmp&0xFF];
             tmp=tmp>>8;
         }
    }
    return (unsigned char*)array64;
}

Эта скорость редукции сравнивается с наивной реализацией в 8 раз, потому что она каждый раз обрабатывается 8 битами.

EDIT:

Я исправил код, чтобы сделать более быстрое разбиение на меньшие целые числа, но я все еще не уверен насчет порядка байтов И это работает только на 256 входах, потому что он использует беззнаковый символ для хранения данных. Если у вас более длинная строка ввода, вы можете изменить этот код так, чтобы он содержал до 2 ^ 16 битовых счетчиков и уменьшал sap на 2

Answer 7

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

Один из них

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

Имейте в виду, что сложность этого метода - aprox O (log2 (n)), где n - число для подсчета битовв, так что для 10 двоичных файлов нужно всего 2 цикла

Вероятно, вам следует взять метод подсчета 32-битной и 64-битной арифметики и применить его к каждой половине слова, что потребует 2 * 15 + 4 инструкций

// option 3, for at most 32-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 
   0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

Если у вас есть процессор с поддержкой sse4,3, вы можете использовать инструкцию POPCNT.http://en.wikipedia.org/wiki/SSE4

Answer 8

Я приведу вас к классическому: Bit Twiddling Hacks , но ваша цель, кажется, немного отличается от обычного подсчета (т.е. ваша переменная 'count' находится в действительно странном формате), но, возможно, это так будет полезно.