【校招编程07】求一个字节中“1”的个数效率最高的方法？

RENT A CAR TO TRAVEL

梦

想

更

进

一

步

INNOVATIVE  THINKING  TO  LEAD  THE  FUTURE

【校招编程】

【题目】对于一个字节（8bit）的数据，求其中“1”的个数，要求算法的执行效率尽可能的高。

【分析】这是一家著名外企的面试题，我们可能最先想到的是除、余操作法和位操作法。但这都不是最快的。最快的方法为本文的方法三，往下阅读吧！

方法一：除余法

//使用除、余操作
#include <stdio.h>
#define BYTE unsigned char
int main(void)
{
  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 /= 2;
  }
  printf("\nThe num of 1 in the BYTE is %d", num);
  return 0;
}

方法二：位操作

//使用位操作
#include <stdio.h>
#define BYTE unsigned char
int main(void)
{
  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;
}

方法三：查表法

#include <stdio.h>
#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(void)
{
  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",numTable[a]);
  return 0;
}

本题中，查表法是查找效率最高的解法，即也是一种用空间换取时间的解法。把0至255这256个数每个数中1的个数都事先计算好，然后保存到一个数组中。要查询的数的“1”的个数就是该数作为数组下标对应的元素。

关注并在后台回复关键字：sch007可获得本文代码

【推荐阅读】【2018年10月汇总】编程学习笔记

正念君编程学习笔记