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

Question

在采访新的候选者时,我们通常会要求他们写一段C代码来计算给定字节变量中值为1的位数(例如,字节3有两个1位).我知道所有常见的答案,例如右移八次,或索引256个预先计算结果的常数表.

但是,如果没有使用预先计算的表,是否有更聪明的方法？什么是字节操作(AND,OR,XOR,+, - ,二进制否定,左移和右移)的最短组合,它计算1位的数量？

Answer 1

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

1. 减一并与新值和旧值。重复直到零。计算迭代次数。复杂度：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;
   }
   

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