首页 > 代码库 > 编程之美——二进制数中1的个数
编程之美——二进制数中1的个数
解法一：若二进制末尾为1，则除以2余1；
int count(int a){ int num=0; while(a) { if(a%2==1) ++num; a=a/2; } return num;}
解法二：使用移位操作相除：
int count(int a){ int num=0; while(a) { num+=a&0x01; a>>=1; } return num;}
解法三：以上两种算法复杂度log2(t)，t为a的二进制表示位数，若要求复杂度仅与二进制表示中1的个数相关，则有：
int count(int a){ int num=0; while(a) { a&=a-1; ++num; } return num;}
当然也可以采取查表法，以时间换空间，获得O(1)的复杂度；
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。