歪んだ二進数システム

歪んだ2進数体系は、非標準の位置記数法であり、n番目の桁は、2進数のように桁の倍数を表すのではなく、桁の倍数（桁は0から始まる）を表します。各桁の値は0、1、または2です。数値は、複数の歪んだ2進数表現を持つことができます。例えば、10進数15は、1000、201、122と表記できます。各数値は、歪んだ2進数標準形式で一意に表記できます。この標準形式では、桁2は最大で1つしか存在せず、最下位の非ゼロ桁である必要があります。この場合、15は標準形式では1000と表記されます。 $2^{n+1}-1$ $2^{n}$

例

0から15までの数字の標準的な歪んだ2進表現は次の表に示すとおりである。^[1]

小数点	バイナリ	スキューバイナリ	三元法
0	0	0	0
1	1	1	1
2	10	2	2
3	11	10	10
4	100	11	11
5	101	12	12
6	110	20	20
7	111	100	21
8	1000	101	22
9	1001	102	100
10	1010	110	101
11	1011	111	102
12	1100	112	110
13	1101	120	111
14	1110	200	112
15	1111	1000	120

算術演算

スキューバイナリの利点は、各インクリメント操作が最大1回のキャリー操作で実行できることです。これは、という事実を利用しています。スキューバイナリ数のインクリメントは、2つの桁目を0に設定し、次の桁を0から1、または1から2にインクリメントすることで行われます。数値がランレングス符号化の形式を用いて非ゼロの桁のリンクリストとして表現される場合、インクリメントとデクリメントは定数時間で実行できます。 $2(2^{n+1}-1)+1=2^{n+2}-1$

その他の算術演算は、スキューバイナリ表現とバイナリ表現を切り替えることによって実行できます。^[2]

10進数と歪んだ2進数の変換

10進数を歪んだ2進数に変換するには、次の式を使用します。^[3]

基本ケース: $a(0)=0$

誘導例： $a(2^{n}-1+i)=a(i)+10^{n-1}$

境界: $0\leq i\leq 2^{n}-1,n\geq 1$

歪んだ2進数を10進数に変換するには、歪んだ2進数の定義を使用できます。

$S=\sum _{i=0}^{N}b_{i}(2^{i+1}-1)$ ただし、最下位ビット (lsb) のみが 2 です。 $b_{i}\in {0,1,2}$ $b_{lsb}$

10進数を歪んだ2進数に変換するC++コード

#include <iostream> #include <cmath> #include <アルゴリズム> #include <反復子>    名前空間stdを使用します。  長いdp [ 10000 ]; // 式 a(0) = 0; を使用。n >= 1 の場合、a(2^n-1+i) = a(i) + 10^(n-1)。0 <= i <= 2^n-1 の場合、// The On-Line Encyclopedia of Integer Sequences (https://oeis.org/A169683) より引用。long convertToSkewbinary ( long decimal ){   int maksIndex = 0 ;長いマスク= 1 ; while ( maks < 10 進数){ maks *= 2 ; maksIndex ++ ; }                   for ( int j = 1 ; j <= maksIndex ; j ++ ){ long power = pow ( 2 , j ); for ( int i = 0 ; i <= power -1 ; i ++ ) dp [ i + power -1 ] = pow ( 10 , j -1 ) + dp [ i ]; }                              return dp [ decimal ]; } int main () { std :: fill ( std :: begin ( dp ), std :: end ( dp ), -1 ); dp [ 0 ] = 0 ; //https://oeis.org/A169683に記載されている数値と比較できますfor ( int i = 50 ; i < 125 ; i ++ ){ long current = convertToSkewbinary ( i ); cout << current << endl ; }                                0を返す; }

歪んだ2進数を10進数に変換するC++コード

#include <iostream> #include <cmath>  名前空間stdを使用します。  // Decimal = (0|1|2)*(2^N+1 -1) + (0|1|2)*(2^(N-1)+1 -1) + ... // + (0|1|2)*(2^(1+1) -1) + (0|1|2)*(2^(0+1) -1) // // 想定される入力: 0、1、または 2 の数字で、最下位ビット/桁のみが 2 である正の整数/long。// long convertToDecimal ( long skewBinary ){   int k = 0 ; long decimal = 0 ; while ( skewBinary > 0 ){ int digit = skewBinary % 10 ; skewBinary = ceil ( skewBinary / 10 ); decimal += ( pow ( 2 , k + 1 ) -1 ) * digit ; k ++ ; } return decimal ; } int main () {                              intテスト[] = { 0 、1 、2 、10 、11 、12 、20 、100 、101 、102 、110 、111 、112 、120 、200 、1000 };    for ( int i = 0 ; i < sizeof ( test ) / sizeof ( int ); i ++ ) cout << convertToDecimal ( test [ i ]) << endl ;;             0を返す; }

