依序列印出 N 個位元的
Gray code

N 個位元的 Gray code 是什麼呢?

例如：N=3

000
001
011
010
110
111
101
100

舉一個簡單的應用來說吧， 在控制或是通訊的領域裡， 有時候我們會需要將數位化的資訊轉換為 類比的控制訊號， 而數位化的資訊又可以由程式來控制更改， 如果有一個連續性的訊號， 比方說由 3 變成 4， 如果我們用一般二進位的方式來表示， 那就是 011 變成 100， 你可以注意到三個位元同時有變動， 從硬體的角度來看， 這三個位元哪一個先完成變動是不一定的， 假設第一個位元先變成 1， 也就是變成 111 了， 雖然很快地第二和第三個位元就會變成 0， 但是 111 這個暫時的狀態是很突兀的， 有可能會造成控制系統的不穩定， 而在 Gray code 系統中， 任何時候都不會出現暫時的狀態。

怎樣寫一個 C 程式來找出一組 Gray code 來呢?

以下面的這組 N=4 的 Gray code 來說， 你可以發現一些規則：

0000
0001 <== 改變前一個數字的 LSB
0011 <== 改變前一個數字最右邊的 1 的左邊那個位元
0010 <== 改變前一個數字的 LSB
0110 <== 改變前一個數字最右邊的 1 的左邊那個位元
0111 <== 改變前一個數字的 LSB
0101 <== 改變前一個數字最右邊的 1 的左邊那個位元
0100 <== 改變前一個數字的 LSB
1100 <== 改變前一個數字最右邊的 1 的左邊那個位元
1101 <== 改變前一個數字的 LSB
1111 <== 改變前一個數字最右邊的 1 的左邊那個位元
1110 <== 改變前一個數字的 LSB
1010 <== 改變前一個數字最右邊的 1 的左邊那個位元
1011 <== 改變前一個數字的 LSB
1001 <== 改變前一個數字最右邊的 1 的左邊那個位元
1000 <== 改變前一個數字的 LSB

程式要求：

1. 請儘量用函式來簡化邏輯， 執行速度暫時不用太在意， 當然你可以討論一下不同的 N 值大概需要多少時間。

2. 你可以用一個整數來記錄目前所處理的 GrayCode， 也可以用陣列變數來記錄 GrayCode， 如果你用整數來存的話， 請注意能夠存放的數字的大小， 如果你用 32 位元的整數來存放的話， 最多當然只能做到 N = 32， 如果你要處理更大一點的數字的話， 就需要用陣列來存放了， 記得要想辦法測試喔!

3. 請以 ANSI C 語法及函式庫來製作

4. 這個程式的功能也可以用遞迴 (recursive) 的函式呼叫來製作， 程式邏輯會更簡化一些。

範例執行程式

回 程式設計課程 首頁

製作日期: 99/10/19 by 丁培毅 (Pei-yih Ting)
E-mail: pyting@cs.ntou.edu.tw