描述
用的是 x & (x-1),表示x这个数的二进制数去掉最后一个1。
遍历过程中,顺便用hashmap记录一下当前计算结果。
java 代码
import java.util.HashMap;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] q = new int[n];
HashMap<Integer, Integer> d = new HashMap<>();
d.put(0, 0);
for (int i = 0; i < n; i++) {
q[i] = in.nextInt();
}
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
int cur = q[i];
int cnt = 0;
while(cur > 0 && !d.containsKey(cur)){
cur = cur & (cur - 1);
++cnt;
}
d.put(q[i], cnt + d.getOrDefault(cur, 0));
ans[i] = cnt + d.getOrDefault(cur, 0);
}
for (int i = 0; i < n; i++) {
System.out.print(ans[i] + " ");
}
}
}