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

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)
    */
}

大约在1990年，我为RISC机器编写了一个快速比特计数宏。它不使用高级算术(乘法，除法，%)，内存提取(太慢)，分支(太慢)，但它确实假设CPU有一个32位的桶移位器(换句话说，>> 1和>> 32占用相同的周期)。它假定小常数(如6、12、24)加载到寄存器中不需要花费任何代价，或者存储在临时变量中并反复重用。

在这些假设下，在大多数RISC机器上，它在大约16个周期/指令中计算32位。注意，15条指令/周期接近于周期或指令数量的下界，因为似乎至少需要3条指令(掩码、移位、运算符)才能将加数的数量减半，因此log_2(32) = 5,5 x 3 = 15条指令是准下界。

#define BitCount(X,Y)           \
                Y = X - ((X >> 1) & 033333333333) - ((X >> 2) & 011111111111); \
                Y = ((Y + (Y >> 3)) & 030707070707); \
                Y =  (Y + (Y >> 6)); \
                Y = (Y + (Y >> 12) + (Y >> 24)) & 077;

这是第一步也是最复杂的一步:

input output
AB    CD             Note
00    00             = AB
01    01             = AB
10    01             = AB - (A >> 1) & 0x1
11    10             = AB - (A >> 1) & 0x1

所以如果我取上面的第一列(A)，右移1位，然后从AB减去它，我就得到了输出(CD)。扩展到3位类似;如果你愿意，你可以用一个8行布尔表来检查它。

不吉利

对于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

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

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。

这可以在O(k)中完成，其中k是设置的比特数。

int NumberOfSetBits(int n)
{
    int count = 0;

    while (n){
        ++ count;
        n = (n - 1) & n;
    }

    return count;
}

我认为Brian Kernighan的方法也很有用… 它的迭代次数和设置位个数一样多。因此，如果我们有一个32位的单词，只设置了高位，那么它将只经过一次循环。

int countSetBits(unsigned int n) { 
    unsigned int n; // count the number of bits set in n
    unsigned int c; // c accumulates the total bits set in n
    for (c=0;n>0;n=n&(n-1)) c++; 
    return c; 
}

出版于1988年的C编程语言第二版(由Brian W. Kernighan和Dennis M. Ritchie编写)在练习2-9中提到了这一点。2006年4月19日，Don Knuth向我指出，这种方法“是由Peter Wegner在CACM 3(1960)， 322中首次发表的。(同样由德里克·莱默(Derrick Lehmer)独立发现，并于1964年在贝肯巴赫(Beckenbach)编辑的一本书中出版。)