C++快速有效地在40字节数组上执行bit_count和AND操作的方法

Question

在我的项目中,我需要AND两个大小为40字节(320位)的二进制数组,然后在C++中计算设置位数.我找到了一些算法来做这个,但我想知道在c ++中实现它的最快方法是什么.我的意思是什么c ++数据类型是正确的？(unsinged char*,unsigned int 32,u_int64,...).我知道许多算法与32位整数兼容,尽管我的数组大小是40字节.

那个链接中描述的算法怎么样: 快速位计数技术哪个更快？

const类型更好还是没有区别？

任何帮助将非常感激.

Answer 1

这是一个版本,它同时通过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;
}

使用编译器内在函数,使用现代CPU可以更快地完成此任务.例如,在使用Visual C++的64位CPU上:

#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++);

但是这一切都考虑到了性能,如果你只是想要一些可读的代码,那肯定与Rob建议的一致.

Answer 2

我的意思是什么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());

如果替代方案的速度要快得多,只需使用上面的代码即可.它将清楚地表达您的意图,并将避免以后的维护问题.