題目描述
這是 LeetCode 上的 劍指 Offer 15. 二進制中1的個數(shù) 怎炊，難度為 簡單。
Tag : 「位運算」、「分治」
請實現(xiàn)一個函數(shù)诈火，輸入一個整數(shù)（以二進制串形式）柿赊，輸出該數(shù)二進制表示中 1 的個數(shù)。例如，把 9 表示成二進制是 1001互躬，有 2 位是 1开仰。因此拟枚，如果輸入 9薪铜，則該函數(shù)輸出 2。
示例 1：
輸入：00000000000000000000000000001011
輸出：3
解釋：輸入的二進制串 00000000000000000000000000001011 中恩溅，共有三位為 '1'隔箍。
示例 2：
輸入：00000000000000000000000010000000
輸出：1
解釋：輸入的二進制串 00000000000000000000000010000000 中，共有一位為 '1'脚乡。
示例 3：
輸入：11111111111111111111111111111101
輸出：31
解釋：輸入的二進制串 11111111111111111111111111111101 中蜒滩，共有 31 位為 '1'。
提示：
- 輸入必須是長度為 32 的 二進制串 每窖。
「位數(shù)檢查」解法
一個樸素的做法是帮掉，對 int 的每一位進行檢查，并統(tǒng)計 的個數(shù)窒典。
代碼：
public class Solution {
public int hammingWeight(int n) {
int ans = 0;
for (int i = 0; i < 32; i++) {
ans += ((n >> i) & 1);
}
return ans;
}
}
- 時間復(fù)雜度：
蟆炊，
為
int的位數(shù)，固定為位
- 空間復(fù)雜度：
「右移統(tǒng)計」解法
對于方法一瀑志，即使 的高位均為是
涩搓，我們也會對此進行循環(huán)檢查。
因此另外一個做法是：通過 n & 1 來統(tǒng)計當(dāng)前 的最低位是否為
劈猪，同時每次直接對
進行右移并高位補 0昧甘。
當(dāng) 代表，我們已經(jīng)將所有的
統(tǒng)計完成战得。
這樣的做法充边，可以確保只會循環(huán)到最高位的 。
代碼：
public class Solution {
public int hammingWeight(int n) {
int ans = 0;
while (n != 0) {
ans += (n & 1);
n >>>= 1;
}
return ans;
}
}
- 時間復(fù)雜度：
int的位數(shù)浇冰，固定為的二進制表示全是
- 空間復(fù)雜度：
「lowbit」解法
對于方法二聋亡，如果最高位 和 最低位
之間全是
肘习，我們?nèi)匀粫T次右移，直到處理到最高位的
為止坡倔。
那么是否有辦法漂佩，只對位數(shù)為 的二進制位進行處理呢？
使用 lowbit 即可做到罪塔，lowbit 會在 復(fù)雜度內(nèi)返回二進制表示中最低位
所表示的數(shù)值投蝉。
例如 傳入
lowbit 返回 ；
傳入
lowbit 返回 ...
代碼：
public class Solution {
public int hammingWeight(int n) {
int ans = 0;
for (int i = n; i != 0; i -= lowbit(i)) ans++;
return ans;
}
int lowbit(int x) {
return x & -x;
}
}
- 時間復(fù)雜度：
int的位數(shù)墓拜，固定為 - 空間復(fù)雜度：
「分組統(tǒng)計」解法
以上三種解法都是 的请契，事實上我們可以通過分組統(tǒng)計的方式咳榜，做到比
更低的復(fù)雜度。
代碼：
public class Solution {
public int hammingWeight(int n) {
n = (n & 0x55555555) + ((n >>> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f);
n = (n & 0x00ff00ff) + ((n >>> 8) & 0x00ff00ff);
n = (n & 0x0000ffff) + ((n >>> 16) & 0x0000ffff);
return n;
}
}
- 時間復(fù)雜度：
爽锥，
int的位數(shù)涌韩，固定為 - 空間復(fù)雜度：
PS. 對于該解法，如果大家學(xué)有余力的話氯夷，還是建議大家在紙上模擬一下這個過程臣樱。如果不想深入，也可以當(dāng)成模板背過（寫法非常固定）腮考，但通常如果不是寫底層框架雇毫，你幾乎不會遇到需要一個 解法的情況。
而且這個做法的最大作用踩蔚，不是處理 int棚放，而是處理更大位數(shù)的情況，在長度只有 位的
int 的情況下馅闽，該做法不一定就比循環(huán)要快（該做法會產(chǎn)生多個的中間結(jié)果飘蚯，導(dǎo)致賦值發(fā)生多次，而且由于指令之間存在對 數(shù)值依賴福也，可能不會被優(yōu)化為并行指令）局骤，這個道理和對于排序元素少的情況下，我們會選擇「選擇排序」而不是「歸并排序」是一樣的暴凑。
最后
這是我們「刷穿 LeetCode」系列文章的第 劍指 Offer 15 篇峦甩，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目现喳，部分是有鎖題凯傲，我們將先將所有不帶鎖的題目刷完。
在這個系列文章里面拿穴，除了講解解題思路以外泣洞，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應(yīng)的代碼模板默色。
為了方便各位同學(xué)能夠電腦上進行調(diào)試和提交代碼球凰，我建立了相關(guān)的倉庫：https://github.com/SharingSource/LogicStack-LeetCode 。
在倉庫地址里腿宰，你可以看到系列文章的題解鏈接呕诉、系列文章的相應(yīng)代碼、LeetCode 原題鏈接和其他優(yōu)選題解吃度。
