分类： C/C++
2012-03-22 15:49:24
Q: 对于一个字节的（8bit）无符整形变量，求其二进制表示中“1”的个数，要求算法执行效率尽可能高。
A：
#include
using namespace std;
int count1(unsigned char v);
int count2(unsigned char v);
int count3(unsigned char v);
int count4(unsigned char v);
int count5(unsigned char v);
int main()
{
unsigned char v = 7;
cout<
return 0;
}
/**
*解法1：
*除法，当除以2余1时，则最低位为1
*时间复杂度为O( log2(v) ),log2(v)为二进制的位数
**/
int count1(unsigned char v)
{
int num = 0;
while(v)
{
if(1 == v%2)
num++;
v = v / 2;
}
return num;
}
/**
*解法2：
*移位操作，与0x01相与，判断最后一位是否为1，然后右移1位
*移位操作的效率要比除法运算的高
*时间复杂度为O( log2(v) ),log2(v)为二进制的位数
*/
int count2(unsigned char v)
{
int num = 0;
while(v)
{
num += v & 0x01;
v >>= 1;
}
return num;
}
/**
*解法3：
*将二进制数减1后与原数相与，得到的结果比原数少一个1
*由此可以只通过1的个数次运算得到结果
*时间复杂度为O(M),M为v中1的个数
*/
int count3(unsigned char v)
{
int num = 0;
while(v)
{
v &= v-1;
num++;
}
return num;
}
/**
*解法4：
*使用分支操作，罗列所有的情况，空间换取时间
*但次法效率可能要低于解法2、3，因v取值不同，进行比较运算
*的次数不同，最差情况要比较255次
*/
int count4(unsigned char v)
{
int num = 0;
switch(v)
{
case 0x00:
num = 0;
break;
case 0x01:
case 0x02:
case 0x04:
case 0x08:
case 0x10:
case 0x20:
case 0x40:
case 0x80:
num = 1;
break;
case 0x03:
case 0x06:
case 0xc:
case 0x18:
case 0x30:
case 0x60:
case 0xc0:
num = 2;
break;
//...
}
return num;
}
/**
*解法5：
*查表法，将256种情况的结果直接存在数组中,通过空间换取时间
*算法复杂度为O(1)
*/
int count5(unsigned char v)
{
int countTable[256]=
{
0,1,1,2,1,2,2,3,1,2,2//...
};
if(v<0 && v>255)
exit(1);
return countTable[v];
}
