1

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

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

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

任何帮助将非常感激。

4

3 回答 3

6

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

如果替代方案没有明显更快，只需使用上述代码。它将清楚地表达您的意图，并将避免以后的维护问题。

于 2012-09-27T22:07:19.183 回答
6

这是一个版本，它一次通过 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 的建议。

于 2012-09-27T22:07:23.033 回答
2

像这样简单的东西应该足够快：

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

每个字节有 3 次加载和 2 次 ALU 操作，即 40 字节用例的 120 次加载和 80 次 ALU 操作。

试一试，分析它，如果它不够快，那么您可以查看可能更快的更复杂的解决方案。

于 2012-09-27T22:08:03.910 回答