在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

回答

相關問題