在面试新候选人时,我们通常要求他们编写一段 C 代码来计算给定字节变量中值为 1 的位数(例如,字节 3 有两个 1 位)。我知道所有常见的答案,例如右移八次,或索引 256 个预计算结果的常量表。
但是,不使用预计算表有没有更聪明的方法?计算 1 位数的字节操作(AND、OR、XOR、+、-、二进制否定、左移和右移)的最短组合是什么?
在面试新候选人时,我们通常要求他们编写一段 C 代码来计算给定字节变量中值为 1 的位数(例如,字节 3 有两个 1 位)。我知道所有常见的答案,例如右移八次,或索引 256 个预计算结果的常量表。
但是,不使用预计算表有没有更聪明的方法?计算 1 位数的字节操作(AND、OR、XOR、+、-、二进制否定、左移和右移)的最短组合是什么?
至少有两种更快的解决方案,具有不同的性能特征:
减去一个并 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 位整数(字节),它有点复杂,但一般的想法是存在的。
您可以查看此链接以获取有关快速位计数功能的更多信息: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 ;
}