有许多算法来计数设置位;但是我认为最好的一个是更快的一个! 您可以在本页查看详细信息:

Bit Twiddling Hacks

我建议这样做:

使用64位指令计数在14,24或32位字中设置的位

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v

// option 1, for at most 14-bit values in v:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;

// option 2, for at most 24-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) 
     % 0x1f;

// option 3, for at most 32-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 
     0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

这种方法需要64位CPU和快速模除法来提高效率。第一个选项只需要3个操作;第二种选择需要10;第三种选择需要15分钟。

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

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

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

    return count;
}

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

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

#!/user/local/bin/perl


    $c=0x11BBBBAB;
     $count=0;
     $m=0x00000001;
    for($i=0;$i<32;$i++)
    {
        $f=$c & $m;
        if($f == 1)
        {
            $count++;
        }
        $c=$c >> 1;
    }
    printf("%d",$count);

ive done it through a perl script. the number taken is $c=0x11BBBBAB   
B=3 1s   
A=2 1s   
so in total  
1+1+3+3+3+2+3+3=19

为什么不迭代地除以2呢?

count = 0
while n > 0
  if (n % 2) == 1
    count += 1
  n /= 2  

我同意这不是最快的，但是“最好”这个词有点含糊不清。我认为“最好”应该有一个清晰的元素

另一个汉明权重算法，如果你使用的是BMI2 CPU:

the_weight = __tzcnt_u64(~_pext_u64(data[i], data[i]));