当前位置：首页 > 资讯 > 技术文档

二进制中1的个数

时间：2021-08-18 16:34 编辑：来源：阅读：
扫一扫，手机访问

摘要：二进制中1的个数

前言最近会手写一些常考的面试题目，测试通过后会跟大家分享一下移位法仅适应于正数的做法：移位法就是每次判断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的数量

[u]复制代码[/u] 代码如下:

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

    for (count = 0, flag = 1; flag; flag <<= 1) {  
        if (flag & n)   count ++;  
    }  

    return count;  
}

快速法这种解法的思路是，二进制中1的个数只与1的位数有关，n & (n - 1)快速的去掉最左边的1，例如7（0111） & 6（0110）= 6（0110）,快速的去掉了最左边的1

[u]复制代码[/u] 代码如下:

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

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

    return count;  
}

全部评论(0)

上一篇：Java线程的生命周期和状态控制_动力节点Java学院整理
下一篇：Java设计模式之工厂方法模式实例简析

资讯排行榜
更多>>