二进制中1的个数__11111111_count_int_flag_nativeOnenum_

当前位置: 编程技术>java/j2ee

二进制中1的个数

来源: 互联网发布时间：2014-10-28

本文导语: 前言最近会手写一些常考的面试题目，测试通过后会跟大家分享一下移位法仅适应于正数的做法：移位法就是每次判断n的二进制的最低位是否为1,时间复杂度为O(logn) 代码如下:int nativeOnenum(int n) { int count = 0; ...

前言
最近会手写一些常考的面试题目，测试通过后会跟大家分享一下

移位法
仅适应于正数的做法：

移位法就是每次判断n的二进制的最低位是否为1,时间复杂度为O(logn)

代码如下:

int nativeOnenum(int n)   
{   
    int count = 0;   

    while (n) {   
        if (n & 1)  count ++;   
        n >>= 1;   
    }   

    return count;   
}

对于正数没问题，但是如果n为负数，这里就出现问题了，以负数-8为例，二进制补码形式为11111111|11111111|11111111|11111000|,右移一位之后，变成了11111111|11111111|11111111|11111100|,因为是负数，所以符号位会一直补1,导致最后全1,出现死循环

针对这种情况，我们可以用变量flag =1,从右向左去和n比较，32位int最多比较32次即可知道n中1的数量

代码如下:

int oneNum(int n)   
{   
    int count, flag;   

    for (count = 0, flag = 1; flag; flag 

您可能感兴趣的文章:

本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术，将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外，均为转载、整理或搜集自网络。欢迎任何形式的转载，转载请注明出处。