c++ - 位摆弄黑客 : most efficient way to remove one bit every n bits?

Question

这是我的问题:

我需要在 C 或 C++11 中非常高效地执行此操作(我需要在 super 计算机上执行此操作数十亿次)。 N 和 n 在编译时已知(模板参数)。最有效的算法是什么？

这是一个例子:

#include <iostream>
#include <climits>
#include <type_traits>
#include <bitset>

template <unsigned int Modulo,
          typename Type,
          unsigned int Size = sizeof(Type)*CHAR_BIT,
          class = typename std::enable_if<std::is_integral<Type>::value
                                       && std::is_unsigned<Type>::value>::type>
inline Type f(Type x)
{
    // The most inefficient algorithm ever
    std::bitset<Size> bx(x);
    std::bitset<Size> by(0);
    unsigned int j = 0;
    for (unsigned int i = 0; i < Size; ++i) {
        if (i%Modulo) {
            by[j++] = bx[i];
        }
    }
    return by.to_ullong();
}

int main()
{
    std::bitset<64> x = 823934823;
    std::cout<<x<<std::endl;
    std::cout<<(std::bitset<64>(f<2>(x.to_ullong())))<<std::endl;
    return 0;
}

Answer 1

语义优先...

语义上(和概念上，因为你实际上不能在这里使用迭代器)，你正在做一个 std::copy_if您的输入和输出范围是 std::bitset<N>并且您的谓词是以下形式的 lambda(使用 C++14 通用 lambda 表示法)

[](auto elem) { return elem % n != 0; }

这个算法有O(N)赋值次数和谓词调用次数的复杂性。因为std::bitset<N>没有迭代器，你必须一点一点地检查。这意味着带有手写谓词的循环正在执行与 std::copy_if 完全相同的计算。在假设的可迭代 std::bitset<N> 上.

这意味着就渐近效率而言，您的算法不应被视为低效。

...最后优化

因此，鉴于您的算法没有像二次复杂度那样糟糕的结论，是否可以优化其常数因子？ std::bitset效率的主要来源这是因为您的硬件可以并行处理许多(8、16、32 或 64)位。如果您有权访问该实现，您可以编写自己的 copy_if它利用了这种并行性，例如通过特殊的硬件指令、查找表或一些 bit-twiddling algorithm .

例如这就是成员函数 count() 的方式，以及 gcc 和 SGI 扩展 Find_first_()和 Find_next_()被实现。旧的 SGI 实现使用 256 个条目的查找表来处理位计数和对每个 8 位 char 的位的准迭代。 .最新的 gcc 版本使用 __builtin_popcountll()和 __builtin_ctzll()对每个 64 位字进行人口计数和位查找。

不幸的是，std::bitset不公开其底层无符号整数数组。所以如果你想改进你发布的算法，你需要自己写BitSet类模板(可以通过调整你自己的标准库的源代码)并给它一个成员函数 copy_if (或类似的)利用您的硬件。与您当前的算法相比，它可以将效率提高 8 到 64 倍。