bytearray — C ++ Быстрый и эффективный способ выполнения операций bit_count и AND на 40-байтовом массиве

Question

bytearray — C ++ Быстрый и эффективный способ выполнения операций bit_count и AND на 40-байтовом массиве

В моем проекте мне нужно AND два двоичных массива размером 40 байтов (320 бит), а затем вычислить установленный счетчик битов в C ++. Я нашел несколько алгоритмов, чтобы сделать это, но я хочу знать, какой самый быстрый способ реализовать это в C ++. Я имею в виду, какой тип данных c ++ будет правильным? (Беззнаковый char *, unsigned int 32, u_int64, …). Я знаю, что многие алгоритмы совместимы с 32-битным целым числом, хотя мой размер массива составляет 40 байт.

как насчет алгоритмов, описанных в этой ссылке:
Методы быстрого подсчета битов какой из них быстрее?

Константный тип лучше или разницы нет?

Любая помощь приветствуется.

1

bit-manipulation bitcount bytearray c++

Решение

Другие решения

Я имею в виду, что тип данных C ++ будет правильным?

std::bitset<320>,

Любой алгоритм, который вы придумаете, следует сравнить по скорости и удобству с этим:

std::bitset<320> first;
std::bitset<320> other;

// twiddle bits here ...

std::bitset<320> and_result(first & other);
std::size_t number_of_bits(and_result.count());

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

5

Нечто подобное должно быть достаточно быстрым:

const uint8_t LUT[256] = { 0, 1, 1, 2, ..., 8 }; // pop count LUT for bytes

int count_bits(const uint8_t *a1, const uint8_t *a2, int n)
{
int count = 0;

for (int i = 0; i < n; ++i)
{
count += LUT[a1[i] & a2[i]];
}
return count;
}

Это три загрузки и две операции ALU на байт, то есть 120 загрузок и 80 операций ALU для вашего 40-байтового варианта использования.

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

2

Источник

Accepted Answer

Вот версия, которая проходит через массив с 4 байтами одновременно, требуя 10 итераций:

uint32_t *arr1_int = (uint32_t*) arr1;
uint32_t *arr2_int = (uint32_t*) arr2;
int i;
int bits_set = 0;

for (i = 0; i < 10; i++) {
uint32_t v = arr1_int[i] & arr2_int[i];

/* http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel */
v = v - ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
bits_set += ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

Вы можете сделать это намного быстрее с современным процессором, используя встроенные функции компилятора. Например, на 64-битном процессоре с Visual C ++:

#include <intrin.h>

__int64 *arr1_int = (__int64*) arr1;
__int64 *arr2_int = (__int64*) arr2;
int bits_set = 0;

/* 40 / 8 bytes == 5 iterations */
bits_set += __popcnt64(*arr1_int++ & *arr2_int++);
bits_set += __popcnt64(*arr1_int++ & *arr2_int++);
bits_set += __popcnt64(*arr1_int++ & *arr2_int++);
bits_set += __popcnt64(*arr1_int++ & *arr2_int++);
bits_set += __popcnt64(*arr1_int++ & *arr2_int++);

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

5