Li Kou brush question 338 Bit count

The idea is ： Write a function to calculate binary bits , And then from 0~n Traverse in turn , Get the returned linked list .

Brian Kernighan The principle of the algorithm is ： For any integer x, Make x=x & (x−1), The operation will x The last binary representation of 1 become 0. therefore , Yes x Repeat the operation , until x become 0.

class Solution {
    
    public int[] countBits(int n) {
    
        int[] arr = new int[n+1];
        for(int i=0; i<=n; i++){
    
            arr[i] = countOne(i);
        }
        return arr;
    }

    public int countOne(int x){
    
        int res = 0;
        while(x>0){
    
            x=x&(x-1);
            res++;
        }
        return res;
    }
}