std::bitset<N>::count与__builtin_popcount的区别

Question

比较以下两个表达式

std::bitset<8>(5).count()
__builtin_popcount(5)

哪个更好？

- Milo Lu

---

我从未听说过第二个，所以在这方面，标准的是首选。此外，std::bitset 保证可移植性和行为一致性。 - Tas

"哪个更好？" 根据什么标准？正如 @Tas 已经提到的，标准版是可移植的。 - Fareanor

“更好”是什么？性能？可移植性？保证的行为？ - Holt

Answer 1

int  __builtin_popcount(unsigned int);

__builtin_popcount 是GCC内置函数，而 std::bitset<N>::count 则是C++的标准函数。

这两个函数的作用相同：返回被设为 true 的位数。

你应该使用哪一个函数？

尽量使用C++标准函数，因为其他编译器不支持 __builtin_popcount 函数。

更新

如果你查看Google基准测试工具所做的统计数据：

#include <bitset>

static void GccBuiltInPopCount(benchmark::State& state) {
    for (auto _ : state) {
        __builtin_popcount(5);
    }
}

BENCHMARK(GccBuiltInPopCount);

static void StdBitsetCount(benchmark::State& state) {
    for (auto _ : state) {
        std::bitset<8>(5).count();
    }
}

BENCHMARK(StdBitsetCount);

使用GCC 9.2和标志-std=c++2a -O3，GCC内置函数比std::bitset<N>::count()函数慢10％，但由于两个函数的ASM输出相同，基准测试中的差异可能是由其他因素引起的。

- NutCracker

---

考虑到两个源代码产生相同的代码，参见Denis的答案，我倾向于假设运行时差异是由其他因素引起的... - Aconcagua

@Aconcagua 实际上，-02 产生相同的汇编输出，但 -03 不会。 - NutCracker

尝试了上述两个链接并更改为-O3，仍然是一样的结果。也许在代码中不使用返回值对优化有些影响？我可以想象，在第二个示例中，由于该值根本没有被使用，因此对__popcountdi2的汇编器调用可能会被丢弃。 - Aconcagua

@Aconcagua 是的，那可能是原因。不过，我会注意到基准测试中的差异可能是由于其他因素造成的。建议仍然是相同的：std::bitset<N>::count()。 - NutCracker

完全同意该建议；不过我认为理由甚至更加强烈：即使我们发现这个扩展更快，除非在我们的应用程序中的时间关键部分使用标准库会出现性能瓶颈，否则我们仍应该选择标准库... - Aconcagua

两个函数的功能都是相同的：返回设置为true的位数。请注意，这两个函数并不等价。当“N == sizeof(unsigned int)”且传递正值时，这两个函数才是等价的。 - Holt

Answer 2

根据godbolt，最新的g++中bitset和popcount产生相同的汇编输出。然而，正如评论中所提到的，__builtin_popcount是gcc的扩展，在除x86以外的其他编译器和架构上都无法使用。因此，bitset选项显然更好。

- Denis Sheremet

---

我认为这已经是popcount的K.O.标准了。但是，使用popcount还受限于无符号整数，即通常为32位（有时甚至只有16位），而自C++11以来，bitset接受unsigned long long，允许（至少）64位（好吧，我们也可以使用位移和多次调用popcount，但那样做不太好看...）。 - Aconcagua

Answer 3

当你不知道 std::bitset<N>::count 中 N 的值时，我认为第二个更好。

更新： 你可以尝试使用 std::popcount。

- Kargath

---

对于运行时确定的位集大小，boost::dynamic_bitset 可用，并且还具有 count 方法。 - fjs