我给出了两个算法来回答这个问题，

package countSetBitsInAnInteger;

import java.util.Scanner;

public class UsingLoop {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        try {
            System.out.println("Enter a integer number to check for set bits in it");
            int n = in.nextInt();
            System.out.println("Using while loop, we get the number of set bits as: " + usingLoop(n));
            System.out.println("Using Brain Kernighan's Algorithm, we get the number of set bits as: " + usingBrainKernighan(n));
            System.out.println("Using ");
        }
        finally {
            in.close();
        }
    }

    private static int usingBrainKernighan(int n) {
        int count = 0;
        while(n > 0) {
            n& = (n-1);
            count++;
        }
        return count;
    }

    /*
        Analysis:
            Time complexity = O(lgn)
            Space complexity = O(1)
    */

    private static int usingLoop(int n) {
        int count = 0;
        for(int i=0; i<32; i++) {
            if((n&(1 << i)) != 0)
                count++;
        }
        return count;
    }

    /*
        Analysis:
            Time Complexity = O(32) // Maybe the complexity is O(lgn)
            Space Complexity = O(1)
    */
}

几个悬而未决的问题:-

如果这个数是负的呢? 如果这个数字是1024，那么“迭代除以2”方法将迭代10次。

我们可以修改算法以支持负数:-

count = 0
while n != 0
if ((n % 2) == 1 || (n % 2) == -1
    count += 1
  n /= 2  
return count

现在为了克服第二个问题，我们可以编写这样的算法:-

int bit_count(int num)
{
    int count=0;
    while(num)
    {
        num=(num)&(num-1);
        count++;
    }
    return count;
}

完整参考请参见:

http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html

对于Java，有一个Java .util. bitset。 https://docs.oracle.com/javase/8/docs/api/java/util/BitSet.html

cardinality():返回在BitSet中设置为true的比特数。

BitSet是内存高效的，因为它被存储为Long类型。

def hammingWeight(n):
    count = 0
    while n:
        if n&1:
            count += 1
        n >>= 1
    return count

我发现了一个在数组中使用SIMD指令(SSSE3和AVX2)的位计数实现。它的性能比使用__popcnt64内禀函数要好2-2.5倍。

SSSE3版:

#include <smmintrin.h>
#include <stdint.h>

const __m128i Z = _mm_set1_epi8(0x0);
const __m128i F = _mm_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m128i T = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);

uint64_t BitCount(const uint8_t * src, size_t size)
{
    __m128i _sum =  _mm128_setzero_si128();
    for (size_t i = 0; i < size; i += 16)
    {
        //load 16-byte vector
        __m128i _src = _mm_loadu_si128((__m128i*)(src + i));
        //get low 4 bit for every byte in vector
        __m128i lo = _mm_and_si128(_src, F);
        //sum precalculated value from T
        _sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, lo)));
        //get high 4 bit for every byte in vector
        __m128i hi = _mm_and_si128(_mm_srli_epi16(_src, 4), F);
        //sum precalculated value from T
        _sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, hi)));
    }
    uint64_t sum[2];
    _mm_storeu_si128((__m128i*)sum, _sum);
    return sum[0] + sum[1];
}

AVX2 版本：

#include <immintrin.h>
#include <stdint.h>

const __m256i Z = _mm256_set1_epi8(0x0);
const __m256i F = _mm256_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m256i T = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
                                   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);

uint64_t BitCount(const uint8_t * src, size_t size)
{
    __m256i _sum =  _mm256_setzero_si256();
    for (size_t i = 0; i < size; i += 32)
    {
        //load 32-byte vector
        __m256i _src = _mm256_loadu_si256((__m256i*)(src + i));
        //get low 4 bit for every byte in vector
        __m256i lo = _mm256_and_si256(_src, F);
        //sum precalculated value from T
        _sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, lo)));
        //get high 4 bit for every byte in vector
        __m256i hi = _mm256_and_si256(_mm256_srli_epi16(_src, 4), F);
        //sum precalculated value from T
        _sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, hi)));
    }
    uint64_t sum[4];
    _mm256_storeu_si256((__m256i*)sum, _sum);
    return sum[0] + sum[1] + sum[2] + sum[3];
}

这不是最快或最好的解决方案，但我以自己的方式发现了同样的问题，我开始反复思考。最后我意识到它可以这样做，如果你从数学方面得到这个问题，画一个图，然后你发现它是一个有周期部分的函数，然后你意识到周期之间的差异……所以你看:

unsigned int f(unsigned int x)
{
    switch (x) {
        case 0:
            return 0;
        case 1:
            return 1;
        case 2:
            return 1;
        case 3:
            return 2;
        default:
            return f(x/4) + f(x%4);
    }
}