二進(jìn)制中1的個(gè)數(shù)

2019-11-26 15:57:32

字體：大中小

供稿：網(wǎng)友

前言
最近會手寫一些常考的面試題目，測試通過后會跟大家分享一下

移位法
僅適應(yīng)于正數(shù)的做法：

移位法就是每次判斷n的二進(jìn)制的最低位是否為1,時(shí)間復(fù)雜度為O(logn)

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

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

    return count;   
}

對于正數(shù)沒問題，但是如果n為負(fù)數(shù)，這里就出現(xiàn)問題了，以負(fù)數(shù)-8為例，二進(jìn)制補(bǔ)碼形式為11111111|11111111|11111111|11111000|,右移一位之后，變成了11111111|11111111|11111111|11111100|,因?yàn)槭秦?fù)數(shù)，所以符號位會一直補(bǔ)1,導(dǎo)致最后全1,出現(xiàn)死循環(huán)

針對這種情況，我們可以用變量flag =1,從右向左去和n比較，32位int最多比較32次即可知道n中1的數(shù)量

復(fù)制代碼代碼如下:

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

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

    return count;   
}

快速法
這種解法的思路是，二進(jìn)制中1的個(gè)數(shù)只與1的位數(shù)有關(guān)，n & (n - 1)快速的去掉最左邊的1，例如7（0111） & 6（0110）= 6（0110）,快速的去掉了最左邊的1

復(fù)制代碼代碼如下:

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

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

    return count;   
}