333.Counting Bits，理解位运算

本题考查对位运算的理解，自己想出的思路，有点骄傲

class Solution {
    public int[] countBits(int num) {
        int[] ret = new int[num + 1];
        ret[0] = 0;
        for(int i = 1; i <= num; i++){
                ret[i] = ret[i & (i - 1)] + 1;
        }
        return ret;
    }
}

• 首先是找规律，通过画图，并尝试使用位运算，找到相关性
• 不是一道典型的DP，但借鉴其思想
• ret[i] = ret[i & (i - 1)] + 1，这是核心逻辑，理解如下：

  • 两个连续的数字，后一位是由前一位加1得到的，比如：6 = 5 + 1、8 = 7 + 1

  • 十进制的加1操作，从二进制的角度理解，有两点：

    1. 从低位到高位，遇到的第一个0会变成1 (后续表述中的第一个0，都是从低位算起的第一个0)

    2. 这个0右边的1，会变成0

       比如：1010 -> 1011, 1001 -> 1010, 01111 -> 10000

  • 当连续的两个数字，做与操作时，对于较小的那个：

    • 第一个0左边(高位)的二进制是相同的，右边(包括0本身)完全不同

      比如：5: 1001, 6:1010，前两位相同，后两位不同

    • 与操作流程：左边完全保留 -> 0变成1 -> 右边都变成0 (如果右边有二进制)

  • 回到本题，求1的个数：

    • 与操作后，得到左边的公共二进制，取到对应1的个数(DP思想，利用之前计算后的结果，减少计算)
    • 在这个基础上加1 (第一个0要变成1)，就是最终1的个数