对于那些想要在c++ 11中为任何无符号整数类型作为consexpr函数的人(tacklelib/include/tacklelib/utility/math.hpp):

#include <stdint.h>
#include <limits>
#include <type_traits>

const constexpr uint32_t uint32_max = (std::numeric_limits<uint32_t>::max)();

namespace detail
{
    template <typename T>
    inline constexpr T _count_bits_0(const T & v)
    {
        return v - ((v >> 1) & 0x55555555);
    }

    template <typename T>
    inline constexpr T _count_bits_1(const T & v)
    {
        return (v & 0x33333333) + ((v >> 2) & 0x33333333);
    }

    template <typename T>
    inline constexpr T _count_bits_2(const T & v)
    {
        return (v + (v >> 4)) & 0x0F0F0F0F;
    }

    template <typename T>
    inline constexpr T _count_bits_3(const T & v)
    {
        return v + (v >> 8);
    }

    template <typename T>
    inline constexpr T _count_bits_4(const T & v)
    {
        return v + (v >> 16);
    }

    template <typename T>
    inline constexpr T _count_bits_5(const T & v)
    {
        return v & 0x0000003F;
    }

    template <typename T, bool greater_than_uint32>
    struct _impl
    {
        static inline constexpr T _count_bits_with_shift(const T & v)
        {
            return
                detail::_count_bits_5(
                    detail::_count_bits_4(
                        detail::_count_bits_3(
                            detail::_count_bits_2(
                                detail::_count_bits_1(
                                    detail::_count_bits_0(v)))))) + count_bits(v >> 32);
        }
    };

    template <typename T>
    struct _impl<T, false>
    {
        static inline constexpr T _count_bits_with_shift(const T & v)
        {
            return 0;
        }
    };
}

template <typename T>
inline constexpr T count_bits(const T & v)
{
    static_assert(std::is_integral<T>::value, "type T must be an integer");
    static_assert(!std::is_signed<T>::value, "type T must be not signed");

    return uint32_max >= v ?
        detail::_count_bits_5(
            detail::_count_bits_4(
                detail::_count_bits_3(
                    detail::_count_bits_2(
                        detail::_count_bits_1(
                            detail::_count_bits_0(v)))))) :
        detail::_impl<T, sizeof(uint32_t) < sizeof(v)>::_count_bits_with_shift(v);
}

谷歌测试库中的附加测试:

#include <stdlib.h>
#include <time.h>

namespace {
    template <typename T>
    inline uint32_t _test_count_bits(const T & v)
    {
        uint32_t count = 0;
        T n = v;
        while (n > 0) {
            if (n % 2) {
                count += 1;
            }
            n /= 2;
        }
        return count;
    }
}

TEST(FunctionsTest, random_count_bits_uint32_100K)
{
    srand(uint_t(time(NULL)));
    for (uint32_t i = 0; i < 100000; i++) {
        const uint32_t r = uint32_t(rand()) + (uint32_t(rand()) << 16);
        ASSERT_EQ(_test_count_bits(r), count_bits(r));
    }
}

TEST(FunctionsTest, random_count_bits_uint64_100K)
{
    srand(uint_t(time(NULL)));
    for (uint32_t i = 0; i < 100000; i++) {
        const uint64_t r = uint64_t(rand()) + (uint64_t(rand()) << 16) + (uint64_t(rand()) << 32) + (uint64_t(rand()) << 48);
        ASSERT_EQ(_test_count_bits(r), count_bits(r));
    }
}

这就是所谓的“汉明权重”，“popcount”或“横向相加”。

一些cpu有单独的内置指令来做这件事，而另一些cpu有并行指令来处理位向量。像x86的popcnt(在支持它的cpu上)这样的指令几乎肯定对单个整数来说是最快的。其他一些架构可能有一个缓慢的指令，实现了一个微编码循环，每个周期测试一个比特(需要引用-硬件popcount通常是快速的，如果它存在的话。)

“最佳”算法实际上取决于你所使用的CPU以及你的使用模式。

Your compiler may know how to do something that's good for the specific CPU you're compiling for, e.g. C++20 std::popcount(), or C++ std::bitset<32>::count(), as a portable way to access builtin / intrinsic functions (see another answer on this question). But your compiler's choice of fallback for target CPUs that don't have hardware popcnt might not be optimal for your use-case. Or your language (e.g. C) might not expose any portable function that could use a CPU-specific popcount when there is one.

