最开始一下子想不出来好的方法用的是O(n*sizeof(integer))的方法，辗转相除，每次除以2以后的余数就是bitwise上的数字。

1     public int[] countBits(int num) { 2         int[] res = new int[num + 1]; 3         res[0] = 0; 4         for(int i = 1; i <= num; i++) { 5             int x = i; 6             int cnt = 0; 7             while(x != 0) { 8                 if(x % 2 == 1){ 9                     cnt++;10                 } 11                 x /= 2;12             }13             res[i] = cnt;14         }15         return res;16     }

然后我自己想了下O(n)的方法

总体的想法是一组一组，每组的size是小于该数最大的2^n的值。

即res[4]=res[0]+1, res[5] = res[1] + 1, res[6] = res[2] + 1

1     public int[] countBits(int num) { 2         int[] res = new int[num + 1]; 3         if(num == 0) { 4             res[0] = 0; 5             return res; 6         } 7         res[0] = 0; 8         res[1] = 1; 9         int cnt = 1;10         for(int i = 2; i <= num; i++) {11             int cur = (int)Math.pow(2, cnt);12             int next = cur * 2;13             while(i <= num && i < next) {14                 res[i] = res[i - cur] + 1;15                 i++;16             }17             i--;18             cnt++;19         }20         return res;21     }

然后别人的做法就跟好看啦，

1     public int[] countBits(int num) {2         int[] res = new int[num + 1];3         for(int i = 1; i <= num; i++) {4             res[i] = res[i >> 1] + (i & 1);5         }6         return res;7     }