解决这个问题有几个步骤。首先,您需要枚举所有可能的位图。正如其他人指出的那样,您可以通过将整数从 0 增加到 2^n - 1 来轻松做到这一点。
一旦你有了它,你就可以遍历所有可能的位图,你只需要一种方法来获取该位图并将其“应用”到一个数组中,以生成由该图表示的所有索引处的元素之和。以下方法是如何执行此操作的示例:
private static int bitmapSum(int[] input, int bitmap) {
// a variable for holding the running total
int sum = 0;
// iterate over each element in our array
// adding only the values specified by the bitmap
for (int i = 0; i < input.length; i++) {
int mask = 1 << i;
if ((bitmap & mask) != 0) {
// If the index is part of the bitmap, add it to the total;
sum += input[i];
}
}
return sum;
}
此函数将采用一个整数数组和一个位图(表示为整数)并返回数组中其索引存在于掩码中的所有元素的总和。
此功能的关键是能够确定给定索引是否确实在位图中。这是通过首先为所需索引创建一个位掩码,然后将该掩码应用于位图以测试该值是否已设置来实现的。
基本上我们想要构建一个整数,其中只有一位被设置,其他所有位都为零。然后,我们可以将该掩码与位图按位与,并通过将结果与 0 进行比较来测试是否设置了特定位置。
假设我们有一个 8 位映射,如下所示:
map: 1 0 0 1 1 1 0 1
---------------
indexes: 7 6 5 4 3 2 1 0
要测试索引 4 的值,我们需要一个如下所示的位掩码:
mask: 0 0 0 1 0 0 0 0
---------------
indexes: 7 6 5 4 3 2 1 0
要构建掩码,我们只需从 1 开始并将其移动 N:
1: 0 0 0 0 0 0 0 1
shift by 1: 0 0 0 0 0 0 1 0
shift by 2: 0 0 0 0 0 1 0 0
shift by 3: 0 0 0 0 1 0 0 0
shift by 4: 0 0 0 1 0 0 0 0
一旦我们有了这个,我们就可以将掩码应用于地图并查看是否设置了值:
map: 1 0 0 1 1 1 0 1
mask: 0 0 0 1 0 0 0 0
---------------
result of AND: 0 0 0 1 0 0 0 0
由于结果是 != 0 我们可以知道索引 4 包含在地图中。