歪んだバイナリ表現からバイナリ表現へ

歪んだ2進数が与えられた場合、その値はループ処理によって計算できます。ループ処理では、の連続する値を計算し、各桁がそれぞれ1または2になるように1回または2回加算します。ここでは、ビット表現と1回の減算のみを使用する、より効率的な手法を示します。 $2^{n+1}-1$ $n$ $n$

2を除いた1を含む形式の歪んだ2進数は、2進数からを引いた値に等しい。は、その数字が何回繰り返されるかを表すものとする。1を含む形式の歪んだ2進数は、 2進数からを引いた値に等しい。 $b_{0}\dots b_{n}$ $m$ $0b_{0}\dots b_{n}$ $m$ $d^{c}$ $d$ $c$ $0^{c_{0}}21^{c_{1}}0b_{0}\dots b_{n}$ $m$ $0^{c_{0}+c_{1}+2}1b_{0}\dots b_{n}$ $m$

バイナリ表現からスキューバイナリ表現へ

前のセクションと同様に、 1 を含む形式の2進数は、歪んだ2進数にを加えた値に等しい。加算は定義されていないため、加算は数を倍に増やすことに相当することに注意されたい。ただし、はの対数で制限され、増加には定数時間かかる。したがって、2進数を歪んだ2進数に変換するには、数の長さに比例した時間がかかる。 $b$ $b_{0}\dots b_{n}$ $m$ $b_{1}\dots b_{n}$ $m$ $m$ $m$ $m$ $b$

アプリケーション

歪んだ二項数は、スタック抽象データ型の操作を可能にし、スタック要素のシーケンスへの効率的なインデックス付けも可能にする純粋に機能的なデータ構造として、1983年にユージン・マイヤーズによって開発されました。 ^[4]その後、歪んだ二項ヒープは、定数時間で最悪のケースの挿入操作をサポートする二項ヒープの変種です。 ^[5]

参照

注記

^ Sloane, N. J. A. (編). 「シーケンスA169683」.整数シーケンスのオンライン百科事典. OEIS財団.
^ Elmasry, Amr; Jensen, Claus; Katajainen, Jyrki (2012). 「2つのSkew-Binary Numeral Systemsと1つのアプリケーション」(PDF) .計算システム理論. 50 : 185–211 . doi :10.1007/s00224-011-9357-0. S2CID 253736860.
^ オンライン整数列百科事典。「標準的な歪んだ2進数」。
^ Myers, Eugene W. (1983). 「応用型ランダムアクセススタック」. Information Processing Letters . 17 (5): 241– 248. doi :10.1016/0020-0190(83)90106-0. MR 0741239.
^ Brodal, Gerth Stølting; Okasaki, Chris (1996年11月). 「最適な純粋関数型優先キュー」. Journal of Functional Programming . 6 (6): 839– 857. doi : 10.1017/s095679680000201x .

[1] Sloane, N. J. A. (編). 「シーケンスA169683」.整数シーケンスのオンライン百科事典. OEIS財団.

[2] Elmasry, Amr; Jensen, Claus; Katajainen, Jyrki (2012). 「2つのSkew-Binary Numeral Systemsと1つのアプリケーション」(PDF) .計算システム理論. 50 : 185–211 . doi :10.1007/s00224-011-9357-0. S2CID 253736860.

[3] オンライン整数列百科事典。「標準的な歪んだ2進数」。

[4] Myers, Eugene W. (1983). 「応用型ランダムアクセススタック」. Information Processing Letters . 17 (5): 241– 248. doi :10.1016/0020-0190(83)90106-0. MR 0741239.

[5] Brodal, Gerth Stølting; Okasaki, Chris (1996年11月). 「最適な純粋関数型優先キュー」. Journal of Functional Programming . 6 (6): 839– 857. doi : 10.1017/s095679680000201x .