不論層數為何

光看第n步需要移動哪一層就可以發現規律

[ (1 2 1) 3 (1 2 1) ] 4 [ (1 2 1) 3 (1 2 1) ] 5 [ (1 2 1) 3 (1 2 1)  ] 4 [ (1 2 1) 3 (1 2 1) ]...

也就是說答案只跟步數有關，而跟層數無關!!

然後看一下n的二進位值跟解答的對應關係:

00001  ->  1

00010  ->  2

00011  ->  1

00100  ->  3

00101  ->  1

00110  ->  2

00111  ->  1

01000  ->  4

會發現答案就是「從最低位數來第一個不為0的位置」~~~

例: 第52步的二進位值為110100，右邊第3位開始不為0，因此答案為3~~~

tips: 可以用(step&1)取得最後一位的數字，每次迴圈完就step>>=1，看幾次之後(step&1)不為0就是答案

x & -x 可以取得ｘ的二進位最後一個 bit 的(十進位)值 
__lg( x & -x ) 則能將上述的值轉換為２的次方項

x & -x 可以取得ｘ的二進位最後一個 bit 的(十進位)值 
__lg( x & -x ) 則能將上述的值轉換為２的次方項

剛剛發現有內建函數:

 __builtin_ctz(a) :可以返回右邊第一個1之後的0的個數，+1即可

或者直接用

 __builtin_ffs(a) :可以返回右邊第一個1的位置

不知道為什麼但前者實測比較快