算法---比特位计数(Kotlin)

题目

比特位计数
给你一个整数 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

提示：

0 <= n <= 105

https://leetcode.cn/problems/counting-bits/

解决思路

2的n次幂 一定是只有一个1
因为都是10000

每当超过一个2的n次幂
我们就可以把超过的部分
从之前的数组里面找出结果
比如超过2，那么当前的结果其实就是1 + int[2]

解决方法

    fun countBits(n: Int): IntArray {
    
        val intArray = IntArray(n + 1)

        var highBit = 0
        for (i in 1..n) {
    
            if ((i and (i - 1)) == 0) {
    
                intArray[i] = 1
                highBit = i
            } else {
    
                intArray[i] = intArray[i - highBit] + 1
            }
        }
        return intArray
    }

总结

1.怎么判断一个数是2的n次幂？
x&(x-1) = 0 就说明是2的n次幂