比特位计数 动态规划

1. 题目描述

给定一个非负整数num。对于0 ≤ i ≤ num范围中的每个数字i，计算其二进制数中的1的数目并将它们作为数组返回。

示例 1:

输入: 2
输出: [0,1,1]

示例 2:

输入: 5
输出: [0,1,1,2,1,2]

2. 题解

2.1 汉明权重

相关阅读：汉明权重。

public int[] countBits(int num) {
	int[] ans = new int[num + 1];
	for (int i = 0; i <= num; ++i)
		ans[i] = popcount(i);
	return ans;
}
private int popcount(int x) {
	int count;
	for (count = 0; x != 0; ++count)
	  x &= x - 1; //zeroing out the least significant nonzero bit
	return count;
}

x &= x - 1将最低有效非零位清零，每次执行此操作，count加1，直到所有非零位都被清零为止。
返回的count的值就是x的二进制形式的1的数目。

2.2 动态规划

2.2.1 最高有效位

public int[] countBits(int num) {
	int[] ans = new int[num + 1];
	int i = 0, b = 1;
	// [0, b) is calculated
	while (b <= num) {
		// generate [b, 2b) or [b, num) from [0, b)
		while(i < b && i + b <= num){
			ans[i + b] = ans[i] + 1;
			++i;
		}
		i = 0;   // reset i
		b <<= 1; // b = 2b
	}
	return ans;
}

注意到2、4和8刚好是2的整数次方(即2的一次方、2的二次方和2的三次方等等)。
以4为例，P(4) = P(0+2^2)，P(5) = P(1+2^2)，P(6) = P(2+2^2)，P(7) = P(3+2^2)。接下来，由于4不小于2^2(b = 2^m > x)，所以b乘以2，于是P(8) = P(0+2^3)。

2.2.2 最低有效位

public int[] countBits(int num) {
  int[] ans = new int[num + 1];
  for (int i = 1; i <= num; ++i)
	ans[i] = ans[i >> 1] + (i & 1); // x / 2 is x >> 1 and x % 2 is x & 1
  return ans;
}

以3(其二进制形式为11)为例，将01转换为11的过程：先将01向左移动一位(实际上相当于乘以2)，然后再加1。
注意到移位操作不会改变1的数目，但是1的数目会随着加1操作而增加一个。
因此，2的整数次方的1的数目为1。
仍然以3(其二进制形式为11)为例，将11转换为01的过程：先减1，然后将10向右移动一位(实际上相当于除以2)。

2.2.3 最后设置位

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

由于x&(x-1)会将x的最低有效非零位清零，这样会少了一个1，所以有P(x)=P(x&(x-1))+1。

P(0) = 0
P(1) = P(1&(1-1))+1 = P(0) + 1 = 0 + 1 = 1
P(2) = P(2&(2-1))+1 = P(0) + 1 = 0 + 1 = 1
P(3) = P(3&(3-1))+1 = P(2) + 1 = 1 + 1 = 2
P(4) = P(4&(4-1))+1 = P(0) + 1 = 0 + 1 = 1
P(5) = P(5&(5-1))+1 = P(4) + 1 = 1 + 1 = 2
P(6) = P(6&(6-1))+1 = P(4) + 1 = 1 + 1 = 2
P(7) = P(7&(7-1))+1 = P(6) + 1 = 2 + 1 = 3
P(8) = P(8&(8-1))+1 = P(0) + 1 = 0 + 1 = 1

参考：

• 比特位计数 - 比特位计数 - 力扣（LeetCode）

比特位计数 动态规划

原文：https://www.cnblogs.com/gzhjj/p/14139109.html