2859. 计算 K 置位下标对应元素的和 (opens new window)

题目难度不大，借此讨论任意数二进制表示的置1位

1.Integer.bitCount

直接使用Integer.bitCount(num)返回num的二进制表示的中置1位的数量。

2.动规

观察每个数的二进制表示，可以发现每个数都是由高n-1二进制表示左移一位后，再加上最低位计算得到。而在从小到大遍历的过程，高n-1二进制表示位的数必定是已经计算过的。

class Solution {
    public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
        int[] dp=new int[nums.size()];
        int res=0;
        for(int i=0;i<dp.length;i++){
            int low=i%2;
            dp[i]=dp[i>>1]+low;
            if(dp[i]==k) res+=nums.get(i);
        }
        return res;
    }
}