Java解决比特维位计数

Java解决比特维位计数

01 题目

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

示例 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

提示：

• 0 <= n <= 105

02 知识点

• 动态规划（DP）

• 二进制原理

03 我的题解

public class dongtai01 {
	public static void main(String[] args) {
		//测试和检查数据
		int[] nums=countBits(2);
		for (int i = 0; i < nums.length; i++) {
			System.out.println(nums[i]);
		}
		
	}
	public static int[] countBits(int n) {
		//根据题设得到返回数组
		int[] nums=new int[n+1];
		//循环判断每一个数的二进制有几个1
		for (int i = 0; i < nums.length; i++) {
			nums[i]=countBit(i);
		}
		
		
		return nums;
	}
	public static int countBit(int n) {
		//计数器
		int count=0;
		//当n=0时终止
		while (n!=0) {
			//根据二进制转化原理，二进制是十进制不断除以2的余数
				if (n%2==1) {
					//当余数为1时，计数器加一
					count++;
				}
				//下一次循环前除2
				n=n/2;
		}
		
		return count;
	}
}