c - 构造一个逻辑表达式，它将计算一个字节中的位

Question

在面试新候选人时，我们通常要求他们编写一段 C 代码来计算给定字节变量中值为 1 的位数（例如，字节 3 有两个 1 位）。我知道所有常见的答案，例如右移八次，或索引 256 个预计算结果的常量表。

但是，不使用预计算表有没有更聪明的方法？计算 1 位数的字节操作（AND、OR、XOR、+、-、二进制否定、左移和右移）的最短组合是什么？

Answer 1

至少有两种更快的解决方案，具有不同的性能特征：

1. 减去一个并 AND 新旧值。重复直到零。计算迭代次数。复杂度：O(B)，其中 B 是一位数。

   int bits(unsigned n)
   {
       for (int i = 0; n; ++i)
       {
           n &= n - 1;
       }
       return i;
   }
   

2. 添加位对，然后是四个一组，然后是八个一组，直到达到字长。有一个技巧可以让您一次添加每个级别的所有组。复杂度：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;
   }
   

   这个版本有点幼稚。稍微想一想，可以避免一些操作。

Answer 2

这是Bit twiddling hacks的方法列表

Answer 3

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 位整数（字节），它有点复杂，但一般的想法是存在的。

您可以查看此链接以获取有关快速位计数功能的更多信息：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 ;
}