假设8位二进制数为v,
解法1:将v不断地做模2运算,计算余数为1的次数。
解法2:解法1的改进,除2的时候用移位,移位后和0x01做与运算,就可得到最后一位是否为1,再累加起来得到结果。
复杂度:O(log2v)。
解法3:直接上代码:
int Count(BYTE v)
{
int num = 0;
whiel(v)
{
v &= (v-1);//这一步很有意思,效果是使得低位的1变成0;
num++;
}
return num;
}
解法4:采用空间换时间的作法,把0~255中“1”的个数直接存储在数组中,v作为数组的下标,这样算法的时间复杂度仅为O(1)。
另外,这里有一篇扩展阅读,上面有更快的方法,但是我水平较低,看得不是很懂,只好先把链接放上来了:http://blog.csdn.net/justpub/article/details/2292823。