本文屬于「征服LeetCode」系列文章之一，這一系列正式開始于2021/08/12。由于LeetCode上部分題目有鎖，本系列將至少持續(xù)到刷完所有無鎖題之日為止；由于LeetCode還在不斷地創(chuàng)建新題，本系列的終止日期可能是永遠(yuǎn)。在這一系列刷題文章中，我不僅會(huì)講解多種解題思路及其優(yōu)化，還會(huì)用多種編程語言實(shí)現(xiàn)題解，涉及到通用解法時(shí)更將歸納總結(jié)出相應(yīng)的算法模板。

為了方便在PC上運(yùn)行調(diào)試、分享代碼文件，我還建立了相關(guān)的倉(cāng)庫：https://github.com/memcpy0/LeetCode-Conquest。在這一倉(cāng)庫中，你不僅可以看到LeetCode原題鏈接、題解代碼、題解文章鏈接、同類題目歸納、通用解法總結(jié)等，還可以看到原題出現(xiàn)頻率和相關(guān)企業(yè)等重要信息。如果有其他優(yōu)選題解，還可以一同分享給他人。

由于本系列文章的內(nèi)容隨時(shí)可能發(fā)生更新變動(dòng)，歡迎關(guān)注和收藏征服LeetCode系列文章目錄一文以作備忘。

給你一個(gè)整數(shù)?n?，對(duì)于?0 <= i <= n?中的每個(gè)?i?，計(jì)算其二進(jìn)制表示中?1?的個(gè)數(shù)?，返回一個(gè)長(zhǎng)度為?n + 1?的數(shù)組?ans?作為答案。

示例 1：

輸入：n = 2
輸出：[0,1,1]
解釋：
0 --> 0
1 --> 1
2 --> 10

示例 2：

輸入：n = 5
輸出：[0,1,1,2,1,2]
解釋：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

提示：

• 0 <= n <= 10^5

進(jìn)階：

• 很容易就能實(shí)現(xiàn)時(shí)間復(fù)雜度為?O(n log n)?的解決方案，你可以在線性時(shí)間復(fù)雜度?O(n)?內(nèi)用一趟掃描解決此問題嗎？
• 你能不使用任何內(nèi)置函數(shù)解決此問題嗎？（如，C++ 中的?__builtin_popcount?）

---

這道題需要計(jì)算從 $0$ 到 $n$ 的每個(gè)整數(shù)的二進(jìn)制表示中的 $1$ 的數(shù)目。

部分編程語言有相應(yīng)的內(nèi)置函數(shù)用于計(jì)算給定的整數(shù)的二進(jìn)制表示中的 $1$ 的數(shù)目，例如 Java 的 Integer.bitCount ，C++ 的 __builtin_popcount 。下列各種方法均為不使用內(nèi)置函數(shù)的解法。

為了表述簡(jiǎn)潔，下文用「一比特?cái)?shù)」表示二進(jìn)制表示中的 $1$ 的數(shù)目。

---

解法1 $BrianKernighan$ 算法

最直觀的做法是對(duì)從 $0$ 到 $n$ 的每個(gè)整數(shù)直接計(jì)算「一比特?cái)?shù)」。每個(gè)int型的數(shù)都可以用 $32$ 位二進(jìn)制數(shù)表示，只要遍歷其二進(jìn)制表示的每一位即可得到 $1$ 的數(shù)目。

利用 Brian?Kernighan 算法，可以在一定程度上進(jìn)一步提升計(jì)算速度。該算法的原理是：對(duì)于任意整數(shù) $x$ ，令 $x=x\&(x?1)$ ，該運(yùn)算將 $x$ 的二進(jìn)制表示的最后一個(gè) $1$ 變成 $0$ 。因此，對(duì) $x$ 重復(fù)該操作，直到 $x$ 變成 $0$ ，則操作次數(shù)即為 $x$ 的「一比特?cái)?shù)」。

對(duì)于給定的 $n$，計(jì)算從 $0$ 到 $n$ 的每個(gè)整數(shù)的「一比特?cái)?shù)」的時(shí)間都不會(huì)超過 $O(\log n)$ ，因此總時(shí)間復(fù)雜度為 $O(n\log n)$ 。

