Бит Тиддлинг в С - Подсчет битов

Question

Я хочу посчитать биты, которые установлены в чрезвычайно большом битовом векторе (т.е. 100 000 бит).

В настоящее время я использую указатель на char (т.е. char * cPtr) для указанияв начале массива битов.Затем я:

1. look at each element of the array (i.e. cPtr[x]),   
2. convert it to an integer (i.e. (int) cPtr[x])   
3. use a 256 element look-up table to see how many bits are set in the given byte (i.e. cPtr[x]). 

Мне приходит в голову, что если вместо этого я использую короткий int-указатель (т. Е. Short int * sPtr), то мне понадобится только половина поисков, но с элементом 65534справочная таблица, которая будет иметь свою собственную стоимость использования памяти.

Мне интересно, какое оптимальное количество бит нужно проверять каждый раз.Кроме того, если это число не является размером какого-либо предустановленного типа, как я могу пройтись по своему битовому вектору и установить указатель равным ЛЮБОЙ произвольное число битов после начальной позиции массива битов.

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

Answer 1

Вы можете считать это, используя побитовую операцию:

char c = cPtr[x];
int num = ((c & 0x01) >> 0) +
          ((c & 0x02) >> 1) +
          ((c & 0x04) >> 2) +
          ((c & 0x08) >> 3) +
          ((c & 0x10) >> 4) +
          ((c & 0x20) >> 5) +
          ((c & 0x40) >> 6) +
          ((c & 0x80) >> 7);

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

Вы можете даже сделать его дешевле, читая int каждый раз, но тогда вам, вероятно, придется решить проблему с выравниванием.

Answer 2

Мне интересно, каково оптимальное количество бит для проверки каждый раз

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

Кроме того, если это число не является размером какого-либо предустановленного типа, как я могупройдитесь по моему битовому вектору и установите указатель равным ЛЮБОМУ произвольному количеству битов после начального местоположения массива битов.

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

Вы можете создать слово, начинающееся с произвольного бита, например:

long wordAtBit(int32_t* array, size_t bit)
{
    size_t idx = bit>>5;
    long word = array[idx] >> (bit&31);
    return word | (array[idx+1] << (32 - (bit&31));
}

Answer 3

Это должно быть довольно быстро (взято из Википедии ):

static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 };
static int popcount(uint32 i)
{
    return (wordbits[i&0xFFFF] + wordbits[i>>16]);
}

Таким образом, вы можете проверять 32 бита за итерацию.

Answer 4

Я немного опоздал на вечеринку, но есть гораздо более быстрые подходы, чем те, которые были предложены до сих пор.Причина в том, что многие современные архитектуры предлагают аппаратные инструкции для подсчета количества битов различными способами (начальные нули, начальные, конечные нули или единицы, подсчет числа битов, установленных в 1, и т. Д.).Подсчет количества битов, установленных в 1, называется весом Хэмминга, также обычно называемым количеством населения, или просто подсчетом.

На самом деле, процессоры x86 имеют инструкцию POPCNT как часть инструкции SSE4.2задавать.Самая последняя новейшая архитектура процессоров от Intel (по прозвищу Haswell) предлагает еще больше аппаратной поддержки для манипулирования битами с расширениями BMI1 и BMI2 - возможно, там есть что-то еще для использования!