《齒差轉輪二進位數》(Gear Shift Binary)

目的：

解決以 bit = 1 之數量多寡為計數方式之數字序列表示，而不以原二進位計算法為數列順序之算數法。

例如，原二進位系統 1 ~ 8 分別為：

0001
0010
0011
0100
0101
0110
0111
1000

齒差轉輪二進位數之 1 ~ 8 ，若以 7 bits 為資料寬度，則分別為：

000 0001 , idx = 0
000 0010 , idx = 1
000 0100 , idx = 2
000 1000 , idx = 3
001 0000 , idx = 4
010 0000 , idx = 5
100 0000 , idx = 6
000 0011 , idx = 7

概念：

=============

1. 現假設實現資料寬度為 7 bits，則單一「齒輪」 (只有 1 個 bit = 1) 就有 7 齒，當轉動 (位元移動) 時，其為 1 之值以下為無效位元，標記為 x ，其上則為 0，表現如下：

000 0001 = 未轉動
000 001x = 轉動 1
000 01xx = 轉動 2
000 1xxx = 轉動 3

依此類推，直到

1xx xxxx = 轉動 6

轉動 7 則代表要進一位，即多一「齒輪」加入運算。

=============

2. 現假設有 2 ~ 7 bits 為 1 ，則為有 2 「齒輪」的狀態，轉動規則為，任何代表較高位元之齒輪皆不得將其有 1 之 bit 旋轉至任何較低位元之齒輪出現 x 之處，舉例，假如第一個齒輪編號為 G0，第二為 G1，則 Gn 為 1 的 bit 放置位置，不可以和 G0 ~ G(n-1) 任何出現 x 的位置重疊，任何齒輪有 1 的 bit，亦不可和任何其他的齒輪有 1 的位置重疊。轉動時則以 Gn 為優先，Gn 轉至「進位」，才轉動 G(n-1)，直到 G0 也轉動至無法轉動為止，才再增加一齒輪，表現如下：

2 bits:

轉動 0, 總和值 = 000 0011

000 001x G1
000 0001 G0

轉動 1, 總和值 = 000 0101

000 01xx G1 (左移 1 bit)
000 0001 G0

轉動 2, 總和值 = 000 1001

000 1xxx G1 (再左移 1 bit)
000 0001 G0

直到轉動 5, 總和值 = 100 0001

1xx xxxx G1 (和轉動 0 比，共左移 5 bits)
000 0001 G0

轉動 6 則需「進位」，總和值 = 000 0110

000 01xx G1 (1 不能和 G0 之 1 or x 重疊，所以進位後將被迫再左移 1 bit)
000 001x G0 (發生進位，1 左移 1 bit)

依此類推，直到

轉動 20, 總和值 = 110 0000

1xx xxxx G1
01x xxxx G0

--------------------------------------

若以 4 bits 有 1 為例，則需要 4 個齒輪

轉動 0, 總和值 = 000 1111

000 1xxx G3
000 01xx G2
000 001x G1
000 0001 G0

隨便舉例，直到

轉動 4, 總和值 = 010 1011

001 xxxx G3 (1 不能和 G0 ~ G2 之 1 or x 重疊，所以進位後將被迫再左移 1 bit)
000 1xxx G2 (發生進位，1 左移 1 bit)
000 001x G1
000 0001 G0

轉動 5, 總和值 = 010 1011

01x xxxx G3 (左移 1 bit)
000 1xxx G2
000 001x G1
000 0001 G0

依此類推，直到

轉動 34, 總和值 = 111 1000

1xx xxxx G3
01x xxxx G2
001 xxxx G1
000 1xxx G0

======================

3. 當同樣資料寬度中的 1 數量首次超過 0 的數量時，則可視為 0 與 1 互換之後的鏡射狀況，例如, 000 0011 = 2 bit 為 1，與 001 1111 = 2 bit 為 0，兩種狀況的組合數是相同的。表現如下：

若以 7 bits 寬度為例，則各種「齒輪」所可能的組合數將如下所示

7 齒 111 1111 = 1
6 齒 011 1111 = 7
5 齒 001 1111 = 21
4 齒 000 1111 = 35 (1 數量首次超過 0，開始鏡射)

----------------------

3 齒 000 0111 = 35
2 齒 000 0011 = 21
1 齒 000 0001 = 7
0 齒 000 0000 = 1

======================

4. 組合數的算法，可用 C( N, r )，其中 N = 資料寬度， r = bit = 1 的數量。例如，若有 2 bits 為 1 有多少種組合，則可代入 C( 7, 2 ) = n!/((n-r)!r!) = 7!/(5!2!) = 21

//==================================================================
// Modified from:
https://gist.github.com/tzengyuxio/5478a1f29cb2a8532238#file-binarystatetoindex-cpp
// and:
https://gist.github.com/tzengyuxio/554c26d9300e455438be