class Solution {public int[] countBits(int n) {int[] bits = new int[n + 1];for (int i = 0; i <= n; i++) bits[i] = countOnes(i);return bits;}public int countOnes(int x) {int ones = 0;while (x > 0) {x &= (x - 1);ones++;}return ones;}
}

復(fù)雜度分析:

• 時(shí)間復(fù)雜度：$O(n\log n)$ 。需要對(duì)從 $0$ 到 $n$ 的每個(gè)整數(shù)使用計(jì)算「一比特?cái)?shù)」，對(duì)于每個(gè)整數(shù)計(jì)算「一比特?cái)?shù)」的時(shí)間都不會(huì)超過 $O(\log n)$ 。
• 空間復(fù)雜度：$O(1)$ 。除了返回的數(shù)組以外，空間復(fù)雜度為常數(shù)。

---

解法2 動(dòng)態(tài)規(guī)劃——最高有效位

方法一需要對(duì)每個(gè)整數(shù)使用 $O(\log n)$ 的時(shí)間計(jì)算「一比特?cái)?shù)」?？梢該Q一個(gè)思路，當(dāng)計(jì)算 $i$ 的「一比特?cái)?shù)」時(shí)，如果存在 $0\le j<i$ ，$j$ 的「一比特?cái)?shù)」已知，且 $i$ 和 $j$ 相比，$i$ 的二進(jìn)制表示只多了一個(gè) $1$ ，則可以快速得到 $i$ 的「一比特?cái)?shù)」。令 $\text{bits}[i]$ 表示 $i$ 的「一比特?cái)?shù)」，則上述關(guān)系可以表示成：$\text{bits}[i]=\text{bits}[j]+1$ 。

對(duì)于正整數(shù) $x$ ，如果可以知道最大的正整數(shù) $y$ ，使得 $y\le x$ 且 $y$ 是 $2$ 的整數(shù)次冪，則 $y$ 的二進(jìn)制表示中只有最高位是 $1$ ，其余都是 $0$，此時(shí)稱 $y$ 為 $x$ 的「最高有效位」。令 $z=x?y$ ，顯然 $0\le z<x$ ，則 $\text{bits}[x]=\text{bits}[z]+1$ 。

為了判斷一個(gè)正整數(shù)是不是 $2$ 的整數(shù)次冪，可以利用方法一中提到的按位與運(yùn)算的性質(zhì)。如果正整數(shù) $y$ 是 $2$ 的整數(shù)次冪，則 $y$ 的二進(jìn)制表示中只有最高位是 $1$，其余都是 $0$，因此 $y\&(y?1)=0$ 。由此可見，正整數(shù) $y$ 是 $2$ 的整數(shù)次冪，當(dāng)且僅當(dāng) $y\&(y?1)=0$ 。

顯然，$0$ 的「一比特?cái)?shù)」為 $0$ 。使用 $\text{highBit}$ 表示當(dāng)前的最高有效位，遍歷從 $1$ 到 $n$ 的每個(gè)正整數(shù) $i$，進(jìn)行如下操作。

• 如果 $i\&(i?1)=0$ ，則令 $\text{highBit}=i$ ，更新當(dāng)前的最高有效位。
• $i$ 比 $i?\text{highBit}$ 的「一比特?cái)?shù)」多 $1$ ，由于是從小到大遍歷每個(gè)整數(shù)，因此遍歷到 $i$ 時(shí)，$i?\text{highBit}$ 的「一比特?cái)?shù)」已知，令 $\text{bits}[i]=\text{bits}[i?\text{highBit}]+1$ 。
• 最終得到的數(shù)組 $\text{bits}$ 即為答案。

class Solution {public int[] countBits(int n) {int[] bits = new int[n + 1];int highBit = 0;for (int i = 1; i <= n; i++) {if ((i & (i - 1)) == 0) highBit = i;bits[i] = bits[i - highBit] + 1;}return bits;}
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：$O(n)$ 。對(duì)于每個(gè)整數(shù)，只需要 $O(1)$ 的時(shí)間計(jì)算「一比特?cái)?shù)」。
• 空間復(fù)雜度：$O(1)$ 。除了返回的數(shù)組以外，空間復(fù)雜度為常數(shù)。

