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

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

2

c# bit-manipulation

Источник

user45914 05 окт '09 в 01:04

8 ответов

Решение

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

0

Источник

user208395 11 ноя '09 в 04:39

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

0

Источник

user154152 05 окт '09 в 01:25

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

  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 (нужно больше тестов)

0

Источник

user103167 05 июл '11 в 01:56

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

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

например

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

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

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

Код в с

//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 бит.

РЕДАКТИРОВАТЬ:

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

0

Источник

user131057 05 окт '09 в 01:52

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

Вот пример для таблицы из 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, чтобы его можно было просто жестко кодировать в вашей программе.

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

Удачной Охоты.

Злой.

0

Источник

user7734 24 авг '10 в 18:32

Лучшее, что я могу здесь сделать, - это просто проявить глупость и развернуть внутренний цикл... кажется, он сократил производительность вдвое (примерно 4 секунды, а не 8 в вашем, чтобы обработать 100 улонов 100000 раз)... Я использовал приложение командной строки 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%. пожав плечами я попробовал.

0

Источник

user164392 05 окт '09 в 03:10

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

Один из них

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

-1

Источник

user131057 05 окт '09 в 01:25

Другие вопросы по тегам c# bit-manipulation

user31092 05 окт '09 в 02:16 2009-10-05 02:16 · Accepted Answer · 2009-10-05 02:16

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