一、思路

求n的第k位数字: n >> k & 1

返回n的最后一位1：lowbit(n) = n & -n

去掉n最高位的1：n & (n - 1)

二、代码模板

import java.util.*;

public class Main {
    public static void main(String[] args) {
        System.out.print(f(in.nextInt()) + " ");
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) 
            System.out.print(f(in.nextInt()) + " ");
        System.out.println();
    }
    方法一：去掉n最高位的1：i & (i - 1)
    public static int f(int i) {
        int s = 0;
        while(i != 0) {
            i = i & (i - 1);
            s++;
        }
        return s;
    }
    方法二：返回n的最后一位1:n & -n，然后再减去
    public static int f(int i) {
        int s = 0;
        while(i != 0) {
            i -= i & (-i);
            s++;
        }
        return s;
    }
    方法三：从最后一位开始计算1的个数，计算完一位就往右移，直到i为0，比前面两种方法移除了最后多余的0，效率低一点
    public static int f(int i) {
        int s = 0;
        while(i != 0) {
            s += i & 1;
            i >>= 1;
        }
        return s;
    }
}

三、复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)