计算包含 1 的子集的数量

Question

有长度为 N 的位集(大约 500-700)。我需要获取每个仅包含 1 的子集的计数

例子

N = 32

设置 = 0*11*0*111*00*1*0*1*00 *1111*0*11*00*111*000*1*0*1*

输出 = {[1] = 4,[2] = 2,[3] = 2,[4] = 1,[5] = 0,...[32] = 0

void get_count(int tab[], int len) {
int *out = calloc(1, sizeof(*out) * INT_BIT * len);
int i, j, k;
int cur;
int count = 0;

for(i = 0; i < len; i++) {
    cur = tab[i];
    for(j = 0; j < INT_BIT; j++) { 
        count += (cur & 1);
        if(!(cur & 1)) { 
            out[count]++; 
            count = 0; 
        }
        cur >>= 1;
    }
}

for(i = 0; i < INT_BIT * len; i++) {
    printf("%d ", out[i]);
}
printf("\n");
free(out);
}

这个简单的操作将被执行大约数十亿次。迭代每一位都太慢了。如何优化这个算法？

Answer 1

我会使用查找表来选择合适的维度(可能是 8 位或 16 位 key )。

在这个查找表中，我会将每个键与 4 个值相关联:

• 附加到左侧的 1 位数
• 附加到右侧的 1 位数
• 中间没有附加任何东西的子集数
• 中间子集的大小

例如，您可以将键 11011011 与 2,2,2 相关联，这样您就知道，至少有 1 位附加到右侧的左相邻字节将包含一个子集，该子集是它的子集size + 2(当前字节左边附加长度)等。

你需要找到一种方法来

• 在同一键中管理超过 1 个子集(例如 01011010)
• 管理全 1 的 key ，这样您就必须考虑左字节和右字节，并将 key 长度添加为子集长度的一部分。

但是每个第一位和最后一位为 0 的 key 都被简单地管理，因此您可以减少某些可能的 key 所需的处理量。

我想开发起来很棘手，但也可能很有趣，最后您只需要比较键，因为其他所有内容都硬编码在查找表中。当然，我不确定最终算法是否会优于简单方法，但我认为值得给它一个机会。