CountingBits [source code]

public class CountingBits {
    public int[] countBits(int num) {
        int [] result = new int[num+1];
        int tmp = 0;
        for (int i = 0; i <= num; i++ ) {
            if (i == 0) result[i] = 0;
            else if (i == 1) result[i] = 1;
            else if ((i & (i-1)) == 0) {
                tmp = i;
                result[i] = 1;
            }
            else result[i] = result[i-tmp] + 1;
        }
        return result;
    }

    public static void main(String[] arg) {
        CountingBits tester = new CountingBits();
        Scanner reader = new Scanner(System.in);
        System.out.println("Type the input: ");
        int input = reader.nextInt();
        for (int i : tester.countBits(input)) System.out.println(i);
    }
}

这个(i & (i-1)) == 0 是在网上找到的办法.一个注意的地方就是必须要加括号. &本身的优先级好像比较低;
当然这个判断power of 2还有别的办法: (http://stackoverflow.com/questions/19383248/find-if-a-number-is-a-power-of-two-without-math-function-or-log-function)
最简单的一个就是直接一个 while loop,除到死,然后看最后的结果是0还是1(这个我自己没有想到,有点蠢);

自己怎么想到这个 pattern 的方法呢? 首先这里要求O(n),这个要求其实是比较苛刻的,一般这个要求,就一定要use old result,就好像在 DP 里面的 memoization 的 table 一样, but in a bottom-up fashion;

如果老想着11=8+2+1这样的分解,其实最后做的,还是老路子,还是要对每一个数字单独分析,这样是做不到O(n)的.

另外这题属于 pattern 题,这种题目的特征其实比较明显,类似之前的那个下棋的题目,也是一样.与这种题目区分的,叫做 processing 题.processing 题一般都会给你specific inputs, 但是 pattern 题一般,对于某一个 n,只有一个未必的input instance/case. 所以 pattern 题目还是比较好发现的.

至于发现了以后怎么去解,怎么去发现这个 pattern,这个可能一句两句也说不清.
其实这个跟2sum 这种的核心思想还是一样的,函数本身的核心就是一个 loop,然后要做到O(n). loop 其实就是make decision for each element,所以怎样控制这个 decision 在constant time? 这一题跟2sum 采用的是不同的方法,但是背后还是有一定的共性.

这个题目一开始被 hint3误导了,一直想着奇偶性,然后认为 i 是奇数,就result[i]=result[i-1]+1,如果是偶数就不变.这个方法看起来正确,其实是有问题的,在11-12的地方就出错了.

后来自己想了一下,写了这个算法,最后时间是4ms,应该算是很快的了.

use old results,当然是不限于仅使用i-1的.实际上,这里使用的 use old的技术,稍微更加复杂一些. 观察到的规律是,比如1011,是11,这个在不断++的过程中的bit 1 count的变化规律,其实跟011是一样的,所以我们对于11,要查询的结果应该是11-8=3,这个也是hint2的这个划分区间的意思; 每次出现一个power of 2,其实就是类似于一个重置点一样,把这个点
记下来,后面的i,直接按照这个 tmp 的距离往前翻.

另外虽然这一题研究 pattern 很多,但是一些基本的算法还是要知道,比如给你一个 integer,怎么知道bit 1 counts?
public class Foo {
public static void main(String[] argv) throws Exception {
int no = 12345;
int count;
for (count = 0; no > 0; ++count) {
no &= no - 1;
}
System.out.println(count);
}
}

这个是搜到的一个算法,很聪明,而且用的思路跟判断power of 2的思路貌似很类似; 判断power of 2那个好像多少还能够通过直接观察比如10000,然后来摸索通过什么样的bit manipulation可以得到想要的结果,但是这个count bit 1的算法就比较复杂一点了.

另外需要学习的是这种while loop(虽然他实际用的是 forloop) 的使用.我目前对于 whileloop 的使用依然是弱项. 这个是一个硬伤.
类似的,如果只是要你找到count bits:
int value = 11;
int count = 0;
while (value > 0) {
count++;
value = value >> 1;
}

这个也是一个很简单的 whileloop;但是要自己想到怎么写;

/*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.

Hint:

You should make use of what you have produced already.
Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
Or does the odd/even status of the number help you in calculating the number of 1s?