【力扣每日一题】力扣2859计算k位置下标对应元素的和（bitCount源码分析及实现）

题目来源

力扣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的位的数量。

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

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

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;
    }
};