关于在9个9位位域中定位恰好被置位两次的位位置的技术问询

你好，针对你这个找「9个9位位域中恰好被置位两次的位位置」的需求，我来梳理下可行的方案，顺便聊聊你当前方法的优化空间：

先明确需求场景 #

你手头有9个int，每个只用了低9位作为位域，要找出所有在这9个位域里刚好被置1两次的位位置——比如你举的例子里，位1就符合这个条件（第一个和最后一个位域各置了一次）。

你当前的方法分析 #

你现在用的「位置人口计数」思路是通顺的：给每个可能的512种位域对应一个long掩码，把每个原始位的置位映射到掩码里的4位计数器（毕竟最多9次置位，4位足够存0-15），求和后扫描每个4位段找值为2的位置。这个方法确实能跑，但问题在于需要预存512个long（占4KB空间），而且预存掩码的过程要么占代码空间，要么占初始化时间，对于你的小规模场景来说有点“重”了。

更适合的优化方案 #

因为你的场景是固定的9个9位位域，规模极小，这里有两个更简洁高效的方案：

方案1：逐位直接计数（最推荐）

既然只有9个位、9个位域，逐位统计每个位的置位次数完全没性能压力，代码还特别直观，不容易出错。比如用C语言实现的话：

// 输入是9个int组成的数组，每个只用低9位；返回结果是低9位中恰好被置两次的位的掩码
int find_exactly_twice_bits(int bitfields[9]) {
    int result_mask = 0;
    // 遍历每个位位置（0到8）
    for (int bit_pos = 0; bit_pos < 9; bit_pos++) {
        int set_count = 0;
        int bit_mask = 1 << bit_pos;
        // 统计这个位在9个位域里被置位的次数
        for (int idx = 0; idx < 9; idx++) {
            if (bitfields[idx] & bit_mask) {
                set_count++;
            }
        }
        // 如果刚好是2次，把这个位加到结果里
        if (set_count == 2) {
            result_mask |= bit_mask;
        }
    }
    return result_mask;
}

这个代码逻辑一目了然，维护成本极低，对于你的场景来说，81次简单操作完全可以忽略性能开销，比预存掩码的方法省心多了。

方案2：位运算状态跟踪（批量处理）

如果想尝试更“巧妙”的位运算批量处理，可以用一个整数跟踪每个位的置位状态，区分「0次」「1次」「2次」「≥3次」四种情况：

• 用state整数，每个原始位对应两位状态位（比如位i对应状态位2i和2i+1），分别表示：
  • 00：该位被置0次
  • 01：该位被置1次
  • 10：该位被置2次
  • 11：该位被置≥3次

处理每个位域时，用批量位运算更新状态：

int find_exactly_twice_bits(int bitfields[9]) {
    int state = 0; // 每个位用两位存状态，9个位需要18位，足够用int存
    for (int idx = 0; idx < 9; idx++) {
        int bf = bitfields[idx] & 0x1FF; // 只取低9位
        // 把bf扩展成每个位占两位的形式（比如bf的位i对应扩展后的位2i）
        int bf_expanded = 0;
        for (int i = 0; i < 9; i++) {
            if (bf & (1 << i)) {
                bf_expanded |= (1 << (2*i));
            }
        }
        // 更新状态：01→10，10→11，00→01
        state = (state ^ bf_expanded) | ((state & bf_expanded) << 1);
        // 清除那些进入≥3次的位的重复标记（避免状态混乱）
        int thrice_mask = (state >> 1) & state;
        state &= ~thrice_mask;
    }
    // 提取状态为10的原始位
    int result_mask = 0;
    for (int i = 0; i < 9; i++) {
        if ((state >> (2*i + 1)) & 1) {
            result_mask |= (1 << i);
        }
    }
    return result_mask;
}

这个方法用位运算批量处理，适合如果以后位数量或位域数量扩大的情况，但对于当前的小场景，其实和逐位计数法效率差不多，胜在“代码技巧性”。

总结 #

如果追求简单可靠，方案1的逐位计数法绝对是你的首选；如果想玩位运算技巧，方案2可以试试。你当前的预存掩码方法虽然可行，但在这个小场景下有点冗余，没必要。

备注：内容来源于stack exchange，提问作者coder