我总是在竞争性编程中使用它，它很容易写，而且效率很高:

#include <bits/stdc++.h>

using namespace std;

int countOnes(int n) {
    bitset<32> b(n);
    return b.count();
}

几个悬而未决的问题:-

如果这个数是负的呢? 如果这个数字是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

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

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

32位还是32位?我只是在阅读了“破解编码面试”第4版练习5.5(第5章:位操作)后，在Java中使用了这种方法。如果最小有效位是1个增量计数，则右移该整数。

public static int bitCount( int n){
    int count = 0;
    for (int i=n; i!=0; i = i >> 1){
        count += i & 1;
    }
    return count;
}

我认为这个比常数0x33333333的解更直观，不管它们有多快。这取决于你对“最佳算法”的定义。

你可以:

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

这背后的逻辑是n-1位从n的最右边的集合位倒出来。

如果n=6，即110，那么5是101，位从n的最右边的集合位倒出来。

因此，如果我们&这两个，我们将在每次迭代中使最右边的位为0，并且总是到下一个最右边的集位。因此，计数设置位。当每一位都被设置时，最糟糕的时间复杂度将是O(log n)。

在我看来，“最好”的解决方案是另一个程序员(或者两年后的原始程序员)可以阅读而不需要大量注释的解决方案。你可能想要最快或最聪明的解决方案，有些人已经提供了，但我更喜欢可读性而不是聪明。

unsigned int bitCount (unsigned int value) {
    unsigned int count = 0;
    while (value > 0) {           // until all bits are zero
        if ((value & 1) == 1)     // check lower bit
            count++;
        value >>= 1;              // shift bits, removing lower bit
    }
    return count;
}

如果你想要更快的速度(并且假设你很好地记录了它，以帮助你的继任者)，你可以使用表格查找:

// Lookup table for fast calculation of bits set in 8-bit unsigned char.

static unsigned char oneBitsInUChar[] = {
//  0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F (<- n)
//  =====================================================
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, // 0n
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // 1n
    : : :
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, // Fn
};

// Function for fast calculation of bits set in 16-bit unsigned short.

unsigned char oneBitsInUShort (unsigned short x) {
    return oneBitsInUChar [x >>    8]
         + oneBitsInUChar [x &  0xff];
}

// Function for fast calculation of bits set in 32-bit unsigned int.

unsigned char oneBitsInUInt (unsigned int x) {
    return oneBitsInUShort (x >>     16)
         + oneBitsInUShort (x &  0xffff);
}

这些依赖于特定的数据类型大小，所以它们不是那么可移植的。但是，由于许多性能优化是不可移植的，这可能不是一个问题。如果您想要可移植性，我会坚持使用可读的解决方案。