在C中n位的2^n个状态循环，n> 32

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

对于短小Ñ我做的是计算X = 2^n的使用整数运算（包括n和x是整数），则

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

这里“位”是在比特的给定表示，什么迄今为止，它是一个长度为n的整数数组，其值为0或1（但也可以是其他值）。

如果n> 32，这种方法即使长时间显然也不起作用。

我该如何处理n> 32？

具体而言，我是否真的需要评估2^n，或者是否有一个很不方便的写循环的方法，它并不是指2^n的实际值，而是迭代2^n次？

来源

2013-03-05 DanielFetchinson

#include int32_t my_32bit_int;它可以声明一个32位整数 – 2013-03-05 12:13:30

使用'uint64_t'。当您完成对所有值的迭代后，回来再发布第二个问题。 – 2013-03-05 12:13:39

_所有整数都有它们的位。要获得_any_整数的'n'，你可以使用'i＆（1 << n）'。您不需要“将整数转换为位”。 – 2013-03-05 12:14:33

对于n> 32使用unsigned long long。这将适用于n达到64.仍然值甚至接近50，你将不得不等待长时间，直到周期结束。

来源

2013-03-05 12:13:15

但sizeof（无符号long long）与sizeof（long）相同，所以如何提供帮助？ – DanielFetchinson 2013-03-05 12:20:00

unsigned long long在我见过的所有编译器上都是64位，而另一方面长可能是32或64，这取决于编译器和体系结构。另外请记住，你将不得不采取一点点不同。例如'unsigned long long a = 1; a＆（1ULL << 55）;'注意1. – 2013-03-05 12:21:58

后的ULL谢谢，这最后一部分还不清楚。我该如何得到一个无符号长整型变量y的位x？ – DanielFetchinson 2013-03-05 12:49:53

不清楚你为什么说如果n> 32，那么显然将不起作用。你关心的是位宽，还是你关心的运行时间？

如果您关注数字宽度，请调查大型数学库，如http://gmplib.org/。

如果你关心运行时间......如果宽度足够大，你的循环不能完成足够长的时间，那么得到一个不同的爱好;）认真......算出粗略运行通过你的循环迭代一次，然后乘以40亿，除以20年，你就可以估计祖先需要等待答案的世代数。

来源

2013-03-05 12:15:22 mah

如果n> 32，我的方法不起作用，因为我使用整数（或长）算术。如果n> 32，2^n的结果（整数或长算术）将是垃圾。 – DanielFetchinson 2013-03-05 12:19:07

@Daniel简单地使用无符号long long，如我的回答 – 2013-03-05 12:19:39

@Daniel所示，这就是为什么我建议使用大型数学库。使用一个，你不会使用任何标量类型 - 然后你不会被锁定到最大64位宽度。无论如何，你将没有足够的时间使用现代CPU来遍历32位。 – mah 2013-03-05 12:21:01

在C中n位的2^n个状态循环，n> 32

回答

相关问题