我认为最快的方法——不使用查找表和popcount——是以下方法。它仅通过12次操作来计数设置位。

int popcount(int v) {
    v = v - ((v >> 1) & 0x55555555);                // put count of each 2 bits into those 2 bits
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits  
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

它之所以有效，是因为你可以通过将设置位分为两半来计算总设置位的数量，计算两半设置位的数量，然后将它们相加。也被称为分而治之范式。让我们来详细谈谈。

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

两位位数可以是0b00、0b01或0b10。让我们试着在2位上解决这个问题。

 ---------------------------------------------
 |   v    |   (v >> 1) & 0b0101   |  v - x   |
 ---------------------------------------------
   0b00           0b00               0b00   
   0b01           0b00               0b01     
   0b10           0b01               0b01
   0b11           0b01               0b10

这就是所需要的:最后一列显示每两个位对中设置位的计数。如果两个比特数>= 2 (0b10)，则产生0b01，否则产生0b00。

v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 

这句话应该很容易理解。在第一个操作之后，我们每两个比特中就有一个set位的计数，现在我们每4个比特中就有一个set位的计数。

v & 0b00110011         //masks out even two bits
(v >> 2) & 0b00110011  // masks out odd two bits

然后我们把上面的结果加起来，得到4位的集合位总数。最后一个陈述是最棘手的。

c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

让我们进一步分析一下……

v + (v >> 4)

这和第二种说法很相似;我们以4为一组来计数集合位。因为我们之前的运算，我们知道每一个咬痕都有一个集合位的计数。让我们看一个例子。假设我们有字节0b01000010。这意味着第一个啃食有它的4位设置，第二个有它的2位设置。现在我们把这些小块加在一起。

v = 0b01000010
(v >> 4) = 0b00000100
v + (v >> 4) = 0b01000010 + 0b00000100

它为我们提供了一个字节中set位的计数，在第二个nibble 0b01000110中，因此我们掩码了该数字中所有字节的前四个字节(丢弃它们)。

0b01000110 & 0x0F = 0b00000110

现在每个字节都有一个集合位的计数。我们需要把它们全部加起来。诀窍是将结果乘以0b10101010，它有一个有趣的属性。如果我们的数字有四个字节，A B C D，它将产生一个新的数字，包含这些字节A+B+C+D B+C+D C+D。一个4字节的数字最多可以设置32位，可以表示为0b00100000。

我们现在需要的是第一个字节，它是所有字节中所有set位的和，我们通过>> 24得到它。该算法是为32位字设计的，但可以很容易地修改为64位字。

我提供了另一个未提及的算法，称为并行，从这里取。它的优点是它是通用的，这意味着代码对于8、16、32、64和128位大小是相同的。

我检查了它的值的正确性和时间的数量为2^26位大小为8,16,32和64位。请看下面的时间安排。

该算法是第一个代码片段。这里提到另外两个只是为了参考，因为我测试和比较了它们。

算法是用c++编写的，是通用的，但它可以很容易地应用到旧的C中。

#include <type_traits>
#include <cstdint>

template <typename IntT>
inline size_t PopCntParallel(IntT n) {
    // https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
    using T = std::make_unsigned_t<IntT>;

    T v = T(n);
    v = v - ((v >> 1) & (T)~(T)0/3);                           // temp
    v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3);      // temp
    v = (v + (v >> 4)) & (T)~(T)0/255*15;                      // temp
    return size_t((T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * 8); // count
}

下面是我比较的两种算法。一个是带有循环的Kernighan简单方法，从这里开始。

template <typename IntT>
inline size_t PopCntKernighan(IntT n) {
    // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
    using T = std::make_unsigned_t<IntT>;
    T v = T(n);
    size_t c;
    for (c = 0; v; ++c)
        v &= v - 1; // Clear the least significant bit set
    return c;
}

另一个是使用内置的__popcnt16()/__popcnt()/__popcnt64() MSVC的内在(doc在这里)。或CLang/GCC (doc)的__builtin_popcount。这个内在应该提供一个非常优化的版本，可能是硬件:

#ifdef _MSC_VER
    // https://learn.microsoft.com/en-us/cpp/intrinsics/popcnt16-popcnt-popcnt64?view=msvc-160
    #include <intrin.h>
    #define popcnt16 __popcnt16
    #define popcnt32 __popcnt
    #define popcnt64 __popcnt64
#else
    // https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
    #define popcnt16 __builtin_popcount
    #define popcnt32 __builtin_popcount
    #define popcnt64 __builtin_popcountll
#endif

template <typename IntT>
inline size_t PopCntBuiltin(IntT n) {
    using T = std::make_unsigned_t<IntT>;
    T v = T(n);
    if constexpr(sizeof(IntT) <= 2)
        return popcnt16(uint16_t(v));
    else if constexpr(sizeof(IntT) <= 4)
        return popcnt32(uint32_t(v));
    else if constexpr(sizeof(IntT) <= 8)
        return popcnt64(uint64_t(v));
    else
        static_assert([]{ return false; }());
}

以下是计时，以纳秒为单位。所有的计时都是对2^26个随机数进行的。比较了所有三种算法的计时以及8、16、32和64之间的所有比特大小。总的来说，所有测试在我的机器上花费了16秒。使用了高分辨率时钟。

08 bit Builtin 8.2 ns
08 bit Parallel 8.2 ns
08 bit Kernighan 26.7 ns

16 bit Builtin 7.7 ns
16 bit Parallel 7.7 ns
16 bit Kernighan 39.7 ns

32 bit Builtin 7.0 ns
32 bit Parallel 7.0 ns
32 bit Kernighan 47.9 ns

64 bit Builtin 7.5 ns
64 bit Parallel 7.5 ns
64 bit Kernighan 59.4 ns

128 bit Builtin 7.8 ns
128 bit Parallel 13.8 ns
128 bit Kernighan 127.6 ns

可以看到，所提供的并行算法(在三个算法中排名第一)与MSVC /CLang的固有算法一样好。

作为参考，下面是我用来测试所有函数的速度/时间/正确性的完整代码。

作为奖励，这段代码(不像上面的短代码片段)也测试128位大小，但只在CLang/GCC下(不是MSVC)，因为它们有unsigned __int128。

在网上试试!

#include <type_traits>
#include <cstdint>

using std::size_t;

#if defined(_MSC_VER) && !defined(__clang__)
    #define IS_MSVC 1
#else
    #define IS_MSVC 0
#endif

#if IS_MSVC
    #define HAS128 false
#else
    using int128_t = __int128;
    using uint128_t = unsigned __int128;
    #define HAS128 true
#endif

template <typename T> struct UnSignedT { using type = std::make_unsigned_t<T>; };
#if HAS128
    template <> struct UnSignedT<int128_t> { using type = uint128_t; };
    template <> struct UnSignedT<uint128_t> { using type = uint128_t; };
#endif
template <typename T> using UnSigned = typename UnSignedT<T>::type;

template <typename IntT>
inline size_t PopCntParallel(IntT n) {
    // https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
    using T = UnSigned<IntT>;

    T v = T(n);
    v = v - ((v >> 1) & (T)~(T)0/3);                           // temp
    v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3);      // temp
    v = (v + (v >> 4)) & (T)~(T)0/255*15;                      // temp
    return size_t((T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * 8); // count
}

template <typename IntT>
inline size_t PopCntKernighan(IntT n) {
    // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
    using T = UnSigned<IntT>;
    T v = T(n);
    size_t c;
    for (c = 0; v; ++c)
        v &= v - 1; // Clear the least significant bit set
    return c;
}

#if IS_MSVC
    // https://learn.microsoft.com/en-us/cpp/intrinsics/popcnt16-popcnt-popcnt64?view=msvc-160
    #include <intrin.h>
    #define popcnt16 __popcnt16
    #define popcnt32 __popcnt
    #define popcnt64 __popcnt64
#else
    // https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
    #define popcnt16 __builtin_popcount
    #define popcnt32 __builtin_popcount
    #define popcnt64 __builtin_popcountll
#endif

#define popcnt128(x) (popcnt64(uint64_t(x)) + popcnt64(uint64_t(x >> 64)))

template <typename IntT>
inline size_t PopCntBuiltin(IntT n) {
    using T = UnSigned<IntT>;
    T v = T(n);
    if constexpr(sizeof(IntT) <= 2)
        return popcnt16(uint16_t(v));
    else if constexpr(sizeof(IntT) <= 4)
        return popcnt32(uint32_t(v));
    else if constexpr(sizeof(IntT) <= 8)
        return popcnt64(uint64_t(v));
    else if constexpr(sizeof(IntT) <= 16)
        return popcnt128(uint128_t(v));
    else
        static_assert([]{ return false; }());
}

#include <random>
#include <vector>
#include <chrono>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>

inline double Time() {
    static auto const gtb = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::duration<double>>(
        std::chrono::high_resolution_clock::now() - gtb).count();
}

template <typename T, typename F>
void Test(std::string const & name, F f) {
    std::mt19937_64 rng{123};
    size_t constexpr bit_size = sizeof(T) * 8, ntests = 1 << 6, nnums = 1 << 14;
    std::vector<T> nums(nnums);
    for (size_t i = 0; i < nnums; ++i)
        nums[i] = T(rng() % ~T(0));
    static std::map<size_t, size_t> times;
    double min_time = 1000;
    for (size_t i = 0; i < ntests; ++i) {
        double timer = Time();
        size_t sum = 0;
        for (size_t j = 0; j < nnums; j += 4)
            sum += f(nums[j + 0]) + f(nums[j + 1]) + f(nums[j + 2]) + f(nums[j + 3]);
        auto volatile vsum = sum;
        min_time = std::min(min_time, (Time() - timer) / nnums);
        if (times.count(bit_size) && times.at(bit_size) != sum)
            std::cout << "Wrong bit cnt checksum!" << std::endl;
        times[bit_size] = sum;
    }
    std::cout << std::setw(2) << std::setfill('0') << bit_size
        << " bit " << name << " " << std::fixed << std::setprecision(1)
        << min_time * 1000000000 << " ns" << std::endl;
}

int main() {
    #define TEST(T) \
        Test<T>("Builtin", PopCntBuiltin<T>); \
        Test<T>("Parallel", PopCntParallel<T>); \
        Test<T>("Kernighan", PopCntKernighan<T>); \
        std::cout << std::endl;
    
    TEST(uint8_t); TEST(uint16_t); TEST(uint32_t); TEST(uint64_t);
    #if HAS128
        TEST(uint128_t);
    #endif
    
    #undef TEST
}

我个人使用这个:

  public static int myBitCount(long L){
      int count = 0;
      while (L != 0) {
         count++;
         L ^= L & -L; 
      }
      return count;
  }

我认为最快的方法——不使用查找表和popcount——是以下方法。它仅通过12次操作来计数设置位。

int popcount(int v) {
    v = v - ((v >> 1) & 0x55555555);                // put count of each 2 bits into those 2 bits
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits  
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

它之所以有效，是因为你可以通过将设置位分为两半来计算总设置位的数量，计算两半设置位的数量，然后将它们相加。也被称为分而治之范式。让我们来详细谈谈。

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

两位位数可以是0b00、0b01或0b10。让我们试着在2位上解决这个问题。

 ---------------------------------------------
 |   v    |   (v >> 1) & 0b0101   |  v - x   |
 ---------------------------------------------
   0b00           0b00               0b00   
   0b01           0b00               0b01     
   0b10           0b01               0b01
   0b11           0b01               0b10

这就是所需要的:最后一列显示每两个位对中设置位的计数。如果两个比特数>= 2 (0b10)，则产生0b01，否则产生0b00。

v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 

这句话应该很容易理解。在第一个操作之后，我们每两个比特中就有一个set位的计数，现在我们每4个比特中就有一个set位的计数。

v & 0b00110011         //masks out even two bits
(v >> 2) & 0b00110011  // masks out odd two bits

然后我们把上面的结果加起来，得到4位的集合位总数。最后一个陈述是最棘手的。

c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

让我们进一步分析一下……

v + (v >> 4)

这和第二种说法很相似;我们以4为一组来计数集合位。因为我们之前的运算，我们知道每一个咬痕都有一个集合位的计数。让我们看一个例子。假设我们有字节0b01000010。这意味着第一个啃食有它的4位设置，第二个有它的2位设置。现在我们把这些小块加在一起。

v = 0b01000010
(v >> 4) = 0b00000100
v + (v >> 4) = 0b01000010 + 0b00000100

它为我们提供了一个字节中set位的计数，在第二个nibble 0b01000110中，因此我们掩码了该数字中所有字节的前四个字节(丢弃它们)。

0b01000110 & 0x0F = 0b00000110

现在每个字节都有一个集合位的计数。我们需要把它们全部加起来。诀窍是将结果乘以0b10101010，它有一个有趣的属性。如果我们的数字有四个字节，A B C D，它将产生一个新的数字，包含这些字节A+B+C+D B+C+D C+D。一个4字节的数字最多可以设置32位，可以表示为0b00100000。

我们现在需要的是第一个字节，它是所有字节中所有set位的和，我们通过>> 24得到它。该算法是为32位字设计的，但可以很容易地修改为64位字。

Kotlin 1.4 之前

        fun NumberOfSetBits(i: Int): Int {
            var i = i
            i -= (i ushr 1 and 0x55555555)
            i = (i and 0x33333333) + (i ushr 2 and 0x33333333)
            return (i + (i ushr 4) and 0x0F0F0F0F) * 0x01010101 ushr 24
        }

这或多或少是上面那个答案的翻版。

它带有Java补丁，然后使用IntelliJ IDEA Community Edition中的转换器进行转换

1.4及以上(截至2021-05-05 -未来可能会改变)。

        fun NumberOfSetBits(i: Int): Int {
            return i.countOneBits()
        }

在底层，它使用Integer。bitCount如下所示:

@SinceKotlin("1.4")
@WasExperimental(ExperimentalStdlibApi::class)
@kotlin.internal.InlineOnly
public actual inline fun Int.countOneBits(): Int = Integer.bitCount(this)

Java JDK1.5

Integer.bitCount (n);

其中n是要计算1的数。

检查,

Integer.highestOneBit(n);
Integer.lowestOneBit(n);
Integer.numberOfLeadingZeros(n);
Integer.numberOfTrailingZeros(n);

//Beginning with the value 1, rotate left 16 times
     n = 1;
         for (int i = 0; i < 16; i++) {
            n = Integer.rotateLeft(n, 1);
            System.out.println(n);
         }