二进制中1的个数

时间:2022-06-06 10:46:08

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

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

移位法就是每次判断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 <<= 1) {   
        if (flag & n)   count ++;   
    }   

    return count;   
}


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

复制代码代码如下:


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

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

    return count;   
}