---

解法3 動(dòng)態(tài)規(guī)劃——最低有效位

方法二需要實(shí)時(shí)維護(hù)最高有效位，當(dāng)遍歷到的數(shù)是 $2$ 的整數(shù)次冪時(shí)，需要更新最高有效位。如果再換一個(gè)思路，可以使用「最低有效位」計(jì)算「一比特?cái)?shù)」。

對(duì)于正整數(shù) $x$ ，將其二進(jìn)制表示右移一位，等價(jià)于將其二進(jìn)制表示的最低位去掉，得到的數(shù)是 $?\frac{x}{2}?$? 。如果 $\text{bits}[?\frac{x}{2}?]$ 的值已知，則可以得到 $\text{bits}[x]$ 的值：

• 如果 $x$ 是偶數(shù)，則 $\text{bits}[x]=\text{bits}[?\frac{x}{2}?]$
• 如果 $x$ 是奇數(shù)，則 $\text{bits}[x]=\text{bits}[?\frac{x}{2}?]+1$

上述兩種情況可以合并成：$\text{bits}[x]$ 的值等于 $\text{bits}[?\frac{x}{2}?]$ 的值加上 $x$ 除以 $2$ 的余數(shù)。

由于 $?\frac{x}{2}?$ 可以通過 $x>>1$ 得到，$x$ 除以 $2$ 的余數(shù)可以通過 $x\&1$ 得到，因此有：$$\text{bits}[x]=\text{bits}[x>>1]+(x\&1)$$
遍歷從 $1$ 到 $n$ 的每個(gè)正整數(shù) $i$ ，計(jì)算 $\text{bits}$ 的值。最終得到的數(shù)組 $\text{bits}$ 即為答案。

class Solution {public int[] countBits(int n) {int[] bits = new int[n + 1];for (int i = 1; i <= n; i++)bits[i] = bits[i >> 1] + (i & 1);return bits;}
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n)$ 。對(duì)于每個(gè)整數(shù)，只需要 $O(1)$ 的時(shí)間計(jì)算「一比特?cái)?shù)」。
• 空間復(fù)雜度：$O(1)$ 。除了返回的數(shù)組以外，空間復(fù)雜度為常數(shù)。

---

解法4 動(dòng)態(tài)規(guī)劃——最低設(shè)置位

定義正整數(shù) $x$ 的「最低設(shè)置位」為 $x$ 的二進(jìn)制表示中的最低的 $1$ 所在位。例如，$10$ 的二進(jìn)制表示是 $1010_{(2)}$ ，其最低設(shè)置位為 $2$ ，對(duì)應(yīng)的二進(jìn)制表示是 $10_{(2)}$ 。

令 $y=x\&(x?1)$ ，則 $y$ 為將 $x$ 的最低設(shè)置位從 $1$ 變成 $0$ 之后的數(shù)，顯然 $0\le y<x$ ，$\text{bits}[x]=\text{bits}[y]+1$ 。因此對(duì)任意正整數(shù) $x$ ，都有 $\text{bits}[x]=\text{bits}[x\&(x?1)]+1$ 。

遍歷從 $1$ 到 $n$ 的每個(gè)正整數(shù) $i$，計(jì)算 $\text{bits}$ 的值。最終得到的數(shù)組 $\text{bits}$ 即為答案。

class Solution {public int[] countBits(int n) {int[] bits = new int[n + 1];for (int i = 1; i <= n; i++)bits[i] = bits[i & (i - 1)] + 1;return bits;}
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n)$ 。對(duì)于每個(gè)整數(shù)，只需要 $O(1)$ 的時(shí)間計(jì)算「一比特?cái)?shù)」。
• 空間復(fù)雜度：$O(1)$ 。除了返回的數(shù)組以外，空間復(fù)雜度為常數(shù)。