編寫一個函數(shù)，輸入是一個無符號整數(shù)（以二進制串的形式），返回其二進制表達式中數(shù)字位數(shù)為 '1' 的個數(shù)（也被稱為 漢明重量）。

示例1

• 輸入：n = 11 (控制臺輸入 00000000000000000000000000001011)

• 輸出：3

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

示例2

• 輸入：n = 4294967293 (控制臺輸入 11111111111111111111111111111101，部分語言中 n = -3）

• 輸出：31

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

提示

• 請注意，在某些語言（如 Java）中，沒有無符號整數(shù)類型。在這種情況下，輸入和輸出都將被指定為有符號整數(shù)類型，并且不應影響您的實現(xiàn)，因為無論整數(shù)是有符號的還是無符號的，其內部的二進制表示形式都是相同的。

• 在 Java 中，編譯器使用 二進制補碼 記法來表示有符號整數(shù)。因此，在上面的 示例 2 中，輸入表示有符號整數(shù) -3。

• 輸入必須是長度為 32 的 二進制串 。

方法一：逐位判斷

根據(jù) 與運算 定義，設二進制數(shù)字 n ，則有：

• 若 n&1=0 ，則 n 二進制 最右一位 為 0 ；

• 若 n&1=1 ，則 n 二進制 最右一位 為 1 。

根據(jù)以上特點，考慮以下 循環(huán)判斷 ：

• 判斷 n 最右一位是否為 1 ，根據(jù)結果計數(shù)。

• 將 n 右移一位（本題要求把數(shù)字 n 看作無符號數(shù)，因此使用 無符號右移 操作）。

代碼如下：

復雜度分析

• 時間復雜度： O(log 以 2 為底 n的對數(shù)) ，此算法循環(huán)內部僅有 移位、與、加 等基本運算，占用 O(1) ；逐位判斷需循環(huán) log 以 2 為底 n的對數(shù) 次，其中 log 以 2 為底 n的對數(shù) 代表數(shù)字 n 最高位 1 的所在位數(shù)。

• 空間復雜度： O(1) ，變量 ret 使用常數(shù)大小的額外空間。

方法二：位運算優(yōu)化

• (n - 1) 解析： 二進制數(shù)字 n 最右邊的 1 變成 0 ，此 1 右邊的 0 都變成 1 。

• n&(n?1) 解析： 二進制數(shù)字 n 最右邊的 1 變成 0 ，其余不變。

代碼如下：

復雜度分析

• 時間復雜度： O(M)，n&(n?1) 操作僅有減法和與運算，占用 O(1) ；設 M 為二進制數(shù)字 n 中 1 的個數(shù)，則需循環(huán) M 次（每輪消去一個 1 ），占用 O(M) 。

• 空間復雜度： O(1)，變量 ret 使用常數(shù)大小額外空間。

END

本文內容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強！

好兄弟可以點贊并關注我的公眾號“javaAnswer”，全部都是干貨。