首页 > 代码库 > 【剑指offer】二进制中1的个数
【剑指offer】二进制中1的个数
题目描述:
请实现一个函数,输入一个整数,输出该数二进制表示中1的个数。例如把9表示成二进制是1001,有2位是1。因此如果输入9,该函数输出2。
分析描述:
1、对一个整数的二进制形式,要想知道其中1的个数,首先想到的应该就是遍历整个二进制数,用到的方法当然就是移动了(包含左移或右移)。例如,用1来跟给定的整数做与运算。如果结果为1,则证明整数的二进制形式中,最右边的一位是1,如果结果是0,则证明整数的二进制形式中,最右边的一位是0。
int NumberOf1(int n) { int count = 0; while(n){ if(n & 1) count++; n = n >> 1; } }
这种方法有一个bug,当n是负数时,右移一位的时候,不能简单地把最高位1移到第二位,因为如果移位前是个负数,仍然要保证移位后是个负数,因此移位后的最高位会设为1。如果一直做右移运算,最终整数会变成0xFFFFFFFF而陷入死循环。
2、针对上面分析的bug,可以不对n移到,而是对1移动,每次与整数n做完与操作后,就左移一位1……反复左移,每次都能判断整数的某一位是否为1。
int NumberOf1(int n) { int count = 0; unsigned int flag = 1; while(flag){ if(n & flag) count++; flag = flag << 1; } return count; }
3、还有一种更加巧妙的办法:当把一个整数减去1,再和原整数做与运算,会把该整数最右边一个1变成0。那么一个整数的二进制表示中有多少个1,就可以进行多少次这样的操作。
int NumberOf1(int n) { int count = 0; while(n) { ++count; n = (n - 1) & n; } return count; }
技巧:把一个整数减去1之后再和原来的整数做位与运算,得到的结果相当于是把整数的二进制表示中的最右边一个1变成0。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。