[brush through sword finger] sword finger offer II 003 Number of 1 in the first n digit binary

Integer article - The finger of the sword Offer II 003. front n A number in binary 1 The number of

Original link ： The finger of the sword Offer II 003. front n A number in binary 1 The number of

analysis

Simple solution ： By binary operation , Every time you move right 1 position , And bitwise pair 1 The sum of this number can be calculated 1 The number of

Advanced solution ： adopt i & (i-1) seek 1 The number of . Consider a binary number i = 1100, be i-1 = 1011, that i & (i-1) = 1000, At this point, we find a value which is 1 Bit , Add one counter , Cycle until i by 0, The number of cycles is the binary of that number 1 The number of .

For the naive solution , The time complexity is O(n*k),k Is the number of bits in binary ;

For advanced solution , The time complexity is O(n*m),m It is... In binary 1 Number of digits ;

Code

Simple solution

class Solution {
    
    public int[] countBits(int n) {
    
        int[] ans = new int[n + 1];
        
        for (int i = 0; i <= n; i++) {
    
            int cnt_One = 0;
            int temp = i;
            while (temp != 0) {
    
                if ((temp & 1) == 1) {
    
                    cnt_One++;
                }
                temp = temp >> 1;
            }
            ans[i] = cnt_One;
        }

        return ans;
    }
}

Advanced solution

class Solution {
    
    public int[] countBits(int n) {
    
        int[] ans = new int[n + 1];

        for (int i = 0; i <= n; i++) {
    
            int cnt_One = 0;
            int temp = i;
            while (temp != 0) {
    
                temp = temp & (temp - 1);
                cnt_One++;
            }
            ans[i] = cnt_One;
        }
        
        return ans;
    }
}

Writing is not easy , Ask for attention , No attention to , Just like it ！