Algorithm --- bit count (kotlin)

subject

Bit count
Give you an integer n , about 0 <= i <= n Each of the i , Calculate its binary representation 1 The number of , Returns a length of n + 1 Array of ans As the answer .

 Example  1：

 Input ：n = 2
 Output ：[0,1,1]
 explain ：
0 --> 0
1 --> 1
2 --> 10
 Example  2：

 Input ：n = 5
 Output ：[0,1,1,2,1,2]
 explain ：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Tips ：

0 <= n <= 105

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

Solutions

2 Of n The next power There must be only one 1
Because it's all 10000

Whenever more than one 2 Of n The next power
We can put the excess part
Find the result from the previous array
For example, over 2, So the current result is actually 1 + int[2]

resolvent

    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
    }

summary

1. How to judge a number is 2 Of n The next power ？
x&(x-1) = 0 It means 2 Of n The next power