每天进步一点点🤏

比特位计数

  • 835 字

比特位计数

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
给你一个整数 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

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
思路:
重点在于获取比特位的算法 $k & ($k - 1),二进制数-1 与 原来的数字,得到去掉末尾的1的结果
例如:1101 & 1100 = 1100 -> 1100 & 1011 = 1000 -> 1000 & 0111 = 0000,重复三次就是三个1

代码:
/**
 * @param Integer $n
 *
 * @return Integer[]
 */
function countBits($n)
{
    $res = [0];
    for ($i = 1; $i <= $n; $i++) {
        $num = 0;
        $k   = $i;
        while ($k) {
            // 每次去掉末尾一个1,直到$k=0为止
            $k = $k & ($k - 1);
            $num++;
        }

        $res[] = $num;
    }

    return $res;
}