跨多个整数计算比特，有更快的方法吗？

Question

跨多个整数计算比特，有更快的方法吗？

5

我有一个由4个长整型组成的数组，我想在给定范围内计算设置位数的数量。这是我目前正在使用的函数（其中bitcount(uint64_t)是一个内联汇编函数，用于计算参数中设置的位数）：

unsigned count_bits(const uint64_t *long_ptr, size_t begin, size_t end)
{
    uint64_t start_mask = ~((1L << (begin & 63)) - 1);
    uint64_t end_mask = ((1L << (end & 63)) - 1);
    if (begin >= 0 && begin < 64) {
        if (end < 64) {
            return bitcount(long_ptr[0] & start_mask & end_mask);
        } else if (end < 128) {
            return bitcount(long_ptr[0] & start_mask) + bitcount(long_ptr[1] & end_mask);
        } else if (end < 192) {
            return bitcount(long_ptr[0] & start_mask) + bitcount(long_ptr[1]) + bitcount(long_ptr[2] & end_mask);
        } else if (end<256) {
            return bitcount(long_ptr[0] & start_mask) + bitcount(long_ptr[1]) + bitcount(long_ptr[2]) + bitcount(long_ptr[3] & end_mask);
        } else {
            return bitcount(long_ptr[0] & start_mask) + bitcount(long_ptr[1]) + bitcount(long_ptr[2]) + bitcount(long_ptr[3]);
        }
    } else if (begin >= 64 && begin < 128) {
        if (end < 128) {
            return bitcount(long_ptr[1] & start_mask & end_mask);
        } else if (end < 192) {
            return bitcount(long_ptr[1] & start_mask) + bitcount(long_ptr[2] & end_mask);
        } else if (end < 256) {
            return bitcount(long_ptr[1] & start_mask) + bitcount(long_ptr[2]) + bitcount(long_ptr[3] & end_mask);
        } else {
            return bitcount(long_ptr[1] & start_mask) + bitcount(long_ptr[2]) + bitcount(long_ptr[3]);
        }
    } else if (begin >= 128 && begin < 192) {
        if (end < 192) {
            return bitcount(long_ptr[2] & start_mask & end_mask);
        } else if (end < 256) {
            return bitcount(long_ptr[2] & start_mask) + bitcount(long_ptr[3] & end_mask);
        } else {
            return bitcount(long_ptr[2] & start_mask) + bitcount(long_ptr[3]);
        }
    } else if (begin<256) {
        if (end < 256) {
            return bitcount(long_ptr[3] & start_mask & end_mask);
        } else {
            return bitcount(long_ptr[3] & start_mask);
        }
    } else {
        return 0;
    }
}

我发现这段代码的性能相当不错，但我想知道是否有什么方法可以使它运行更快，或者重新设计算法是否能提高性能。

- markt1964

1

我认为你的问题是如何在多个整数中计算特定范围内设置的位数，而不仅仅是在一个整数中。请明确说明这一点，否则人们会快速浏览你的问题并对其进行假设。 - Neil Kirk

1

掩码表达式应该以1ULL开头，而不是1L。 - M.M

2

由于您似乎是要求现有的、可工作的代码进行审查，因此codereview.stackexchange.com是更适合发布的网站。 - M.M

2

我还没有运行过这个代码，但如果你有一个测试工具，可以尝试一下这个：

assert(begin <= end && end < 256); uint32_t tb = begin / 64; uint32_t te = end / 64; uint32_t ret = 0; uint64_t r; for (r = long_ptr[tb] & start_mask; tb < te ; tb++, r = long_ptr[tb]) { ret += bitcount(r); } return ret + bitcount(r & end_mask);

。虽然OP代码避免了循环，但我认为这段代码没有更多的比较/跳转。而且因为它更小，可能不会占用太多的代码缓存。无论如何，值得进行基准测试。 - David Wohlferd

如果你在x86上，其中未对齐的指针很快，那么从正确的字节开始可能是值得的，以避免一种情况，即你计算一个元素的7个字节和下一个元素的11个字节，而不是在未对齐的加载上执行一个掩码和计数。 - Peter Cordes

显示剩余6条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- VladimirS · Accepted Answer

我已经创建了两个不需要分支的版本，我认为应该选择David Wohlferd的评论，因为它更加紧凑。我不认为没有分支的版本会更快。处理器分支预测可以有效地消除一致数据上的跳转。而没有分支的版本将始终计算4次位数（除非使用SSE？）。在这里发布我的第二个（非常短）的无分支版本。第一个版本用于位运算比较复杂。

unsigned bitcount2(const uint64_t *long_ptr, size_t begin, size_t end)
{
    uint64_t mask[] = { 0, 0, 0, ~((1ULL << (begin & 63)) - 1), -1LL, -1LL, -1LL, ((1ULL << (end & 63)) - 1), 0, 0, 0 };
    uint64_t* b_start = mask+(3 - begin / 64);
    uint64_t* b_end = mask + (7 - end / 64);
    return bitcount(long_ptr[0] & b_start[0] & b_end[0]) +
        bitcount(long_ptr[1] & b_start[1] & b_end[1]) +
        bitcount(long_ptr[2] & b_start[2] & b_end[2]) +
        bitcount(long_ptr[3] & b_start[3] & b_end[3]);
}