题目来源

力扣2859计算k位置下标对应元素的和

题目概述

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

请你用整数形式返回 nums 中的特定元素之 和 ，这些特定元素满足：其对应下标的二进制表示中恰存在 k 个置位。

整数的二进制表示中的 1 就是这个整数的 置位 。

例如，21 的二进制表示为 10101 ，其中有 3 个置位。

思路分析

大部分语言都内置了bitCount函数，最简单的方法就是调用库函数了。

bitCount函数分析

这里以java源码为例分析bitCount函数，Java的Integer和Long类中都提供了bitCount。 其实是非常好理解的

public static int bitCount(int i) {// HD, Figure 5-2// 这里是代码的关键，计算出每两位中1的个数i = i - ((i >>> 1) & 0x55555555);// 以下开始执行每两位相加、每四位相加，最终得到结果i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);i = (i + (i >>> 4)) & 0x0f0f0f0f;i = i + (i >>> 8);i = i + (i >>> 16);return i & 0x3f;
}

为了使解析工整 我做成了图片： 

自己使用C++实现一个bit_count

java源码中难想到的点在于0bAB - 0b0A的结果会是0xAB中权值为1的位的数量。

其实我们还有一种更容易想到的思路:

1. 我们可以把0bAB拆分为0b0A和0b0B 这样两个数只可能是0或者1；
2. 拆分开的1和0本身就代表了这两个数中1的数量，直接相加就可以得到结果；
3. 最后可以通过每两位相加得到结果。

GCC编译器内置了__builtin_popcount函数可以实现数位计数，我这里只有Visual Studio 2019，MSVC好像没有提供这个函数，所以我决定自己来实现一下这个函数。

class Solution {
public:int sumIndicesWithKSetBits(vector<int>& nums, int k) {int result = 0;for (int i = 0; i < nums.size(); i++) {if (bit_count(i) == k) {result += nums[i];}}return result;}int bit_count(int data) {// 0b0A + 0b0B 可以得到两位的个数data = (data & 0x55555555) + ((data >> 1) & 0x55555555);int result = 0;while (data > 0) {result += data & 0x03;data >>= 2;}return result;}
};

c++结果

也能实现，就是内存使用有点惨不忍睹。。。。。