计算包含1的子集的数量

概述有一个lengt N的位数(大概是500-700).我需要得到每个只包含1的子集的计数 例 N = 32 设置= 0 * 11 * 0 * 111 * 00 * 1 * 0 * 1 * 00 * 1111 * 0 * 11 * 00 * 111 * 000 * 1 * 0 * 1 * Out = { [1] = 4, [2] = 2, [3] = 2, [4] = 1, [5] = 0, … [3 有一个lengt N的位数(大概是500-700).我需要得到每个只包含1的子集的计数

例

N = 32

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

Out = {
[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);}

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

解决方法 我会使用查找表选择适当的维度(可能是8位或16位密钥).

在这个查找表中,我将每个键与4个值相关联：

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

例如,您可以将密钥11011011与2,2,2相关联,以便您知道右侧附加了至少1位的左相邻字节将包含其大小为2的子集(当前的左附加长度)字节)等等.

你需要找到一种方法

>在同一个密钥中管理多个子集(例如01011010)
>管理一个具有全1的密钥,这样您就必须考虑左字节和右字节,并将密钥长度作为子集长度的一部分.

但是,在第一个和最后一个位上具有0的每个键都可以轻松管理,因此您可以减少某些可能键所需的处理量.

我觉得开发很棘手,但它也可能很有趣,最后你只需要对键进行比较,因为其他所有内容都在查找表中进行了硬编码.当然,我不确定最终的算法是否会胜过简单的方法,但在我看来值得给它一个机会.

总结

以上是内存溢出为你收集整理的计算包含1的子集的数量全部内容，希望文章能够帮你解决计算包含1的子集的数量所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。