什麼叫牡丹
演算法
，大概是
C語言
的永恆主題。
不管拿C語言去寫什麼，難的永遠不是C語言本身，而是相關的演算法。
在用C語言寫國際象棋遊戲的時候，一個問題就是：怎麼去判斷對方的
雙聯兵
？
要求這個判斷的
時間複雜度
必須是
O(1)
的。
即：只能有
if else語句
，不能有for / while迴圈，當然也不能有
遞迴
。
如下圖：
黑白雙方的兩個“
堡壘象
”各自控制1條大斜線，同時它們也被對方的雙聯兵阻擋。
象最怕雙聯兵，而且雙聯兵離象越近，物件的活動範圍壓縮的越厲害。
上圖的雙聯兵在F線和G線，如果在D線和E線的話，這兩個象就完全沒法活動了。
怎麼判斷這種情況？
最簡單的是用for迴圈去遍歷斜線上的8個格子。
int diff = x - y； // x， y是象的座標，與主斜線平行的情況下x - y的差相同
for （int i = x + 1； i < 8； i++） {
int j = i - diff；
if （j > 7） break；
if （board［i］［j］ == 兵） {
i ++；
j = i - diff；
if （i < 8 && j < 8 && board［i］［j］ == 兵） //第二個兵
printf（“雙聯兵\n”）；
} // 第一個兵
}
但這個演算法是
O(N)
的，在圖中的情況下需要
遍歷5個格子
才可以發現象是頂著雙聯兵的。
程式碼的效率老是比
人眼
差，就是因為程式碼使用
靜態的資訊
，而人眼是使用
動態的資訊
。
上圖的那個局面，當然不是一下子就那樣的，而是一步步的走成那樣的。
每一步棋都是動態的資訊，所以人眼是可以瞬間發現頂著雙聯兵的。
在黑棋的
兵F6
之後，白棋的象就頂著雙聯兵了。
為了也讓程式碼可以處理動態的資訊，就需要
記錄每條斜線上的兵
的情況。
國際象棋裡共有30條斜線，其中15條與主斜線A1-H8平行，另外15條與反斜線A8-H1平行（4個角上的1格也被看作1條斜線）。
圖中藍線圈出來的部分，就是記錄斜線上的兵的情況的程式碼。
diagonals［2］［2］［16］，第1個2表示黑白雙方，第2個2表示主反斜線，最後的16表示15條斜線。
為了讓記憶體大小是2個冪，餘著1個就餘著吧。
每當走兵的時候，就改變這個陣列的情況。
斜線上的兵的情況，
只需用x座標
就可以。
因為x - y或x + y是固定的，斜線上的x和y並不是獨立的變數，而是
線性相關
的。。
兵在哪個位置，就把哪個位置的掩碼設定為1。
實際上只需要
uint8_t
就夠了，國際象棋每條斜線上最多隻有8個格。
黑棋的兵F6導致的斜線狀態變化就是：
diagonals[BLACK][0][5 - 5 + 7] |= (1 << 5);
F6
在C語言裡的座標是
(5,5)，C語言從0開始計數
，國象從1開始計數。
F6所在的主斜線的x - y是0。
因為x - y有可能出現負數，而
負數不能用作C陣列的索引
，所以這裡把
x - y + 7
作為陣列索引。
在只有8格的情況下陣列索引最大就是7，x - y + 7肯定是 >= 0
的
。
反斜線上x + y的和就可以作為陣列索引，直接表示反斜線的編號。
兵如果從F6繼續到達F5，那麼F6所在斜線的掩碼就要清除：
diagonals[BLACK][0][5 - 5 + 7] &= ~(1 << 5);
C語言設定二進位制位用
或運算|
，清除二進位制位用
與運算&
。
藍框裡的雙聯兵
象正頂著雙聯兵時，從象的角度看過去，斜線掩碼的二進位制必然是0000 1100。
如果總是把
象所在的位置
看作
低位
，把
兵所在的位置
看作
高位
，那麼高位有
連續2個1
的情況就是雙聯兵。
這個判斷是O（1）的，如果n0是斜線上的兵的掩碼：
n1 = n0 & （n0 - 1）； //這樣就可以清除
最靠近
低位的那個1
p0 = n0 - n1； // 這就是第1個兵的掩碼1
雙聯兵的情況下，第2個兵必然緊鄰著第1個，所以：
if （
p0 && (n0 & (p0 << 1))
） 必然為
真（TRUE）
。
雙聯兵的二進位制碼如果去掉
所有是0的低位
，那麼就是
十六進位制的0x3
。
如果是
黑棋看主斜線
的話，首先看到的是二進位制碼的最高位的1。
黑棋視角的主斜線，二進位制碼0000 0110
黑棋從高位往低位看，G7象的x座標比C3兵的大，要透過去掉高位的1來判斷雙聯兵。
去掉最低位的1可以用n & （n - 1），但去掉最高位的1就比較麻煩，不知道它具體在哪一位。
我就乾脆做了個數組與它對應了，1100 0000對應的就是0000 0011，即0xc0對應著0x3。
C語言裡沒有反轉二進位制位的運算子，
intel手冊裡
也沒查到
反轉二進位制
的彙編碼。
這樣拿到掩碼之後可以直接查表，n0 = reverse［mask］，然後再n0 & （n0 - 1），與白棋的情況一樣了。
反正這個掩碼的情況最多隻有256種，uint8_t reverse［256］，提前把這個陣列填好就可以。
C語言裡，n - 1必然會導致n的
最低位的1被清零
，並且所有
低於這個1的位
被置1。
例如6個二進位制碼是110，6 - 1 = 5的
二進位制減法
必然會
從最低的1借位。
十進位制的高位1
被借1之後還
剩下9
，但
二進位制的高位1
被借1之後就只能
剩下0
了，
同時它的
所有低位
都會變成1。
如果
最低位本來就是1
的話n - 1不需要借位，只會把最低位清零。
5的二進位制碼是101，第2位的1被清零了，第1位的0變成了1。
3 - 1的情況下是不需要借位的，3的二進位制碼是11，3 - 1 = 2，2的二進位制碼是10，最低位的1被清零。
C語言的書可以看看
C Primer Plus
，二進位制碼的運算大概也就C語言還在玩。
因為C語言可以拿來寫需要
高效運算
的軟體，例如國際象棋的AI。
我寫這個程式用clock_gettime（）檢視到
納秒
，gettimeofday（）的
微秒
太大了（汗）。
想了解更多精彩內容，快來關注閒聊程式碼