求二进制数中1的个数

假设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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容