Aim Wang: 7月 2016

2016/07/14

leetcode Counting Bits

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(n*sizeof(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 like __builtin_popcount in c++ or in any other language.

給一個正整數，輸出 0 ≤ i ≤ num 的二進制數值 1 的數量，明明很簡單的題目。但是後面的條件說要在 O(n) 解決掉，而不能用到 O(n * sizeof(integer))，所以直覺的寫個 function 用 shift 去計算個別數值 1 的數量並不能滿足條件。只好回歸二進制的特性找線索。

二進制每次+1的時候，就是最後一位 0 變 1 或 1 變 0，每個位數從 1 變成 0 的時候，就往前進一位。

所以 1,2,4,8,16,32,64...在進位之後，低位數就開始循環。列個清單來驗證一下這樣的推論

十進制	二進制	1 的數量
0	0000 0000	0
1	0000 0001	1
2	0000 0010	1
3	0000 0011	2
4	0000 0100	1
5	0000 0101	2
6	0000 0110	2
7	0000 0111	3
8	0000 1000	1
9	0000 1001	2
10	0000 1010	2
11	0000 1011	3
12	0000 1100	2
13	0000 1101	3
14	0000 1110	3
15	0000 1111	4

從表格已經可以看出 1 的數量在 1, 2, 4, 8 的時候，就是複製前面 1, 2, 4, 8 個結果，並將新複製的結果 + 1，也就是重複前面的循環但是要再加上本身進位所增加的那一個。

十進制	複製	輸出結果
0		0
1	0 0	0 1
2	01 01	01 12
4	0112 0112	0112 1223
8	01121223 01121223	01121223 12232334

確定這個方法可行，開始動手寫程式啦

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* countBits(int num, int* returnSize) {
    int s, ss, i;
    *returnSize = num+1;
    int * retvals = malloc(sizeof(int) * (num+1));
    memset(retvals, 0, sizeof(int));

    s=1;
    retvals[0] = 0;
    while(s <= num)
    {
 if(s*2 > num)
 {
     ss = num - s + 1;
 }
 else
 {
     ss = s;
 }
 memcpy(retvals + s, retvals, sizeof(int) * ss);
 for(i=0;i<ss;i++)
 {
     retvals[s+i]++;
 }
 s = s<<1;
   }
    return retvals;
}

void main(int argc, char *argv[])
{
 int * resarr;
 int rescnt, i;

 if(2 != argc)
 {
  printf("What?\n");
  return;
 }
 
 if(atoi(argv[1]))
 {
  resarr = countBits(atoi(argv[1]), &rescnt);
  printf("[%d", resarr[0]);
  for(i=1; i<rescnt; i++)
  {
   printf(",%d", resarr[i]);
  }
  printf("]\n");
 }
 else
 {
  printf("Oh! Oh!\n");
 }
}