沃爾夫勒姆自動機（Rule 30）C語言實現：位域優化與時空圖生成

編輯：關於C語言

沃爾夫勒姆自動機（Rule 30）C語言實現：位域優化與時空圖生成

沃爾夫勒姆一維元胞自動機是計算理論與複雜系統研究的經典模型。Rule 30 因其混沌特性常被用作隨機數生成器基礎。本文展示一個高度優化的 C 語言實現，利用位域結構壓縮存儲，並通過位運算實現高速演化。

核心數據結構

#define ROW_LEN 38

typedef struct bits bits;
struct bits {
    unsigned int c0 : 1;
    unsigned int c1 : 1;
    unsigned int c2 : 1;
    unsigned int c3 : 1;
    unsigned int c4 : 1;
    unsigned int c5 : 1;
    unsigned int c6 : 1;
    unsigned int c7 : 1;
};

typedef bits row[(ROW_LEN + 7) / 8];  // 每行 5 個 bytes 存 38 個 cell

每個 bits 結構體僅佔 1 字節，存放 8 個元胞狀態，row 類型為定長數組，極大減少內存佔用並提升緩存命中率。

關鍵算法函數

get_cell(row rw, int x)：支持環狀邊界（-1 對應末尾，ROW_LEN 對應開頭），通過 switch(x % 8) 快速提取位域。
set_cell(row rw, int x, unsigned int v)：同樣處理邊界，寫入指定位域。
evo_cell(row rw, int x, unsigned char tab)：根據左、中、右三個鄰居構成 3-bit 索引，查表 tab（Rule 30 = 0b00011110）決定下一狀態。
evo_row(row rw1, row rw2, unsigned char tab)：並行演化整行。

主程序流程

#define TYPE_ID 30  // Rule 30

int main(int argc, char *argv[]) {
    row rw1, rw2;
    srand((unsigned int)time(NULL));
    rand_row(rw1);  // 隨機初始化

    while (1) {
        display_row(rw1);  // 輸出 ▉ 和空格
        _getch();          // 按鍵步進
        evo_row(rw1, rw2, TYPE_ID);
        display_row(rw2);
        _getch();
        evo_row(rw2, rw1, TYPE_ID);
    }
    return 0;
}