我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 191. 位1的個數

題目

編寫一個函數，輸入是一個無符號整數，返回其二進位表達式中數字位數為 ‘1’ 的個數（也被稱為漢明重量）。

示例 1：

輸入：00000000000000000000000000001011
輸出：3
解釋：輸入的二進位串 00000000000000000000000000001011 中，共有三位為 '1'。

示例 2：

輸入：00000000000000000000000010000000
輸出：1
解釋：輸入的二進位串 00000000000000000000000010000000 中，共有一位為 '1'。

示例 3：

輸入：11111111111111111111111111111101
輸出：31
解釋：輸入的二進位串 11111111111111111111111111111101 中，共有 31 位為 '1'。

提示：

• 請註意，在某些語言（如 Java）中，沒有無符號整數類型。在這種情況下，輸入和輸出都將被指定為有符號整數類型，並且不應影響您的實現，因為無論整數是有符號的還是無符號的，其內部的二進位表示形式都是相同的。
• 在 Java 中，編譯器使用二進位補碼記法來表示有符號整數。因此，在上面的 示例 3 中，輸入表示有符號整數 -3。
   
  進階:
• 如果多次調用這個函數，你將如何優化你的演算法？

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/number-of-1-bits
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

解題思路

思路1-轉為string計算1的數量或者逐位右移與1與運算計算1的數量

略

演算法複雜度:

• 時間複雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
• 空間複雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $

思路2-不斷減1與運算

思路解析：對於只有一個bit位為1的值來說其與其本身減1的值與運算後必為0；
該思路一般化後對於任意的數，只要不斷將其與其本身減1後的值與運算直至為0即可得到bit位為1的數量；

演算法複雜度:

• 時間複雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
• 空間複雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $

演算法源碼示例

package leetcode;

/**
 * @author ZhouJie
 * @date 2020年5月2日 下午9:26:00 
 * @Description: 191. 位1的個數
 *
 */
public class LeetCode_0191 {

}

class Solution_0191 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年5月2日 下午9:26:32 
	 * @param: @param n
	 * @param: @return
	 * @return: int
	 * @Description: 1-一個正數與其減1後二進位與運算後，該數的最低位的1將被0替代；
	 *
	 */
	// you need to treat n as an unsigned value
	public int hammingWeight(int n) {
		int count = 0;
		while (n != 0) {
			n &= (n - 1);
			count++;
		}
		return count;
	}
}