題目來源：牛客網-劍指Offer專題
題目地址：二進制中1的個數

題目描述

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

題目解析

對于這種涉及位運算的題目，我們首先要了解基本的位運算，我們可以看這篇文章：C++描述的位運算總結

（PS：本文的圖例用的是8位的整數，int有32位，畫出來也不美觀呀）

下面先給說一種因為存在負數而錯誤的做法：

• 先通過 ‘&1’ 操作來判斷 $n$ 的最低位否為1，若為1，則計數器 $cnt$ 的值加1；
• 然后利用 ‘>>1’ 操作將 $n$ 右移一位；
• 最后重復上述兩步操作，直到 $n$ 的值為0，得出 $cnt$ 的值即為該數二進制表示中1的個數。

這種方法在 $n$ 為正數的時候是沒有問題的，因為正數進行右移操作的時，最低位舍棄，最高位補0。過程如圖所示：

但是負數進行右移操作的時，最低位舍棄，最高位的是1（過程如下圖），這樣經過多次以后，所有數位都會變成1，進而產生死循環。

下面給大家一共四種不同的正確解法：

方法一：
利用Integer內置的toBinaryString()方法將 $n$ 轉換為二進制字符串，然后二進制串中的0全部消掉，最后求得的字符串長度就是該數二進制表示中1的個數。

public class Solution {public int NumberOf1(int n) {return Integer.toBinaryString(n).replaceAll("0", "").length();} }

方法二：
這是對上面講到的錯誤方法的改進，由于左移操作是最高位舍棄，最低位補0，我們選擇讓 $n$ 不變， 對 ‘&1’ 中的1進行左移，直到移動31位為止。

由上圖的兩種情況可以看出，當1移動了 $i$ 位之后，若 $n$ 的第 $i$ 位為1，進行&運算的結果為 $(1<<i)$，否則為0。于是，我們就可以利用他們為判斷條件來計算1的個數啦~

public class Solution {public int NumberOf1(int n) {int cnt = 0;for(int i = 0; i < 32; i++) {//if ((n & (1 << i)) == (1 << i))也是可行的if ((n & (1 << i)) != 0)cnt++;}return cnt;} }

方法三：
這種方法是很久之前zls師兄告訴我的，沒想到今天才派上用場（我記憶力真好 ）。

理論：$n$ 和 $n?1$ 進行 $\&$ 運算可以把 $n$ 的二進制表示的右邊第一個1變成0

根據上面給的理論，我們只要知道 $n$ 可以進行多少次這樣的操作，就可以得到 $n$ 的二進制表示中1的個數，下圖以n=29為例展示這個過程：

如果對上訴過程感受不深，可以手動計算多幾組數據，雖然這種方法感覺起來比較笨，但卻是理解的好辦法。能用上這種方法，面試應該沒問題了。

public class Solution {public int NumberOf1(int n) {int cnt = 0;while (n != 0) {n = n & (n - 1);cnt++;}return cnt;} }

方法四：
這是在牛客網評論區看到做法，由Holiday_12138發表，但是ta并沒有給出具體思路，我也參悟不出來，我打算以后理解了再更新這部分，也歡迎各位大佬提供解釋。（做法真的太騷了 ）

public class Solution {public int NumberOf1(int n) {int temp = n;temp = (temp & 0x55555555) + ((temp & 0xaaaaaaaa) >>> 1);temp = (temp & 0x33333333) + ((temp & 0xcccccccc) >>> 2);temp = (temp & 0x0f0f0f0f) + ((temp & 0xf0f0f0f0) >>> 4);temp = (temp & 0x00ff00ff) + ((temp & 0xff00ff00) >>> 8);temp = (temp & 0x0000ffff) + ((temp & 0xffff0000) >>> 16);return temp;} }

---

如果本文對你有所幫助，要記得點贊哦~

總結

以上是生活随笔為你收集整理的剑指Offer #11 二进制中1的个数（想不到的骚操作）的全部內容，希望文章能夠幫你解決所遇到的問題。

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