一个字节中的1的个数

编写一个 C 函数，该函数给出一个字节中被置 1 的位的个数，并请给出该题至少一个不同解法。

void oneofchar()
{
 unsigned char ch = 0x77;
 unsigned char temp = 1;
 int i,j=0;
 for(i = 0;i<8;i++)
 {
  if((ch & temp) != 0)
   j++;
  temp = temp << 1;
 }
 printf("0x%x\n",ch);
 printf("Count = %d \n",j);
}

上面的解法确实有点傻了。

下面是根据判断32位整数二进制中1的个数的算法文章来模仿的四种算法。

unsigned int FindOneInNumber_01(unsigned char x)

{

    unsigned int n;

    for(n=0; x; x >>= 1)

        if (x & 1) n++;

    return n;

}

unsigned int FindOneInNumber_02(unsigned char x)

{

   unsigned int n;

   for(n=0; x; n++)

      x &= x-1;

    return n;

}

unsigned FindOneInNumber_03(unsigned char x)

{

    const unsigned MASK1  = 0x5555;

    const unsigned MASK2  = 0x3333;

    const unsigned MASK4  = 0x0f0f;

 

    x = (x&MASK1 ) + (x>>1 &MASK1 );

    x = (x&MASK2 ) + (x>>2 &MASK2 );

    x = (x&MASK4 ) + (x>>4 &MASK4 );

    return x;

}

unsigned numbits_lookup_table[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

};

unsigned FindOneInNumber_04(unsigned char x)

{

    unsigned n;

    n = numbits_lookup_table[x & 0xff];

    n += numbits_lookup_table[x>>8  & 0xff];
  

    return n;

}