Contact

Facebook Page: https://www.facebook.com/GoogolForex/
YouTube Channel: https://www.youtube.com/c/AngrywaterNet
Global Prime IB Plan: https://secure.globalprime.com.au/?promocode=KCL , Refer ID: KCL
中文 (台灣地區) ICMarkets IB Plan: https://www.icmarkets-zhv.com/global/tw/?camp=12437 , Refer ID: 12437
英文 (台灣以外地區) ICMarkets IB Plan: https://www.icmarkets.com/en/?camp=12437 , Refer ID: 12437

Adsense Top

2017年6月7日 星期三

《齒差轉輪二進位數》(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

沒有留言:

張貼留言

注意:只有此網誌的成員可以留言。