一道著名外企面试题的抽丝剥茧

: xilinxue

2008-11-10

问题：对于一个字节（8bit）的数据，求其中“1”的个数，要求算法的执行效率尽可能地高。
分析：作为一道著名外企的面试题，看似简单，实则可以看出一个程序员的基本功底的扎实程度。你或许已经
想到很多方法，譬如除、余操作，位操作等，但都不是最快的。本文一步步分析，直到最后给出一个最快的方
法，相信你看到本文最后的那个最快的方法时会有惊诧的感觉。
解答：
首先，很自然的，你想到
#include
#define BYTE unsigned char
int main(int argc, char *argv[])
{
int i, num = 0;
BYTE a;
/* 接收用户输入 */
printf("\nPlease Input a BYTE(0~255):");
scanf("%d", &a);
/* 计算1 的个数 */
for (i = 0; i < 8; i++)
{
if (a % 2 == 1)
{
num++;
}
a = a / 2;
}
printf("\nthe num of 1 in the BYTE is %d", num);
return 0;
}
很遗憾，众所周知，除法操作的运算速率实在是很低的，这个答案只能意味着面试者被淘汰！
好，精明的面试者想到了以位操作代替除法和求余操作，并给出如下答案：
方法2：使用位操作
#include
#define BYTE unsigned char
int main(int argc, char *argv[])
{
int i, num = 0;
BYTE a;
/* 接收用户输入 */
printf("\nPlease Input a BYTE(0~255):");
scanf("%d", &a);
/* 计算1 的个数 */
for (i = 0; i < 8; i++)
{
num += (a >> i) &0x01;
}
/*或者这样计算1 的个数：*/
/* for(i=0;i<8;i++)
{
if((a>>i)&0x01)
num++;
}
*/
printf("\nthe num of 1 in the BYTE is %d", num);
return 0;
}
方法二中num += (a >> i) &0x01;操作的执行效率明显高于方法一中的
if (a % 2 == 1)
{
num++;
}
a = a / 2;
到这个时候，面试者有被录用的可能性了，但是，难道最快的就是这个方法了吗？没有更快的了吗？方法二真
的高山仰止了吗？
能不能不用做除法、位操作就直接得出答案的呢？于是你想到把0~255 的情况都罗列出来，并使用分支操作，
给出如下答案：
方法3：使用分支操作
#include
#define BYTE unsigned char
int main(int argc, char *argv[])
{
int i, num = 0;
BYTE a;
/* 接收用户输入 */
printf("\nPlease Input a BYTE(0~255):");
scanf("%d", &a);
/* 计算1 的个数 */
switch (a)
{
case 0x0:
num = 0;
break;
case 0x1:
case 0x2:
case 0x4:
case 0x8:
case 0x10:
case 0x20:
case 0x40:
case 0x80:
num = 1;
break;
case 0x3:
case 0x6:
case 0xc:
case 0x18:
case 0x30:
case 0x60:
case 0xc0:
num = 2;
break;
//...
}
printf("\nthe num of 1 in the BYTE is %d", num);
return 0;
}

xilinxue

楼主 2008/11/10 13:18:53

方法三看似很直接，实际执行效率可能还会小于方法二，因为分支语句的执行情况要看具体字节的值，如果a=0，
那自然在第1 个case 就得出了答案，但是如果a=255，则要在最后一个case 才得出答案，即在进行了255
次比较操作之后！
看来方法三不可取！但是方法三提供了一个思路，就是罗列并直接给出值，离最后的方法四只有一步之遥。眼
看着就要被这家著名外企录用，此时此刻，绝不对放弃寻找更快的方法。
终于，灵感一现，得到方法四，一个令你心潮澎湃的答案，快地令人咋舌，算法中不需要进行任何的运算。你
有足够的信心了，把下面的答案递给面试官：
方法4：直接得到结果
#include
#define BYTE unsigned char
/* 定义查找表 */
BYTE numTable[256] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,
3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3,
4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,
3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3,
4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4,
5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3,
4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4,
4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6,
7, 6, 7, 7, 8
};
int main(int argc, char *argv[])
{
int i, num = 0;
BYTE a = 0;
/* 接收用户输入 */
printf("\nPlease Input a BYTE(0~255):");
scanf("%d", &a);
/* 计算1 的个数 */
/* 用BYTE 直接作为数组的下标取出1 的个数，妙哉！ */
printf("\nthe num of 1 in the BYTE is %d", checknum[a]);
return 0;
}
这是个典型的空间换时间算法，把0~255 中1 的个数直接存储在数组中，字节a 作为数组的下标，checknum[a]
直接就是a 中“1”的个数！算法的复杂度如下：
时间复杂度：O(1)
空间复杂度：O(2n)
恭喜你，你已经被这家著名的外企录用！老总向你伸出手，说：“Welcome to our company”。

控制工程师论坛

教程与手册

一道著名外企面试题的抽丝剥茧

xilinxue

xilinxue