什么是算在UInt32的设置位的最快方法(What is the fastest way to co

什么是设置位计数的数量以最快的方式（即计数1秒的数量）在UInt32不使用查找表的？ 有没有办法在计算O(1)

Answer 1:

是重复的： 如何做-实施-位计数-使用-只-按位运算符或最佳算法对计数的用户号码的设置位-IN-A-32位整数

而且有对这个问题许多解决方案。 我使用的一个是：

    int NumberOfSetBits(int i)
    {
        i = i - ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
    }

Answer 2:

该位摆弄黑客网页有多种选择。

当然，你可以争辩说，遍历所有32位可能为O（N），因为它的每一次相同的成本:)

为简单起见，我会考虑的查找表，每字节的方法，或布赖恩Kernighan的整洁的想法它迭代，因为有位设置，这我是写很多次：

public static int CountBits(uint value)
{
    int count = 0;
    while (value != 0)
    {
        count++;
        value &= value - 1;
    }
    return count;
}

如果你不喜欢填充256条目查找表的想法，查找每半字节仍然是相当快的。 你要知道，它可能是8名阵列查找可能会慢于32个简单位操作。

当然，它的价值才去特别深奥的方式测试你的应用程序的真实表现......这真的是一个瓶颈吗？

Answer 3:

这是Java中的解决方案，使给定数量的设置位。

import java.util.*;

public class HelloWorld {

static int setBits(int n) {
    int count = 0;
    while(n != 0) {
        count+= ((n & 1) == 1) ? 1 : 0;
        n >>= 1;

    }
    return count;
}

 public static void main(String []args){
     Scanner sc = new Scanner(System.in);
     int n = sc.nextInt();
     System.out.println("Results: " + HelloWorld.setBits(n)); 
 }
}

文章来源: What is the fastest way to count set bits in UInt32