位運算–求二進制中1的個數

給定一個長度為 n 的數列，請你求出數列中每個數的二進制表示中 1 的個數。

輸入格式

第一行包含整數 n。

第二行包含 n 個整數，表示整個數列。

輸出格式

共一行，包含 n 個整數，其中的第 i 個數表示數列中的第 i 個數的二進制表示中 1 的個數。

數據范圍

1≤n≤100000,
0≤數列中元素的值≤$10^9$

輸入樣例：

5
1 2 3 4 5

輸出樣例：

1 1 2 1 2

【分析】

介紹一個lowbit算法，能夠返回一個二進制序列從最后一位1的結果

代碼很簡單只有一行

public static int lowbit(int x){return x & (~x + 1);
}

如果x為10100，取反后結果是01011，再加一則變為了01100，再與10100做與運算后變為00100

返回的結果則是二進制為100

import java.util.*;
class Main{static final int N = 100010;static int[] arr = new int[N];public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();for(int i = 0;  i < n; i++){int a = sc.nextInt();int size = 0;while(a > 0){int changed = lowbit(a);a -= changed;size++;}System.out.print(size + " ");}sc.close();}public static int lowbit(int x){return x & (~x + 1);}
}