---

不需要(或受益于)任何硬件支持的可移植算法

如果您的CPU有一个很大的缓存，并且您在一个紧密的循环中执行大量这些操作，那么预先填充的表查找方法可以非常快。然而，它可能会因为“缓存丢失”的代价而受到影响，在这种情况下，CPU必须从主存中获取一些表。(分别查找每个字节以保持表小。)如果你想要popcount的连续范围的数字，只有低字节改变的组256个数字，这是非常好的。

如果你知道你的字节大部分是0或1，那么就有针对这些情况的有效算法，例如在循环中使用bithack清除最低的集合，直到它变成0。

我相信一个非常好的通用算法是以下，称为“并行”或“可变精度SWAR算法”。我已经在一个类似C的伪语言中表达了这一点，你可能需要调整它以适用于特定的语言(例如使用uint32_t for c++和>>> in Java):

GCC10和clang 10.0可以识别这种模式/习惯用法，并在可用时将其编译为硬件popcnt或等效指令，为您提供两全其美的服务。(https://godbolt.org/z/qGdh1dvKK)

int numberOfSetBits(uint32_t i)
{
     // Java: use int, and use >>> instead of >>. Or use Integer.bitCount()
     // C or C++: use uint32_t
     i = i - ((i >> 1) & 0x55555555);        // add pairs of bits
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);  // quads
     i = (i + (i >> 4)) & 0x0F0F0F0F;        // groups of 8
     return (i * 0x01010101) >> 24;          // horizontal sum of bytes
}

对于JavaScript:强制为整数|0的性能:更改第一行为i = (i|0) - ((i >> 1) & 0x55555555);

这是所有讨论过的算法中最糟糕的行为，因此可以有效地处理您抛出的任何使用模式或值。(它的性能不依赖于普通cpu的数据，在普通cpu中，包括乘法在内的所有整数操作都是常量时间。“简单”输入不会让它变得更快，但它仍然相当不错。)

引用:

https://graphics.stanford.edu/~seander/bithacks.html https://catonmat.net/low-level-bit-hacks用于bithack基础知识，例如如何减去1翻转连续的零。 https://en.wikipedia.org/wiki/Hamming_weight http://gurmeet.net/puzzles/fast-bit-counting-routines/ http://aggregate.ee.engr.uky.edu/MAGIC/人口% 20计数% 20(% 20计数)

---

这个SWAR bithack如何工作:

i = i - ((i >> 1) & 0x55555555);

第一步是屏蔽的优化版本，以隔离奇数/偶数位，移动以对齐它们，并添加。这有效地在2位累加器(SWAR = SIMD Within A Register)中进行16个独立的加法。比如(i & 0x55555555) + ((i>>1) & 0x55555555)。

下一步是取这16个2位累加器中的奇/偶8个，然后再次相加，得到8个4位累加器。我…这次不可能进行优化，所以它只是在移动之前/之后进行遮罩。使用相同的0x33…两次都是常量，而不是0xccc…在为需要单独在寄存器中构造32位常量的isa编译时，在移位之前进行转换是一件好事。

(i + (i >> 4)) & 0x0F0F0F0F的最后一个移位和添加步骤将扩大为4个8位累加器。它在加后而不是加前进行掩码，因为如果设置了所有对应的4位输入位，则任何4位累加器中的最大值为4。4+4 = 8仍然适合4位，所以在I + (I >> 4)中，啃食元素之间的进位是不可能的。

到目前为止，这只是使用SWAR技术和一些聪明的优化的相当普通的SIMD。继续相同的模式2步可以扩大到2x 16位，然后1x 32位计数。但在硬件快速相乘的机器上，有一种更有效的方法:

一旦我们有足够少的“元素”，一个神奇常数的乘法可以把所有的元素加起来变成最上面的元素。在本例中是字节元素。乘法是通过左移和加法完成的，因此x * 0x01010101的乘法得到x + (x<<8) + (x<<16) + (x<<24)。我们的8位元素足够宽(并且包含足够小的计数)，因此不会产生进位到前8位。

