Get-1bit-from-1byte.rar_C++ 字节 位

求一个字节（8bit）有几位为"1"的O(1)解 宋宝华 软件报 问题：对于一个字节（8bit）的数据，求其中“1”的个数，要求算法的执行效率尽可能地高。 分析：作为一道著名外企的面试题，看似简单，实则可以看出一个程序员的基本功底的扎实程度。你或许已经 想到很多方法，譬如除、余操作，位操作等，但都不是最快的。本文一步步分析，直到最后给出一个最快的方 法，相信你看到本文最后的那个最快的方法时会有惊诧的感觉。 解答： 首先，很自然的，你想到除法和求余运算，并给出了如下的答案： 方法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; } 方法三看似很直接，实际执行效率可能还会小于方法二，因为分支语句的执行情况要看具体字节的值，如果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” 不知道嵌入式那点内存是否允许鼓励这样做。