Какой самый быстрый способ перебрать большой кусок данных для каждого бита

Question

Я выполняю блок памяти двоичных данных побайтно.

В настоящее время я делаю что-то вроде этого:

for (i = 0; i < data->Count; i++)
{   
    byte = &data->Data[i];
    ((*byte & Masks[0]) == Masks[0]) ? Stats.FreqOf1++; // syntax incorrect but you get the point.
    ((*byte & Masks[1]) == Masks[1]) ? Stats.FreqOf1++;
    ((*byte & Masks[2]) == Masks[2]) ? Stats.FreqOf1++;
    ((*byte & Masks[3]) == Masks[3]) ? Stats.FreqOf1++;
    ((*byte & Masks[4]) == Masks[4]) ? Stats.FreqOf1++;
    ((*byte & Masks[5]) == Masks[5]) ? Stats.FreqOf1++;
    ((*byte & Masks[6]) == Masks[6]) ? Stats.FreqOf1++;
    ((*byte & Masks[7]) == Masks[7]) ? Stats.FreqOf1++;
}

Где Маски:

for (i = 0; i < 8; i++)
{
    Masks[i] = 1 << i;
}

(Мне как-то не удалось сделать это так быстро в цикле или во встроенной функции, поэтому я выписал это.)

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

Это может показаться глупостью. Но я нахожусь в процессе реализации алгоритма сжатия. Я просто хочу получить доступ к части внизу справа.

Спасибо!

PS: это в компиляторе Visual Studio 2008. Поэтому было бы неплохо, если бы предложения применялись к этому компилятору.

PPS: Я только что понял, что мне не нужно увеличивать два счета. Одного было бы достаточно. Затем вычислите разницу в общем количестве бит в конце. Но это было бы просто для подсчета. Что я действительно хочу сделать быстро, так это извлечение битов.

EDIT: Идея таблицы поиска, которая была выдвинута, хороша. Однако я понимаю, что поставил вопрос неправильно в названии. Потому что в итоге я хочу не считать биты, а получить доступ к каждому биту как можно быстрее.

ДРУГОЕ РЕДАКТИРОВАНИЕ: Можно ли продвинуть указатель на один бит в данных?

ДРУГОЕ РЕДАКТИРОВАНИЕ: Спасибо за все ваши ответы.

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

Возможна обработка 4 байта вместо 1 байта. Но цикл с 32 битами также дорог, не так ли?

Answer 1

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

Answer 2

См. Следующую ссылку для дюжины вещей, связанных с битами: Bit Twiddling Hacks

Answer 3

Используйте таблицу, которая отображает значение каждого байта (256) на количество единиц в нем. (Количество из 0 просто (8 - из 1)). Затем переберите байты и выполните один поиск для каждого байта вместо нескольких поисков и сравнений. Например:

int onesCount = 0;
for (i = 0; i < data->Count; i++)
{   
    byte = &data->Data[i];
    onesCount += NumOnes[byte];
}
Stats.FreqOf1 += onesCount;
Stats.FreqOf0 += (data->Count * 8) - onesCount;

Answer 4

Я не очень понял, что вы пытаетесь сделать. Но если вы просто хотите получить доступ к битам растрового изображения, вы можете использовать эти (непроверенные !!!) функции:

#include <stddef.h>

_Bool isbitset(unsigned char * bitmap, size_t idx)
{
    return bitmap[idx / 8] & (1 << (idx % 8)) ? 1 : 0;
}

void setbit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] |= (1 << (idx % 8));
}

void unsetbit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] &= ~(1 << (idx % 8));
}

void togglebit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] ^= (1 << (idx % 8));
}

Редактировать: Хорошо, я думаю Я понимаю, что вы хотите сделать: быстрая итерация по последовательности битов. Поэтому мы не хотим использовать функции произвольного доступа сверху, а читаем сразу целое слово данных.

Вы можете использовать любой беззнаковый целочисленный тип, но вам следует выбрать тот, который может соответствовать размеру слова вашей архитектуры. Я пойду с uint_fast32_t из stdint.h:

uint_fast32_t * data = __data_source__;
for(; __condition__; ++data)
{
    uint_fast32_t mask = 1;
    uint_fast32_t current = *data;
    for(; mask; mask <<= 1)
    {
        if(current & mask)
        {
            // bit is set
        }
        else
        {
            // bit is not set
        }
    }
}

Из внутреннего цикла вы можете установить бит с помощью

*data |= mask;

сбросить бит с помощью

*data &= ~mask;

и переключить бит с помощью

*data ^= mask;

Предупреждение: Код может неожиданно работать на архитектурах с прямым порядком байтов!

Answer 5

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

static int bitcount_lookup[256] = { ..... } ; /* or make it a global and compute the values in code */

...

for( ... ) 
   byte = ... 
   Stats.FreqOf1 += bitcount_lookup[byte];

Answer 6

ttobiass - имейте в виду, что ваши встроенные функции важны в приложениях, о которых вы говорите, но есть вещи, которые вы должны иметь в виду. Вы МОЖЕТЕ получить производительность из встроенного кода, просто запомните несколько вещей.

• Встроенный в режиме отладки не существует. (Если вы не заставите это)
• компилятор встроит функции так, как считает нужным. Часто, если вы скажете, что это встроенная функция, она может вообще этого не делать. Даже если вы используете __forceinline. Проверьте MSDN для получения дополнительной информации о встраивании.
• Только определенные функции могут быть встроены. Например, вы не можете встроить рекурсивную функцию.

Вы получите максимальную производительность от настроек проекта для языка C / C ++ и от того, как вы строите свой код. На этом этапе важно понимать операции «куча против стека», соглашения о вызовах, выравнивание памяти и т. Д.

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

Answer 7

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

int ones = 0;
int x = 0xdeadbeef;
for(int y = 0;y < 32;y++)
{
    if((x & 0x1) == 0x1) ones++;
    x = (x >> 1);
}

printf("%x contains %d ones and %d zeros.\n", x, ones, 32-ones);

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

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

С каждым рассматриваемым решением у каждого будут свои недостатки. Таблица поиска или немного сдвиг (как у меня), оба имеют недостатки.

Larry

Answer 8

Вот метод подсчета 1 бита 32-битного целого числа (на основе метода Java Integer.bitCount(i)):

unsigned bitCount(unsigned i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    i = (i + (i >> 4)) & 0x0f0f0f0f;
    i = i + (i >> 8);
    i = i + (i >> 16);
    return i & 0x3f;
}

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

Answer 9

Более быстрый способ извлечь биты - использовать:

bitmask= data->Data[i];

while (bitmask)
{
    bit_set_as_power_of_two= bitmask & -bitmask;
    bitmask&= bitmask - 1;
}

Если вы просто хотите посчитать установленные биты, LUT в кэше будет быстрым, но вы также можете сделать это в постоянное время с помощью метода подсчета чередующихся битов в ссылка в этом ответе .

Answer 10

В книге есть целая глава о различных методах для этого Красивый код . Вы можете прочитать (большинство) это в книгах Google , начиная здесь .