# 一、可能死循環的方法 給出通常能想到的方式，這兩種方式在《C和指針》一書中給出。以下討論的均為非負整數。 ~~~ /* 該方法每次在循環中判斷數的二進制最右一位是否為1（如果該數能不能被2整除）。 每次循環后該數右移一位。因此遍歷了數的二進制表示的每一位。 */ int count_one_bits1(int value) { int count; for (count = 0; value != 0; value >>= 1) if (value % 2 != 0) count++; return count; } /* 與上邊方法類似，也是每次將該數右移一位，遍歷該數的二進制表示的每一位。 不過這里是將該數與1做與運算，這樣，與的結果不為零則說明該數的二進制表示的最右一位為1。 */ int count_one_bits2(int value) { int count; for (count = 0; value != 0; value >>= 1) { if ((value & 1) != 0) count++; } return count; } //這里只是上述方法的另外一種寫法 int count_one_bits3(int value) { int count = 0; while (value) { if (value & 1) ++count; value >>= 1; } return count; } ~~~ 以上給出的方法當數為負數的時候會死循環。因為計算機中數是用二進制補碼表示的，負數右移其最高位補1（算術右移），那么如上的方法，會一直右移，不斷在最高位補1，最終數字變為0xffffffff而陷入死循環。參考文章[位運算的常見操作和題目](http://blog.csdn.net/u013074465/article/details/46686881) # 二、避免死循環的方法 為了避免死循環，不右移數字value，而是現將value和1做與運算，判斷最低位是否為1；接著把1做移一位得到2，再和value與運算，判斷value的次低位是否為1；依次下去……判斷value的每一位是否為1。32位整數要循環32次。 ~~~ int count_one_bits4(int value) { int count = 0; unsigned int flag = 1; //這里將flag設為無符號整型很重要 while (flag) { if (value & flag) ++count; flag = flag << 1; } return count; } ~~~ # 三、高效方法 ### 1、循環方法 下面介紹另外一種方式，可以通過比上述少的比較次數來統計出數的二進制表示中1的個數。 首先作如下分析： ? ? ? ?n & (n - 1)可以將n的二進制表示中最右側的一個1去掉，例如1100 減去1得到1011，那么 1100 & 1011得到1000，即將1100最右側的一個1去掉。如下函數每次循環就去掉其二進制表示中一個1，那么函數循環的次數就是其二進制表示中所含1的個數。 ~~~ int count_one_bits3(int value) { int count = 0; while (value) { ++count; value = value & (value - 1); //int v1 = value; //cout << value << " "; } cout << endl; return count; } ~~~ while循環結束的條件是value為0，也就是當value是2的n次冪時，下一次循環就結束了，因為2的n次冪的二進制表示中僅含有一個1。循環中value = value & (value - 1)使得每次循環后，value的二進制表示中1的個數少一個。該方法與前兩個方法比，循環的次數少。 如下圖，輸入value為8888，可以看出方法1執行while循環14次，方法3執行while循環6次。方法3每次循環后value的二進制中1的個數少一個。 **** ### **2、位移方法** **參考文章：[](#)[二進制位的翻轉和二進制表示中1的個數](http://blog.csdn.net/u013074465/article/details/45485959)**