題目

輸入一個整數，輸出該數二進制表示中1的個數。其中負數用補碼表示。

思路

把一個整數減去1，再和原整數做與運算，會把整數最右邊一個1變成0.那么一個整數的二進制表示中有多少個1，就可以進行多次這樣的操作。

代碼

/*--------------------------------------- * 日期：2015-07-20 * 作者：SJF0115 * 題目: 12.二進制中1的個數 * 結果：AC * 網址：http://www.nowcoder.com/books/coding-interviews/8ee967e43c2c4ec193b040ea7fbb10b8?rp=1 * 來源：劍指Offer * 博客： -----------------------------------------*/ #include <iostream> #include <vector> #include <string> #include <stack> #include <algorithm> using namespace std;class Solution { public:int NumberOf1(int n){int count = 0;while(n){n &= (n-1);++count;}//whilereturn count;} };int main(){Solution s;int n;while(cin>>n){int result = s.NumberOf1(n);// 輸出cout<<result<<endl;}//whilereturn 0; }

思路二

我們可能很快就有一個思路：先判斷整數二進制表示中最右邊一位是不是1.接著把輸入的整數右移一位，此時原來處于從右邊數起第二位被移到最右邊了，再判斷是不是1。這樣每次移動一位，直到整個整數變成0為止。基于這個思路我們寫完下面的程序。但是當我們輸入一個負數時，這個方法就會出現問題。比如0x80000000，把負數0x80000000右移一位時并不是簡單的把最高位的1移到第二位變成0x40000000，而是0xC0000000。這是因為移位前是個負數，仍然要保證移位后是個負數，因此移位后最高位仍然是1。如果一直做右移運算，最終這個數字就會變成0xFFFFFFFF而陷入死循環。

代碼二

class Solution { public:int NumberOf1(int n){int count = 0;while(n){if(n & 1){++count;}//ifn = n >> 1;}//whilereturn count;} };

思路三

為了避免死循環，我們可以不右移輸入的數字n。首先把n和1做與運算，判斷n的最低位是不是為1。接著把1左移一位得到2，再和n做與運算，就能判斷n的次低位是不是1…….這樣反復左移，每次都能判斷n的其中一位是不是1。

代碼三

/*--------------------------------------- * 日期：2015-07-20 * 作者：SJF0115 * 題目: 12.二進制中1的個數 * 結果：AC * 網址：http://www.nowcoder.com/books/coding-interviews/8ee967e43c2c4ec193b040ea7fbb10b8?rp=1 * 來源：劍指Offer * 博客： -----------------------------------------*/ #include <iostream> #include <vector> #include <string> #include <stack> #include <algorithm> using namespace std;class Solution { public:int NumberOf1(int n){int count = 0;int base = 1;while(base){if(n & base){++count;}//ifbase = base << 1;}//whilereturn count;} };int main(){Solution s;int n;while(cin>>n){int result = s.NumberOf1(n);// 輸出cout<<result<<endl;}//whilereturn 0; }

總結

以上是生活随笔為你收集整理的[剑指Offer]12.二进制中1的个数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。