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

題目描述

輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)。其中負(fù)數(shù)用補(bǔ)碼表示。

解題思路：

• 思路1：直接去掉二進(jìn)制中位置最靠后的1。假設(shè)n=1100，則n-1=1011，那么n&(n-1)=1000,位置最靠后的1被去掉。 時(shí)間復(fù)雜度O(M), M為1的個(gè)數(shù)
• 思路2：利用標(biāo)志位遍歷int的32位; 時(shí)間復(fù)雜度O(1), 32次循環(huán)

注：負(fù)數(shù)右移后，最高位補(bǔ)1，如果右移判斷最低位將導(dǎo)致死循環(huán)

解答：

// 方法1
class Solution {
public:
    int NumberOf1(int n) {
        int cnt = 0;
        while(n != 0)
        {
            n = n & (n-1);
            cnt++;
        }
        return cnt;
    }
};
// 方法2:
class Solution {
public:
     int  NumberOf1(int n) {
         int cnt = 0;
         int flag = 1;
         while(flag != 0)
         {
             if((n & flag) != 0)
                 ++cnt;
             flag = flag << 1;
         }
         return cnt;
     }
};

大家有興趣可以訪問(wèn)我的個(gè)人博客，不定時(shí)更新一些內(nèi)容哦！

圖片來(lái)自必應(yīng)壁紙