它的64位版本可以使用0x0101010101010101乘数在64位整数中处理8x 8位元素，并使用>>56提取高字节。所以它不需要任何额外的步骤，只是更大的常数。这是当硬件popcnt指令未启用时，GCC在x86系统上对__builtin_popcountll使用的方法。如果您可以为此使用内置或内在函数，那么这样做可以让编译器有机会进行特定于目标的优化。

---

对于更宽的向量具有完整的SIMD(例如计算整个数组)

这种逐位swar算法可以在多个向量元素中同时进行并行运算，而不是在单个整数寄存器中进行并行运算，从而在具有SIMD但没有可用popcount指令的cpu上实现加速。(例如x86-64代码必须在任何CPU上运行，而不仅仅是Nehalem或更高版本。)

然而，对popcount使用矢量指令的最佳方法通常是使用变量-shuffle并行地对每个字节每次4位进行表查找。(4位索引保存在向量寄存器中的16项表)。

在Intel cpu上，硬件64位popcnt指令的性能比SSSE3 PSHUFB位并行实现的性能好2倍，但前提是编译器的性能恰到好处。否则，上交所可能会大幅领先。较新的编译器版本意识到popcnt对Intel的错误依赖问题。

https://github.com/WojciechMula/sse-popcount state-of-the-art x86 SIMD popcount for SSSE3, AVX2, AVX512BW, AVX512VBMI, or AVX512 VPOPCNT. Using Harley-Seal across vectors to defer popcount within an element. (Also ARM NEON) Counting 1 bits (population count) on large data using AVX-512 or AVX-2 related: https://github.com/mklarqvist/positional-popcount - separate counts for each bit-position of multiple 8, 16, 32, or 64-bit integers. (Again, x86 SIMD including AVX-512 which is really good at this, with vpternlogd making Harley-Seal very good.)

对于232查找表和逐个遍历每个位之间的折中方法:

int bitcount(unsigned int num){
    int count = 0;
    static int nibblebits[] =
        {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
    for(; num != 0; num >>= 4)
        count += nibblebits[num & 0x0f];
    return count;
}

从http://ctips.pbwiki.com/CountBits

我觉得很无聊，于是对三种方法进行了十亿次迭代。编译器是gcc -O3。CPU就是第一代Macbook Pro里装的东西。

最快的是3.7秒:

static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 };
static int popcount( unsigned int i )
{
    return( wordbits[i&0xFFFF] + wordbits[i>>16] );
}

第二名是相同的代码，但查找的是4个字节而不是2个半字。这花了大约5.5秒。

第三名是“横向加法”法，用时8.6秒。

第四名是GCC的__builtin_popcount()，仅为11秒。

一次一个比特的计数方法要慢得多，我厌倦了等待它完成。

因此，如果您最关心的是性能，那么请使用第一种方法。如果您关心它，但又不想在上面花费64Kb的RAM，那么可以使用第二种方法。否则，请使用可读的(但速度较慢)一次一位的方法。

很难想象在什么情况下你会想要使用比特旋转方法。

编辑:这里也有类似的结果。

我特别喜欢这个来自《财富》的例子:

#define BITCOUNT(x)    (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x)         ((x) - (((x)>>1)&0x77777777)
                             - (((x)>>2)&0x33333333)
                             - (((x)>>3)&0x11111111))

我最喜欢它，因为它太漂亮了!

当你写出比特模式时，“黑客的喜悦”比特旋转变得更加清晰。

unsigned int bitCount(unsigned int x)
{
  x = ((x >> 1) & 0b01010101010101010101010101010101)
     + (x       & 0b01010101010101010101010101010101);
  x = ((x >> 2) & 0b00110011001100110011001100110011)
     + (x       & 0b00110011001100110011001100110011); 
  x = ((x >> 4) & 0b00001111000011110000111100001111)
     + (x       & 0b00001111000011110000111100001111); 
  x = ((x >> 8) & 0b00000000111111110000000011111111)
     + (x       & 0b00000000111111110000000011111111); 
  x = ((x >> 16)& 0b00000000000000001111111111111111)
     + (x       & 0b00000000000000001111111111111111); 
  return x;
}

第一步将偶数位加到奇数位上，产生每两个位的和。其他步骤将高阶数据块添加到低阶数据块，将数据块的大小一直增加一倍，直到最终计数占用整个int。