c - 如何计算未知位数的整数类型的汉明权重(又名人口计数，即整数中 1 的位数)？

Question

在 C 中，如何有效地计算可变宽度类型的整数的汉明权重，例如uint_fast8_t 还是 uintmax_t？

• 我无法编码 shift and add算法，因为直到编译时我才知道数字中有多少位。
• 我不能使用 __builtin_popcount()函数族，因为我不知道给定类型对应于“unsigned int”、“unsigned long int”或“unsigned long long int”中的哪一个(如果有的话)。
• 我什至无法编写一个函数，它对每种可能的长度都有不同的情况，并在编译时选择正确的情况，因为 sizeof() 在预处理器条件中不可用。

注意事项:

• 我正在使用 GCC 进行编译
• 我更喜欢尽可能使用 __builtin_popcount() 函数的解决方案，这样我就可以在可用时利用处理器级 popcount 操作。
• 我没有主动针对任何不寻常的架构，因此假设所有整数类型都是 8 * 2^n 位长的解决方案是可以接受的，其中 0 <= n <= 4。也就是说，我的其余代码都与非典型字符或整数大小无关，因此最好保留该属性。

Answer 1

how can I efficiently calculate the Hamming weight of an integer which is of a variable-width type, e.g. uint_fast8_t or uintmax_t?

[...]

I am compiling using GCC

I would prefer a solution which uses the __builtin_popcount() functions

你可以根据 sizeof() 所讨论的类型编写一个 if/else 语句:

int weight(uintmax_t x) {
    if (sizeof x <= sizeof int) {
        return __builtin_popcount(x);
    else if (sizeof x <= sizeof long) {
        return __builtin_popcountl(x);
    else {
        return __builtin_popcountll(x);
    }
}

GCC 很有可能认识到关系表达式是编译时常量，因此将所有这些优化为仅调用适当的内置函数。

或者，您可以只使用__builtin_popcountll(x)；据我所知，GCC 不提供比 long long int 更宽的整数类型，因此在所有情况下都会产生正确的答案。

或者您可以确定在特定于机器的构建配置期间选择哪个替代方案(例如通过 Autoconf 或 CMake 测试)，并定义一个符号来指示 GCC 选择哪个可用变体。如果您意外遇到比 long long int 宽的整数类型，此变体还允许您提供回退。

其中任何一个(回退除外)都可以让您通过一次调用合适的内置函数来计算汉明权重。我认为这比需要多次调用的替代方案更能满足您对高效性能的明显兴趣。