Leetcode 338. Counting Bits

Next challenges: Android Unlock Patterns Maximum XOR of Two Numbers in an Array Maximum Vacation Days

思路：动态规划。

两种分解方法：

count[i]表示的是i的二进制表示中1的个数。

1.count[i]=count[i/2]+count[i%2]=count[i>>2]+count[i&1]

2.count[i]=count[i&(i+1)]+1。这里i & (i - 1)的实际效果是消除i的二进制表示的最右边的1

1 class Solution {
2     public int[] countBits(int num) {
3         int[] count = new int[num + 1];
4         // for(int i = 1; i <= num; i++) count[i] = count[i >> 1] + (i & 1);//按位与的优先级低于加号
5         for(int i = 1; i <= num; i++) count[i] = count[i & (i - 1)] + 1;//i & (i - 1)的实际效果是消除i的二进制表示的最右边的1
6         return count;
7     }
8 }