The Josephus Problem 似乎是一個相當有名的問題，我則是在 Concrete Math 這本書上第一次看到，本來針對這麼一個被廣泛討論的問題寫文章好像有點沒意思，但是我邊看感覺問題挺有趣的
以下我應該不會著重在怎麼實做，因為說白了它可以很好的簡化成 Rotate-shift，我應該會著重在 Concrete Math 上的觀點跟我的思考
約瑟夫問題
由於是一個廣泛被討論的問題，我直接引用 OpenhomeCC 對問題的描述：
據說著名猶太歷史/數學家約瑟夫（Josephus）有過以下的故事：在羅馬人佔領喬塔帕特後，40個猶太士兵與約瑟夫躲到一個洞中，眼見脫逃無望，一群人決定集體自殺，然而私下約瑟夫與某個傢伙並不贊成，於是約瑟夫建議自殺方式，41個人排成圓圈，由第1個人 開始報數，每報數到3的人就必須自殺，然後由下一個重新報數，直到所有人都自殺身亡為止。約瑟夫與不想自殺的那個人分別排在第16個與第31個位置，於是逃過了這場死亡遊戲
簡單講解法
一樣因為這個問題已經被廣泛討論了，相關解法應該是相當五花八門，所以我就簡單帶過，畢竟下面的討論完全基於你要先知道這個問題該怎麼解，如果你已經知道這個問題並且知道該怎麼解，請直接跳過
然後以下的討論是上述問題的小變種，我們假設是數到 2 就要自殺
基本上這個問題要想出解法很大程度要靠觀察，就是那種靈感突發蘋果突然砸到你的那種，你基本上需要先觀察一下幾個結果，然後（很可惜的）靠猜
我一個數學系的朋友說這個問題是也可以從根本上一點一點推，但是很難我可能聽不懂
基本上透過觀察，我們可以知道至少偶數的一定會掛掉（畢竟是數到二），那當在場原本是二的倍數的人死掉之後，下一輪是哪些人會死呢？
這邊有一個很好玩的偷換概念的方法，我們其實可以這樣想
每次報數完一輪，所有人重新編號，編到偶數的人就可以直接說再見
那要怎麼重新編號，這就是我們要討論的問題了
透過觀察，如果總人數是偶數，則「所有人的新編號是舊編號的兩倍減一」，因為這個關係，我們也可以假設/推論最後活著人的編號也照個這個規律
今天我們用 J(n) 這個函式表示「假設有總共有 n 個人，則第 J(n) 編號的人可以活到最後」，我們可以發現 J(10) = 5 並且 J(20) = 2 * J(10) - 1 = 9 符合我們的預期（你可能會想自己試試看 20 個人時到底是不是第九人活下來）
相反的，如果人數是奇數，則 「所有人的新編號是舊編號的兩倍加一」，所以恭喜，我們得到一個遞迴解
- J(1) = 1
- J(2n) = 2J(n) - 1
- J(2n +1) = 2J(n) + 1
然後因為我們實在需要一個 closed-form 解，所以我們又需要透過觀察得到這個很不友善的解
令 n = 2m + l ，則 J(n) = J(2m + l) = 2l + 1
(for m >= 0 and 0 <= l < 2m)
Btw 你們應該也可以看得出來我很討厭透過觀察獲得解，這感覺就很像直接給你答案不跟你講原因，「阿就是這樣阿沒有原因阿」
雖然這個解看起來不是很友善，但是它其實還挺好理解的：
你想辦法找到離 n 最近但比它小的 2 的次方數，然後跟那個數字的距離就是他的 l，因為是最近的所以 l 一定會小於 2m
舉例來說 J(15)，離 15 最近的 2 次方是 8 ，15 - 8 = 7，所以 J(15) = 2 * 7 + 1 = 15
二進位表示
如果我們今天用二進位表示數字的話，上面那個 Closed-form 的詭異寫法會瞬間變成一個位元運算就能作到的事（這能極大優化計算效率！）
用剛剛我們用魔法得到的 close form solution，我們先讓 n 用二進位表示，也就是 (bmbm-1 … b1b0)2
因為 n = 2m + l，我們可以做以下操作
n = (1 bm-1 bm-2 … b1 b0)2
l = n - 2m，也就是去掉最高位
l = (0 bm-1 bm-2 … b1 b0)2
乘二等價於左移
2l = (bm-1 bm-2 … b1 b00)2
2l + 1 = (bm-1 bm-2 … b1 b01)2
J(n) = 2l + 1
J(n) = (bm-1 bm-2 … b1 b01)2
bm 必為 1
J(n) = (bm-1 bm-2 … b1 b0bm)2
到這邊我們證明可以用左循環位移實做
J((bmbm-1 … b1b0)2) = (bm-1 … b1b0bm)2
真的等價嗎？
我們在上面驗證了 J(n) 就是對 (n)2 做循環左移一個位元，但是事情真的這麼簡單嗎？
我們來簡單考慮一下完備性：
假設自然數 n 有 m-1 個位元（也就是前面提到的 2m + 1）
- 那麼假設對 n 做 m+1 次操作，得到的東西有意義嗎？它等價於對 n 做 m+1 次 J() 操作嗎？
這是個腦筋急轉彎，Concrete math 裡面有解答，但是不是很直白（因為我看到前人的筆記在上面畫一個問號，一個清華學子畫問號我覺得這應該某種程度代表問題有難度）
你可以花時間好好想一下
… 答案是沒有意義
原因是 J() 要等價成左循環位移有個前提，也就是一開始的 “0 <= l < 2m“ 這個條件，換到位元運算下這個條件就會變成 m =1 （或者說是 leading bit 必須要為 1 ）
舉個書上的例子好了
J((1101)2) = (1011)2
J((1011)2) = (0111)2
這個時候你可以注意到 leading bit 已經變成 0 了，以十進制表示的話這個值應該是 7，事實上下個迭代我們應該用 (111)2 去掉前面的零繼續
如果我們不去掉這個零，啥都不做的話就違背一開始的假設，也就是「最近的且比 n 小的 2m」
所以這邊對「J() 等價為左循環位移」的描述應該更正為，「J() 等價為左循環位移，然後移除 leading zero bit」
可惜的是，就我所知除非你自己實現 rotate shift 不然原生指令是不可能幫你刪掉 leading zero bit 的，但是自己實做等於就失去底層指令加速的優勢了
所以請不要使用一次以上的左循環位移，這可能導致你開頭位元變成零
- 承上，那如果我做了 m+1 次左循環位移操作，這樣不是會得到 n 自己嗎？（等於全部都循環過一次了）
首先請你仔細上面對左循環位移操作的補充，「我們還需要刪掉開頭的零位元」
然後我們就會開始發現，回不去了
由於我們在循環過程中總是會把所有的 zero bit 刪掉，這導致我們就算一直跑 J() 也會讓它卡在 J(n) = n 之後就不動了（此時所有的位元都是 1，再怎麼左循環位移都沒用）
從原始的 J(n) = 2l + 1 也可以得知 J() 一定會是一個遞減的函數，不過很有趣的是，它會收縮在那些所有位元都是 1 的數字上
為什麼會等價 ？
Brace yourself for impact !
你可能會跟我一樣開始懷疑 左循環位移 到底代表什麼，到底該怎麼去理解它
為了解釋這樣的關係，我們需要開始擴展原本的等式，讓它變成一個更廣泛的定義
等式擴充
我們一開始有的等式是這些關係：
- J(1) = 1
- J(2n) = 2J(n) - 1
- J(2n + 1) = 2J(n) + 1
現在我們把後面的常數用符號代替，變成：
- F(1) = α
- F(2n) = 2J(n) + β
- F(2n + 1) = 2J(n) + γ
或者說，我們可以乾脆寫成這樣：
F(1) = α
F(2n + j) = 2F(n) + βj
並且令 j = 0, 1 （其實這邊 j 應該定義為小於 2 的數）
要怎麼理解/想像這組函數呢？ 我們於是把這組函數拆開來 （relax）
我們已知 n 可以用 (bmbm-1 … b1b0)2 的二進制方式表示，因此帶入上面那個推廣公式
右移本身就等於用整數除法除二，它現在又把 βb0 這個餘數拿出來，就便成了等價的除法
F((bmbm-1 … b1b0)2) = 2F((0bmbm-1 … b2b1)2) + βb0
… = 4F((00bmbm-1 … b3b2)2) + 2βb1 + βb0
… = 2m F((bm)2) + 2m-1βbm-1 + … + 2βb1 + βb0
根據定義，起始位元一定要為 1
… = 2mα + 2m-1βbm-1 + … + 2βb1 + βb0
你有沒有發現，這擺明就是二進位的轉換
F((bmbm-1 .. b1b0)) = (αβbm-1βbm-2 … βb1βb0)2
我們終於可以從原本的遞進關係推到它跟二進制的關聯了
所以到底為什麼會等價左循環位移？
我們假設想算 J((1 1 0 0 1 0 0)2) ，因為 F() 在 α = 1, β = -1, γ = 1 時會回到 J() 的函數，因此 βb0 = β = -1, 而 βb1 = γ = 1
因此我們可以得到 J((1 1 0 0 1 0 0)2) = (1 1 -1 -1 1 -1 -1)2
也就是所有零 0 都變成了 -1
轉成十進位就是 1 * 64 + 1 * 32 + (-1) * 16 + (-1) * 8 + 1 * 4 + (-1) * 2 + (-1) * 1 = 73
簡單做點 sanity check，因為首位必為一，所以算出來一定是正數
那這個運算跟 左循環位移 有什麼關聯阿？
因為實際上， J((1 0 0 0 0 0 0)2) = (1 -1 -1 -1 -1 -1 -1)2 = (0 0 0 0 0 0 1)2
透過把最高位的 1 左循環移到最低位，以上數例子來說就是把自己的 63 （最高位的 64 減掉最低位的 1）分給其他位元，讓其他位元的人都上升 1
以我自己比較粗糙的理解，轉換過程就是這樣 J(1 1 0 0 1 0 0)2 = (1 1 -1 -1 1 -1 -1)2
之後把最高位移到最低位，其他位全部加一
(1 1 -1 -1 1 -1 -1)2 = (0 2 0 0 2 0 1)2
之後把二進制裡面的 2 進位，就等於左循環位移的結果了
(0 2 0 0 2 0 1)2 = (1 0 0 1 0 0 1)2
事實上，這個等式可以擴充成不同進制間的轉換，像是這樣：
F(j) = αj
F(dn + j) = cF(n) + βj ，其中 0 <= j < d
不過這邊就沒那麼驚奇了，所以就不繼續提下去了
後序
做這類 brain teaser 真的很好玩，從知道問題到思考解法，到思考為什麼它會有用，什麼時候可以用什麼時候可以用，為什麼這個轉換是有效的，這是不是表示我可以把它背後的概念用在別的地方
不過真的挺費時間的，從一開始覺得怪怪的，到開始可以想像、類比描述你的問題，到後面開始思考原因
其實只看數學式還挺無聊的，我還是挺推薦直接去看書，然後花上一點時間思考（我零零碎碎的時間加起來，第一章應該看了有兩三個下午）