如何处理很长的位序列？
让我们有一些序列 A，例如 {-1, 3, 2, 5}。我们可以使用迭代（二进制递增某个迭代器）来选择其所有非空子序列 1 .. 2^|A|：
int i, A[] = {-1, 3, 2, 5};
for (i = 1; i < (1 << sizeof(A)); i++)
{
int t = i, p = 0;
while (t > 0)
{
if (t % 2 > 0)
printf("%d\t", a[p]);
t /= 2, p++;
}
printf("\n");
}
但是，如果 A 包含例如 5000000 个元素，我们该怎么办？例如如何处理50亿位的数字？
Let us have some sequence A, {-1, 3, 2, 5} for example. We can select all its non-empty subsequences using iterations (binary incrementing some iterator) 1 .. 2^|A|:
int i, A[] = {-1, 3, 2, 5};
for (i = 1; i < (1 << sizeof(A)); i++)
{
int t = i, p = 0;
while (t > 0)
{
if (t % 2 > 0)
printf("%d\t", a[p]);
t /= 2, p++;
}
printf("\n");
}
But what should we do if A contains, for example, 5000000 elements? E.g. how to handle 5-billion-bit number?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
有一组无规律的算法可以执行此类任务，称为“枚举算法”。他们主要处理以下问题：
1. 所有子集的第 i 个非空子集是什么？
2. 给定一个非空子集，下一个元素是什么？或以前的
3. 给定一个非空子集，该子集的秩是多少？
所有这些操作都是以线性时间执行的。如果你想获得所有子集，那么你将需要进行回溯。
一本涉及这些问题的有趣的书是：K. Rossen 的《Combinatorial Algorithms, Generation, Enumeration, Search》。
我还有一组关于这个主题的幻灯片，但我不知道如何附加它们。查看 Lucia Moura 网站，组合算法课程。
（如果您需要上述任何算法的详细信息，请告诉我）
Well there is an inerestign set of algorithms that perform such tasks called "Enumeration algorithms". They deal mainly which questions such as:
1. What is the ith non-empty subset of all subsets ?
2. Given a non empty subset, what is the next element ? or previous
3. Given a non empty subset, what is the rank of this subset ?
All these operations are performed with linear time. In case you want to obtain all subsets, then you will need to do backtracing.
An interesting book that deals with these issues is: Combinatorial Algorithms, Generation, Enumeration, Search By K. Rossen.
I have also a set of slides on this topic, I dont know how to attach them though. Check Lucia Moura website, course Combinatorial Algorithms.
(if you need details of any of these algorithms above, let me know please)
您可能希望开始使用 CUDA 或 SSE 对其进行优化，就像 bitmagic 所做的那样。
您还可以测试字节是否完全为零并完全跳过它们，并且使用 BSR、BSF 和 LCZ，您可以跳过为零的位并仅打印出跳过的位数的零。
You'd probably want to start optimizing it using CUDA or SSE, like bitmagic does.
you can also test if bytes are totally zero and skip them entirely, and using BSR, BSF and LCZ, you can skip over the bits that are zero and just print out zeros for the amounts of bits skipped.