preface

One property of the bitwise and operation (&) is that, for any integer x, x=x & (x−1), the operation changes the last 1 in the binary representation of x to 0. Therefore, repeat this operation on x until x becomes 0, and the number of operations is “one bit” of X.

Topic describes

Given a non-negative integer num. For each number I in the range 0 ≤ I ≤ num, count the number of 1s in its binary number and return them as an array.

Example 1:

Input:2Output:0.1.1]
Copy the code

Example 2:

Input:5Output:0.1.1.2.1.2]
Copy the code

Advanced:

It is very easy to give a time complexity of O(n*sizeof(integer)). But can you do that in one scan in linear time O(n)? The space complexity of the algorithm is O(n). Can you refine the solution further? Requires that you do this without using any built-in functions (such as __builtin_popcount in C++) in C++ or any other language.Copy the code

Their thinking

1. Use a property of the bitwise and operation (&)

Just double loop each I to get its “one bit”.

AC code

 var countBits = function(num) {
     let bits = [];
     let x = 0;
    for(let i = 0; i <= num ; i++) {
        let singleNum = 0
        x = i;
        while(x > 0) {
            x = x & (x-1);
            singleNum++
        }
        bits[i] = singleNum;
    }
    return bits;
};
Copy the code

2. Find the lowest number where 1 becomes 0

Define the “lowest set bit” of a positive integer x to be the lowest 1 bit in the binary representation of x. For example, the binary representation of 10 is 1010(2), whose lowest setting bit is 2, and the corresponding binary representation is 10(2).

And I & (I – 1) is the number that turns 1 to 0 in the lowest position, and then I +1 gives me the number of bits I.

For example: 7(10)–111(2) Find the number in the lowest position where 1 becomes 0, i.e. 6(10)– 110(2)

Iterating over every positive integer I from 1 to num, calculating the value of bits. The resulting array bits are the answer.

AC code

var countBits2 = function(num) {
    const bits = new Array(num + 1).fill(0);
    for (let i = 1; i <= num; i++) {
        bits[i] = bits[i & (i - 1)] + 1;
    }
    return bits;
};
Copy the code

3. Look for patterns

• Odd: In binary representation, an odd number must have one more 1 than the preceding even number, because the extra 1 is the lowest 1.
• Even: In binary representation, the number of 1s in an even number must be the same as the number divided by 2

AC code

var countBits3 = function(num) {
    let bits = [];
    bits[0] = 0;
    for(let i = 1; i <= num; i++)
    {
        if((i & 1) != 0)
        {
            bits[i] = bits[i-1] + 1;
        }
        else
        {
            bits[i] = bits[i/2]; }}return bits;
}
Copy the code

conclusion

In fact, dynamic planning is not beat the head to come out, in most cases can be the first analysis of memory search, and then optimized for dynamic planning.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign