剑指offer_3_前n个数字二进制形式中1的个数(java)

输入一个非负数n，请计算0到n之间每个数字的二进制形式中1的个数，并输出一个数组。例如，输入的n为4，由于0、1、2、3、4的二进制形式中1的个数分别为0、1、1、2、1，因此输出数组[0，1，1，2，1]。

/**
     * 每次用“i&（i-1）”将整数i的最右边的1变成0。
     * 整数i减去1，那么它最右边的1变成0。如果它的右边还有0，则右边所有的0都变成1，而其左边所有位都保持不变。
     * 下面对i和i-1进行位与运算，相当于将其最右边的1变成0。
     * 以二进制的1100为例，它减去1的结果是1011。1100和1011的位与运算的结果正好是1000。
     * 二进制的1100最右边的1变为0，结果刚好就是1000。
     *
     * @param num
     * @return
     */
    public static int[] countBIt1(int num) {
        int[] res = new int[num + 1];
        for (int i = 1; i < num; i++) {
            int j = i;
            while (j != 0) {
                res[i]++;
                j = j & (j - 1);
            }
        }
 
        return res;
    }
 
    /**
     * “i&（i-1）”将i的二进制形式中最右边的1变成0，
     * 也就是说，整数i的二进制形式中1的个数比“i&（i-1）”的二进制形式中1的个数多1
     *
     * @param num
     * @return
     */
    public static int[] countBIt2(int num) {
        int[] res = new int[num + 1];
        for (int i = 1; i < num; i++) {
            res[i] = res[i & (i - 1)] + 1;
        }
 
        return res;
    }
 
    /**
     * 如果正整数i是一个偶数，那么i相当于将“i/2”左移一位的结果，
     * 因此偶数i和“i/2”的二进制形式中1的个数是相同的。
     * 如果i是奇数，那么i相当于将“i/2”左移一位之后再将最右边一位设为1的结果，
     * 因此奇数i的二进制形式中1的个数比“i/2”的1的个数多1。
     * 例如，整数3的二进制形式是11，有2个1。偶数6的二进制形式是110，有2个1。
     * 奇数7的二进制形式是111，有3个1。我们可以根据3的二进制形式中1的个数直接求出6和7的二进制形式中1的个数。
     *
     * @param num
     * @return
     */
    public static int[] countBIt3(int num) {
        int[] res = new int[num + 1];
        for (int i = 1; i < num; i++) {
            res[i] = res[i >> 1] + (i & 1);
        }
 
        return res;
    }

System.out.println(Arrays.toString(countBIt1(4))); //[0, 1, 1, 2, 0]
System.out.println(Arrays.toString(countBIt2(4))); //[0, 1, 1, 2, 0]
System.out.println(Arrays.toString(countBIt3(4))); //[0, 1, 1, 2, 0]