力扣热门100题——比特位计数（（内置函数，Brian Kernighan算法，动态规划：最高有效位，最低有效位，最低设置位））

1.问题描述

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

2.示例

示例 1：

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10
示例 2：

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

3.提示

0 <= n <= 105

4.进阶

很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）

5.具体解法（内置函数，Brian Kernighan算法，动态规划：最高有效位，最低有效位，最低设置位）

package day8_比特位计数;

//方法一：内置函数：Java的Integer.bitCount


//方法二：Brian Kernighan算法
// 原理是：对于任意整数x，令x=x&(x−1)，该运算将x的二进制表示的最后一个1变成0。
// 因此，对x重复该操作，直到x变成0，则操作次数即为x的「1的比特数」。


//方法三：动态规划：最高有效位
//这个方法的思路：是当计算i的「一比特数」时，如果存在0≤j>1 得到，x除2的余数可以用 x&1 得到
//遍历从1到n的每个正整数i，计算bits的值。最终得到的数组bits 即为答案。


//方法五：动态规划：最低设置位
//定义正整数 x的「最低设置位」为x的二进制表示中的最低的1所在位。例如10的最低设置位是2（1010）
//令y=x&(x-1)，则 y 为将 x 的最低设置位从 1 变成 0 之后的数
//显然0≤y 
6.收获
 
复习到并掌握了数组的定义格式int [] 名字=new int[n]；可以在一开始创建的时候用变量去创建，后面会给一个具体的n，这样的创建方式要学习并吸收感触到这种将内容进行分开两个方法的形式，避免看起来很繁琐（方法一将查1个数的方法内容单独做了一个方法再调用）学习到了一个新的算法Brian Kernighan 算法，可以利用他统计1的比特位数学到一个新的位运算的应用：[x/2]可以通过 x>>1 得到，x除2的余数可以用 x&1 得到