构造一个逻辑表达式，它将计算一个字节中的位
在采访新的候选者时，我们通常要求他们写一段C代码来计算给定字节变量中值为1的位数（例如，字节3有两个1位）。 我知道所有常见的答案，例如右移八次，或索引256个预先计算结果的常数表。
但是，如果不使用预先计算的表，是否有更聪明的方法？ 什么是字节操作（AND，OR，XOR，+， – ，二进制否定，左移和右移）的最短组合，它计算1位的数量？
至少有两种更快的解决方案，具有不同的性能特征：
-
减去一个和AND新旧值。 重复直到零。 计算迭代次数。 复杂度：O（B），其中B是一位的数量。
int bits(unsigned n) { for (int i = 0; n; ++i) { n &= n - 1; } return i; } -
添加一对位，然后是四个组，然后是八个组，直到达到字大小。 有一个技巧可以让你在一次通过中添加每个级别的所有组。 复杂度：O（log（N）），其中N是总位数。
int bits(uint32 n) { n = (n & 0x55555555) + ((n >> 1) & 0x55555555); n = (n & 0x33333333) + ((n >> 2) & 0x33333333); n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f); n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff); n = (n & 0x0000ffff) + (n >> 16); return n; }这个版本有点幼稚。 如果你考虑一下，你可以避免一些操作。
这是一个比特杂乱无章的方式列表
Java这样做（使用32位整数）（14次计算）
public static int bitCount(int i) { // HD, Figure 5-2 i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f; }
对于16位整数（短），该方法可以重写为：
private static int bitCount(int i) { // HD, Figure 5-2 i = i - ((i >>> 1) & 0x5555); i = (i & 0x3333) + ((i >>> 2) & 0x3333); i = (i + (i >>> 4)) & 0x0f0f; i = i + (i >>> 4); i = i + (i >>> 8); return i & 0x3f; }
对于8位整数（字节），它有点复杂，但总的想法是存在的。
有关快速位计数function的更多信息，请查看此链接： http ： //gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/
任何整数的最快/最简单的方法，对于最好的情况是O（0），对于最坏的情况是O（n）（其中n是值中的位数）是
static private int bitcount(int n) { int count = 0 ; while (n != 0) { count++ ; n &= (n - 1) ; } return count ; }