E.位运算-基础——338. 比特位计数

题目链接：338. 比特位计数（简单）

算法原理：

以下两种方法跟E.位运算-基础——191. 位1的个数几乎一模一样，仅仅是把单个数变成多个数的数组了

解法一：库方法

1ms击败99.80%

时间复杂度O(N)

解法二：n&(n-1)

1ms击败99.80%

时间复杂度O(Nlog N)

Java代码：

class Solution { //解法一：库方法 public int[] countBits(int n) { int[] ret=new int[n+1]; for(int i=0;i<=n;i++) ret[i]=Integer.bitCount(i); return ret; } }

class Solution { //解法二：n&(n-1) public int[] countBits(int n) { int[] ret=new int[n+1]; for(int i=0;i<=n;i++){ int t=i; while(t!=0){ ret[i]++; t&=t-1; } } return ret; } }