009. Counting Bits

[KyrieSu]

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example:

For num = 5 you should return [0,1,1,2,1,2].

Follow up:

• It is very easy to come up with a solution with run time *O(nsizeof(integer)). But can you do it in linear time O(n)** possibly in a single pass?
• Space complexity should be O(n).
• Can you do it like a boss? Do it without using any builtin function in c++ or in any other language.

[KyrieSu]

剛剛簡單想了一下，只要是2的次方一定都只有一個1

至於其他的就待補充了 哈哈

[LarryLuTW]

還好不難 某種程度上應該也算 D&C

2 的次方一定是一 不過你能在 O(1) 判斷某個數是不是二的次方嗎

[KyrieSu]

嘿嘿~~ 之前看過妳的特殊解法阿XD 利用位元運算，但我不知道是不O(1)

int x = 4 ;
if(~(x)+1 == x)
   return true;

[LarryLuTW]

哈哈對 太好了你還記得 這樣是 O(1) 沒錯

你要 D&C 的提示嗎

[KyrieSu]

恩恩 我覺得我該加強一下D&C了!

[LarryLuTW]

譬如說你要算 10 離 10 最近的 2 的次方數是 8 所以 10 就會是 2 的答案加一等於 2

因為 十是 1010 八是 1000 二是 0010

簡單來說就是拿走最大那個 1 然後看剩下的是哪個數字 用他加一就可以了

假如要算 300 有幾個 1 那就先扣 256 = 44 看 44 有幾個 1 加上一個就是了 反正在算 300 之前一定算過 44 這樣可以 O(1) 算完每一個數字有幾個 1

[KyrieSu]

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 這方法好屌~ 完全懂! 但這樣是不是還要再計算最"近"的2的次方數 ?!

我剛剛寫了1~16，我有發現一個規則欸~

1. 0
2. 1
3. 1
4. 2
5. 1
6. 2
7. 2
8. 1
9. 2
10. 2
11. 3
12. 2
13. 3
14. 3
15. 4
16. 1

如果index為偶數，那她的個數剛剛好跟(index/2)一樣 若不是，那她為(index/2)+1。 但我沒有辦法證明XD，只能大概猜想跟2有關

[LarryLuTW]

哦哦滿好證明的 除二就是 right shift ～

10 = 1010 除二是 5 = 101 10 是偶數最右邊是 0 所以除二之後會一樣

同理 是奇數的話右移會被除掉 所以 + 1

這方法也超棒的欸

[KyrieSu]

對耶!!!!!!! 今天又是收穫滿滿~~~

學了一學期的計組，原來是要用在這裡，根本不是要拿去用ALU阿XDDDDD

超神的~