c - 循环遍历 C 中 n 位的 2^n 个状态，其中 n > 32

Question

我想在 C 中对 n 位的所有可能的 2^n 状态进行循环。例如，如果 n=4，我想循环遍历 0000、0001、0010、0011、...、1110、1111。这些位可以用任何方式表示，例如长度为 n 且值为 0 的整数数组或1，或者长度为 n 的字符数组，其值为“0”或“1”等，这并不重要。

对于较小的 n，我所做的是使用整数算术计算 x=2^n（n 和 x 都是整数），然后

for(i=0;i<x;i++) {
    bits = convert_integer_to_bits( i );
    work_on_bits( bits );
}

这里 'bits' 在给定的位表示中，到目前为止有用的是一个长度为 n 的整数数组，其值为 0 或 1（但可以是其他任何值）。

如果 n>32 这种方法显然不适用于多头。

我将如何处理 n>32？

具体来说，我真的需要评估 2^n，还是有一种棘手的方法来编写不引用 2^n 的实际值但仍然迭代 2^n 次的循环？

score 1 · Accepted Answer

对于 n > 32 使用unsigned long long. 这适用于 n 高达 64。对于即使接近 50 的值，您也必须等待很长时间才能完成循环。

score 0 · Accepted Answer

不清楚你为什么说如果n>32，它显然是行不通的。您关心的是位的宽度，还是您关心的是运行时间？

如果您担心数字宽度，请研究大型数学库，例如http://gmplib.org/。

如果您担心运行时间...如果宽度足够大，您将无法完成循环，因此请换一种爱好；）说真的...算出一次迭代的粗略运行时间通过你的循环，将它乘以 40 亿，除以 20 年，你就会估计出需要等待答案的祖先的世代数。

2 回答 2