338. Counting Bits（计算整数二进制表示中1的位数）

偏执的太偏执、 2022-07-15 07:00 147阅读 0赞

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example:  
For `num = 5` you should return `[0,1,1,2,1,2]`.

Follow up:

*  It is very easy to come up with a solution with run time O(n\*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
 *  Space complexity should be O(n).
 *  Can you do it like a boss? Do it without using any builtin function like \_\_builtin\_popcount in c++ or in any other language.

Hint:

1.  You should make use of what you have produced already.
2.  Divide the numbers in ranges like \[2-3\], \[4-7\], \[8-15\] and so on. And try to generate new range from previous.
3.  Or does the odd/even status of the number help you in calculating the number of 1s?

题目大意：给出参数num，计算0到num一共num+1个整数的二进制表示中各有多少个‘1’，将结果以数组形式返回。要求不使用时间复杂度为**O(n\*sizeof(integer))**的蛮力算法，空间复杂度为 O(n)，且不使用相关的系统内建功能函数。

解题思路： 设结果数组为res\[\]。

**解法一：**观察下表，从i=1开始的每个区间\[2^0, 2^1-1\],\[2^1, 2^2-1\],\[2^2, 2^3-1\]...每个区间上的 res\[i\]都等于res\[i-该区间长度\]+1。

i  二进制表示 '1'  res[i] 0    0000    0    res[0]=0
    -------------
    1    0001    1    res[1]=res[0]+1
    -------------
    2    0010    1    res[2]=res[0]+1
    3    0011    2    res[3]=res[1]+1
    -------------
    4    0100    1    res[4]=res[0]+1
    5    0101    2    res[5]=res[1]+1
    6    0110    2    res[6]=res[2]+1
    7    0111    3    res[7]=res[3]+1
    -------------
    8    1000    1    ...
    9    1001    2
    10   1010    2
    11   1011    3
    12   1100    2
    13   1101    3
    14   1110    3
    15   1111    4

那么我们可以根据这个规律得到一种解法，代码如下：（3ms，beats 41.16%）

public int[] countBits(int num) {
    		int[] res = new int[num + 1];
    		int i = 1, j, k = 2;
    		res[0] = 0;
    		while (i <= num) {
    			for (j = 0; i <= num && i < k; )
    				res[i++] = res[j++] + 1;
    			k <<= 1;
    		}
    		return res;
    	}

**解法二：**观察下表，发现从i=1开始，**当 i 为偶数时，res\[i\] = res\[i/2\]；当 i 为奇数时，res\[i\] = res\[i/2\] + 1。**这是因为i /= 2 等价于 i>>=1。当 i 为偶数时，i 的二进制表示中最低位为‘0’， i>>=1并不改变其二进制表示中‘1’的位数；当 i 为奇数时，对应的二进制最低位为‘1’， i>>=1会使 i 的二进制表示中‘1’的位数减少一位。

i  二进制表示 '1'  res[i] 0    0000    0    res[0]=0
    -------------
    1    0001    1    res[1]=res[0]+1
    -------------
    2    0010    1    res[2]=res[1]
    3    0011    2    res[3]=res[1]+1
    -------------
    4    0100    1    res[4]=res[2]
    5    0101    2    res[5]=res[2]+1
    6    0110    2    res[6]=res[3]
    7    0111    3    res[7]=res[3]+1
    -------------
    8    1000    1    ...
    9    1001    2
    10   1010    2
    11   1011    3
    12   1100    2
    13   1101    3
    14   1110    3
    15   1111    4

解法二代码如下：（3ms，beats 41.16%）

public int[] countBits(int num) {
    		int[] res = new int[num + 1];
    		int i = 1, j, k = 2;
    		res[0] = 0;
    		while (i <= num) {
    			if (i % 2 == 1)
    				res[i] = res[i / 2] + 1;
    			else
    				res[i] = res[i / 2];
    			i++;
    		}
    		return res;
        }

**解法三：**这是一种更简单的方法，规律是从i=1开始，res\[i\] = res\[i & (i-1)\] + 1。

i  二进制表示 '1'  i&(i-1)    res[i] 0    0000    0    \          res[0]=0
    -------------
    1    0001    1    0          res[1]=res[0]+1
    -------------
    2    0010    1    0          res[2]=res[0]+1
    3    0011    2    2          res[3]=res[2]+1
    -------------
    4    0100    1    0          res[4]=res[0]+1
    5    0101    2    4          res[5]=res[4]+1
    6    0110    2    4          res[6]=res[4]+1
    7    0111    3    6          res[7]=res[6]+1
    -------------
    8    1000    1    ...        ...
    9    1001    2
    10   1010    2
    11   1011    3
    12   1100    2
    13   1101    3
    14   1110    3
    15   1111    4

解法三代码如下：(2ms，beats 87.75%)

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