如何快速统计两个二进制数组交集位之间的1的数量？

问题定义 #

给定两个二进制数组（以32位整数数组为例），先计算两数组的交集位（即对应位均为1的位置，等价于i1 & i2的结果），再统计相邻交集位之间的区间、最左侧交集位左侧的区间、最右侧交集位右侧的区间内，两个原数组各自的1的数量。

示例说明 #

16位单整数示例 #

假设：

i1  = 0b0001001000100100;
i2  = 0b0101000100010110;
i12 = i1 & i2 = 0b0001000000000100; // 交集位在第3位和第13位（从0开始计数）

分割出的有效区间为0-2位、4-12位，对应统计结果：

x1 = [0, 2] // i1在两个区间内的1的数量
x2 = [1, 2] // i2在两个区间内的1的数量

32位整数数组示例 #

给定：

int i1[2] = {2719269390, 302235938};
int i2[2] = {2315436042, 570885266};

对应的二进制形式：

i1      = [10100010 00010100 11000010 00001110, 00010010 00000011 11000001 00100010]
i2      = [10001010 00000010 11000000 00001010, 00100010 00000111 00000100 10010010]
i1 & i2 = [10000010 00000000 11000000 00001010, 00000010 00000011 00000000 00000010]

预期统计结果：

x1 = [2, 2, 0, 1, 1, 1, 0, 0, 4];
x2 = [2, 1, 0, 0, 0, 1, 1, 0, 3];

现有暴力解法的不足 #

暴力解法通过循环定位交集位：

1. 用__builtin_clz()获取i1 & i2的前导零位数，定位最高交集位
2. 将i1、i2右移对应位数，用__builtin_popcount()统计当前区间的1的数量
3. 重复操作直至所有交集位处理完毕

但该方法需要频繁操作临时变量、执行多条指令，且包含逻辑分支，效率与代码简洁性均不理想。

优化实现思路与代码 #

我们可以通过位掩码批量生成区间，一次性计算所有区间的1的数量，避免循环分支。核心逻辑：

1. 将多整数数组合并为一个大整数，统一处理跨整数的位区间
2. 通过位运算直接生成每个分割区间的掩码
3. 对每个掩码，与原数组做按位与后统计1的数量

以下是针对双32位整数数组的C语言实现：

#include <stdint.h>
#include <stdio.h>

// 统计两数组在交集位分割区间内的1的数量
void count_bits_in_intervals(const uint32_t i1[], const uint32_t i2[], 
                            uint32_t *x1, uint32_t *x2, size_t *result_len) {
    // 合并为64位整体，统一处理跨整数的位
    uint64_t full_i1 = ((uint64_t)i1[0] << 32) | i1[1];
    uint64_t full_i2 = ((uint64_t)i2[0] << 32) | i2[1];
    uint64_t intersect = full_i1 & full_i2;

    *result_len = 0;
    if (intersect == 0) {
        // 无交集位，直接统计整个区间的1的数量
        x1[0] = __builtin_popcountll(full_i1);
        x2[0] = __builtin_popcountll(full_i2);
        *result_len = 1;
        return;
    }

    // 处理最左侧区间：最高位到第一个交集位左侧
    uint64_t highest_bit = 1ULL << (63 - __builtin_clzll(intersect));
    uint64_t left_mask = ((1ULL << 63) >> __builtin_clzll(intersect)) ^ (highest_bit - 1);
    if (left_mask != 0) {
        x1[*result_len] = __builtin_popcountll(full_i1 & left_mask);
        x2[*result_len] = __builtin_popcountll(full_i2 & left_mask);
        (*result_len)++;
    }

    // 处理中间区间：相邻交集位之间
    uint64_t mask = intersect;
    uint64_t prev_bit = highest_bit;
    while ((mask &= mask - 1) != 0) {
        uint64_t curr_bit = mask ^ (mask & (mask - 1));
        uint64_t interval_mask = (prev_bit - curr_bit) ^ curr_bit;
        x1[*result_len] = __builtin_popcountll(full_i1 & interval_mask);
        x2[*result_len] = __builtin_popcountll(full_i2 & interval_mask);
        (*result_len)++;
        prev_bit = curr_bit;
    }

    // 处理最右侧区间：最后一个交集位右侧到最低位
    uint64_t lowest_bit = intersect & -intersect;
    uint64_t right_mask = lowest_bit - 1;
    if (right_mask != 0) {
        x1[*result_len] = __builtin_popcountll(full_i1 & right_mask);
        x2[*result_len] = __builtin_popcountll(full_i2 & right_mask);
        (*result_len)++;
    }
}

int main() {
    uint32_t i1[2] = {2719269390, 302235938};
    uint32_t i2[2] = {2315436042, 570885266};
    uint32_t x1[10], x2[10];
    size_t len;

    count_bits_in_intervals(i1, i2, x1, x2, &len);

    printf("x1 = [");
    for (size_t i = 0; i < len; i++) {
        printf(i > 0 ? ", %u" : "%u", x1[i]);
    }
    printf("];\n");

    printf("x2 = [");
    for (size_t i = 0; i < len; i++) {
        printf(i > 0 ? ", %u" : "%u", x2[i]);
    }
    printf("];\n");

    return 0;
}

代码说明 #

1. 将两个32位整数合并为64位整体，避免处理跨整数的位区间时的拆分逻辑
2. 通过位运算直接生成各区间的掩码，无需循环移位或分支判断
3. 利用__builtin_popcountll()一次性统计区间内的1的数量，效率更高
4. 兼容无交集位的特殊场景，直接返回整个序列的统计结果

内容的提问来源于stack exchange，提问作者zdebruine