面試題10：二進制中1的個數
題目：請實現一個函數，輸入一個整數，輸出該數二進制表示中 1 的個數。例如把9表示成二進制是1001，有2位是1。因此如果輸入9，該函數輸出2。

? 可能引起死循環的解法

代碼如下:

int CountNumbers(int n) {int count = 0;while (n){if (n & 1) count++;n = n >> 1;}return count; }

面試官看了代碼之后可能會問：把整數右移一位和把整數除以 2 在數學上是等價的，那上面的代碼中可以把右移運算換成除以 2 嗎？答案是否定的。因為除法的效率比移位運算要低得多，在實際編程中應盡可能地用移位運算符代替乘除法。

面試官接下來可能要問的第二個問題就是：上面的函數如果輸入一個負數，比如0x80000000，運行的時候會發生什么情況？
把負數0x80000000右移一位的時候，并不是簡單地把最高位的1移到第二位變成0x40000000，而是0xC0000000。這是因為移位前是個負數，仍然要保證移位后是個負數，因此移位后的最高位會設為1。
如果一直做右移運算，最終這個數字就會變成0xFFFFFFFF而陷入死循環。

? 常規解法
為了避免死循環，我們可以不右移輸入的數字i。首先把i和1做與運算，判斷i的最低位是不是為1。接著把1左移一位得到2，再和i做與運算，就能判斷i的次低位是不是1……這樣反復左移，每次都能判斷i的其中一位是不是1。基于這種思路，我們可以把代碼修改如下：

int CountNumbers(int n) {int count = 0;unsigned int flag = 1;while (flag){if (n & flag) count++;flag = flag << 1;}return count; }

這個解法中循環的次數等于整數二進制的位數，32 位的整數需要循環32次。

? 能給面試官帶來驚喜的解法

把一個整數減去1，再和原整數做與運算，會把該整數最右邊一個1變成0。那么一個整數的二進制表示中有多少個1，就可以進行多少次這樣的操作。基于這種思路，我們可以寫出新的代碼：

int CountNumbers(int n) {int count = 0;while (n){++count;n = (n - 1) & n;}return count; }

測試用例：
● 正數（包括邊界值1、0x7FFFFFFF）。
● 負數（包括邊界值0x80000000、0xFFFFFFFF）。
● 0。
本題考點：
● 考查對二進制及位運算的理解。
● 考查分析、調試代碼的能力。如果應聘者在面試過程中采用的是第一種思路，當面試官提示他輸入負數將會出現問題時，面試官會期待他能在心中運行代碼，自己找出運行出現死循環的原因。這要求應聘者有一定的調試功底。

總結

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

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