338_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.

给定一个整数N，输出一个有N+1个元素的数组，第i个元素是0··i··N，该数字含1的位的个数

按照2ⁿ分开，因为n是该数字的总共位数

0  1

0  1

……

2  　　3

10     11     

……

4　　　　 5　　 　　6　　 　　7

100        101        110         111

……

可见：2ⁿ开始，每个奇数加一，偶数不变

public class Solution {
    public int[] CountBits(int num)
    {
        int[] returnSize = new int[num + 1];
        int count = 0;
        int k = 1;
        while (num >= k || (num < k && num >= k>>1) )
        {
            int temp = 0;
            if (count > 1)
            {
                temp = 1;
            }
            for (; count < k && count <= num; count++)
            {
                if ((count & 1) == 1)//奇数
                {
                    returnSize[count] = ++temp;
                }
                else
                {
                    returnSize[count] = temp;
                }
            }
            k = k << 1;
        }
        return returnSize;
    }
}

问题：在VS中可以得到的正确结果在leetcode中不能得到

338_Counting Bits

原文：http://www.cnblogs.com/Anthony-Wang/p/5315327.html