数一数二进制1个数

最近隔了几天没更新博客，因为最近刷的题觉得没什么价值写。

不过好在今天遇到一道题，动态规划与二进制特征结合在一起特别妙。

原题

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

原题链接

思路

最简单的想法就是一个个数字数过去。

因为要多次调用数二进制1个数这个功能，所以封装一个函数用来操作。

1
2
3
4
5
6
7
8
9
10

int countEveryBits(int n)
{
  int cnt = 0;
  while (n)
  {
    cnt += n % 2;
    n /= 2;
  }
  return cnt;
}

进阶一点，我们这个函数对一个数的每个二进制位都判断一下。

有没有什么办法可以不管0，只提取其中的1呢？

Brian Kernighan 算法

Brian Kernighan 算法的原理是：对于任意整数x，令 x = x & (x−1)，该运算将 x 的二进制表示的最后一个1变成0。

1
2
3
4
5
6
7
8
9
10

int countEveryBits(int n)
{
  int cnt = 0;
  while (n)
  {
    n &= (n - 1);
    ++cnt;
  }
  return cnt;
}

具体原理可以读者自己手算操作一下。

这样能显著将时间复杂度降下来。

but 这样还是不够。

每个数都走一遍这个函数有点太麻烦了。

我们可以根据二进制的规则来根据前面数中1的个数来快速判断当前数1的个数吗？

二进制特征

• 奇数的最后一位绝对是1。
• 偶数的最后一位绝对是0。
• 奇数中1的个数等于前一个数中1的个数+1。（因为前一个是偶数）
• 偶数除以2，相当于将二进制位向右移一位。

如此，我们就可以写出动态规划的规则了。

1. 初始状态数字0中1的个数是0。
2. 如果是奇数，那么它二进制中1的个数就是前一个数+1
3. 如果是偶数，那么它二进制中1的个数等于它除以2对应的数中1的个数。（例如6与3中1的个数相同，8与4中1的个数相同）

代码

1
2
3
4
5
6
7
8
9
10

vector<int> countBits(int n) {
	vector<int> res(n + 1);
	res[0] = 0;
	for (int i = 1; i <= n; ++i)
	{
		if (i & 1) res[i] = res[i - 1] + 1;   //i & 1（如果i是奇数就是true，反之为false）
		else res[i] = res[i / 2];
	}
	return res;
}