找到在多个位字段中精确设置两次的位位置

Question

我有 9 个位字段，每个位字段有 9 个 9 位，即 int 的 9 个 LSB。 我想找到在所有位字段中精确设置两次的位位置。

例如：

    0.1111.1111
    0.0000.1101
    0.0001.1101
    0.0001.1101
    0.0010.1101
    0.0010.1101
    0.0100.1101
    0.0100.1101
    0.0000.0010

在此示例中，其位位置为 1，因为在该位置 1 恰好设置了两次。

第一次在第一个位域，第二次在最后一个位域。

目前我对整数进行“位置人口计数”。 对于每个可能的位字段，有 512 个，我有一个相应的长位掩码， 用于计算设置位位置的频率。

0.0100.1101 -> 0000.0000.0001.0000.0000.0001.0001.0000.0001

我总结了9位字段的9个长位掩码。 因此，总和的前 4 个 LSB 表示频率位 0 已设置。 第二个 4 位表示设置的频率位 1。 依此类推，这样我就可以扫描2的频率了。

这可行，但没有我希望的那么快。

有没有更快的算法可以用 Java 实现？

我不需要知道频率为 2 的所有位位置，只需要知道一个位位置即可。

Answer 1

与完整的 pos-popcount 相比，有一个捷径。

你可以发现两件事：

• 哪些位至少设置两次
• 哪些位至少被设置 3 次

然后您可以找到被设置两次的位，作为至少设置两次的位与未设置至少 3 次的位的交集。

int set_a1 = 0;
int set_a2 = 0;
int set_a3 = 0;
for (int i : values) {
    set_a3 |= set_a2 & i;
    set_a2 |= set_a1 & i;
    set_a1 |= i;
}
int set_twice = set_a2 & ~set_a3;