题目描述

.前 n 个数二进制中 1 的个数
给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

示例 1:
  1. 输入: n = 2
  2. 输出: [0,1,1]
  3. 解释: 
  4. 0 --> 0
  5. 1 --> 1
  6. 2 --> 10

示例 2:
  1. 输入: n = 5
  2. 输出: [0,1,1,2,1,2]
  3. 解释:
  4. 0 --> 0
  5. 1 --> 1
  6. 2 --> 10
  7. 3 --> 11
  8. 4 --> 100
  9. 5 --> 101

说明 :

0 <= n <= 105

进阶:

给出时间复杂度为 O(n*sizeof(integer)) 的解答非常容易。但你可以在线性时间 O(n) 内用一趟扫描做到吗？
要求算法的空间复杂度为 O(n) 。
你能进一步完善解法吗？要求不使用任何内置函数来执行此操作。

解题思路

位运算

比如1100，实值为12
右移一位之后为0110，实值为6
2 * 右移结果 = 原数
此时右移损失的是0，也就是此时最低为为0
对右移结果再次进行右移，直到右移结果为0为止。
由此可以得到二进制表示中1个数。

动态规划

对于偶数 其二进制表示的最低位必为0，则其二进制表示中1的个数与其1/2相同
也就是i为偶数 res[i] = res[i/2]
对于奇数，他的最低位一定为1，刚好就比他前一个数(偶数)多了一个低位1
res[i] = res[i-1] + 1

实现代码

  2. // 位运算
  3. int k = i;
  4. while(k!=0){
  5.   int temp = k>>1;
  6.   if(k!=temp<<1){
  7.     res[i]++;
  8.   }
  9.   k = temp;
  10. }
  11. // 动态规划
  13. public int[] countBits(int n) {
  14.   int[] res = new int[n+1];
  15.   for (int i = 1; i <= n; i++) {
  16.     res[i] = i%2 == 0 ? res [i/2] : res[i-1] + 1;
  17.   }
  18.   return res;
  19. }

时间及空间复杂度分析

两种思路时间复杂度均为一次遍历O(n)，空间复杂度返回长度n的数组，空间复杂度O(n)

拓展思路

leetcode题解
值得一提的是，官方题解中提出了几种按位与(&)运算的用法，值得了解。

  • 对任意数x 使 x=x & (x−1)，该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」。
  • 若 y & (y−1)=0 则表示 y为2的幂

评论区题解
提到直接取最低位的方法，lowbit运算 y = x& -x，结果y就为最低位的值