ネガベース

負塩基 （または負の基数）は、非標準位置数字システムを構築するために使用することができます。他の場所価値システムと同様に、各位置にはシステムのベースの適切な倍数の倍数が保持されます。しかし、その底は負です。つまり、ある自然数r（r≥2）に対して底bは-rに等しくなります。

負のベースシステムは、標準の場所と値のシステムと同じすべての数値に対応できますが、正と負の両方の数値は、マイナス記号（またはコンピューター表現では符号ビット）を使用せずに表されます。この利点は、算術演算の複雑さが増すことで相殺されます。通常、負の記号に含まれる情報を格納する必要があるため、多くの場合、負の基数はその正の基数に相当するものよりも1桁長くなります。

負ベース位置数字システムのための共通の名前は、対応する正ベース・システムの名前にnega-付けることによって形成されます。たとえば、 ネガデシマル （ベース-10）は10進数（ベース10）、 ネガバイナリ （ベース-2）からバイナリ（ベース2）、 ネガタナリ （ベース-3）からターナリ （ベース3）、 ネガクォータナリー （ベース-4）に対応四元へ（基数4）。

例

基数bが-10であるネガデシマルシステムの表現12243の意味を考えてみましょう。

（-10）4 = 10,000	（-10）3 = -1,000	（-10）2 = 100	（-10）1 = -10	（-10）0 = 1
1	2	2	4	3

10,000 +（−2,000）+ 200 +（−40）+ 3 = 8,163であるため、負数表記の表現12,243-10は10進表記の8,16310と同等ですが、10進数の−8,16310は9,977-10と記述されます負数で。

歴史

負の数値ベースは、VittorioGrünwaldの1885年に出版されたGiornale di Matematiche di Battagliniで最初に検討されました。負の塩基は、1936年にAJ Kempnerによって、1959年にZdzisławPawlakおよびA. Wakuliczによって独立して再発見されました。

Negabinaryは、ワルシャワのMathematical InstituteのZ. PawlakとA. Lazarkiewiczのアイデアに基づいて、1957〜59年に構築されたポーランドの初期コンピューターBINEG（およびUMC）に実装されました。それ以降の実装はまれです。

表記と使用

基数を-rと示すと、すべての整数aは、

a = ∑i = 0ndi（−r）i {\ displaystyle a = \ sum _ {i = 0} ^ {n} d_ {i}（-r）^ {i}}

各ディジットDKは0からRまでの整数である- 1と先頭桁DN> 0（しない限りN = 0）です。 aのベース-r展開は、文字列d n d n -1… d 1 d 0によって与えられます。

したがって、負の基数システムは、基数は正であるが数字は部分的に負の範囲から取られる、バランスの取れた3進法などの符号付き数字表現と比較できます。（以下の表では、値-1の数字は単一文字Tとして記述されています。）

いくつかの数値は、ベースrとベース-rで同じ表現を持っています。たとえば、100〜109の数字は、10進数と負数で同じ表現を持ちます。同様に、

17 = 24 + 20 =（− 2）4 +（− 2）0 {\ displaystyle 17 = 2 ^ {4} + 2 ^ {0} =（-2）^ {4} +（-2）^ {0 }}

バイナリでは10001、ネガバイナリでは10001で表されます。

いくつかの正の基底と対応する負の基底に展開された数値は次のとおりです。

小数	ネガデシマル	バイナリ	ネガバイナリ	三元系	ネガタナリー	バランスの取れた三元	ネガバランスターナリー	第四紀	ネガクォータナリー
−15	25	−1111	110001	−120	1220	T110	11T0	−33	1301
⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮
−5	15	−101	1111	−12	21	T11	TT1	−11	23
−4	16	−100	1100	−11	22	TT	1T	−10	10
−3	17	−11	1101	−10	10	T0	10	−3	11
−2	18	−10	10	−2	11	T1	11	−2	12
−1	19	−1	11	−1	12	T	T	−1	13
0	0	0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1	1	1
2	2	10	110	2	2	1T	TT	2	2
3	3	11	111	10	120	10	T0	3	3
4	4	100	100	11	121	11	T1	10	130
5	5	101	101	12	122	1TT	11T	11	131
6	6	110	11010	20	110	1T0	110	12	132
7	7	111	11011	21	111	1T1	111	13	133
8	8	1000	11000	22	112	10T	10T	20	120
9	9	1001	11001	100	100	100	100	21	121
10	190	1010	11110	101	101	101	101	22	122
11	191	1011	11111	102	102	11T	1TT	23	123
12	192	1100	11100	110	220	110	1T0	30	110
13	193	1101	11101	111	221	111	1T1	31	111
14	194	1110	10010	112	222	1TTT	TT1T	32	112
15	195	1111	10011	120	210	1TT0	TT10	33	113
16	196	10000	10000	121	211	1TT1	TT11	100	100
17	197	10001	10001	122	212	1T0T	TT0T	101	101
18	198	10010	10110	200	200	1T10	TTT0	102	102

ネガバランス三元法を除いて、負の整数のベース-r展開は偶数桁であり、非負の整数のベース-r展開は奇数桁であることに注意してください。

計算

数値のベース-r展開は、-rによる除算を繰り返すことで見つけることができ、非負の剰余ε{0,1、…、r-1} {\ displaystyle \ in \ {0,1、\ ldotsを記録します。 r-1 \}}、最後から始めてそれらの残りを連結します。 a / b = c 、剰余d、 bc + d = a 、したがってd = a - bcであることに注意してください。正しい変換に到達するには、cの値を選択して、dが非負で最小になるようにする必要があります。これは、次の例の4行目に例示されています。この例では、-1剰余2ではなく2剰余1に等しくなるように–5÷–3を選択する必要があります。

たとえば、146を10進数から負の整数に変換するには：

146÷（−3）= − 48剰余⁡2−48÷（−3）= 16剰余⁡016÷（−3）= − 5剰余⁡1−5÷（−3）= 2剰余⁡12÷（− 3）= 0余り⁡2 {\ displaystyle {\ begin {array} {rr} 146 \ div（-3）=＆-48〜\ operatorname {remainder}〜2 \\-48 \ div（-3）=＆16 〜\ operatorname {remainder}〜0 \\ 16 \ div（-3）=＆-5〜\ operatorname {remainder}〜1 \\-5 \ div（-3）=＆2〜\ operatorname {remainder}〜1 \ \ 2 \ div（-3）=＆0〜\ operatorname {remainder}〜2 \ end {array}}}

残りを逆読みすると、14610：21102-3のネガタナリ表現が得られます。

証明：（（（ 2・（–3）+ 1 ）・（–3）+ 1 ）・（–3）+ 0 ）・（–3）+ 2 = 14610。

ほとんどのプログラミング言語では、負の数を負の数で除算した結果（整数演算）は0に丸められ、通常は負の剰余が残ります。このような場合、a =（− r ） c + d =（− r ） c + d − r + r =（− r ）（ c + 1）+（ d + r ）です。なぜなら| d | r、（ d + r ）は正の剰余です。したがって、このような場合に正しい結果を得るには、上記のアルゴリズムのコンピューター実装は、商と剰余にそれぞれ1とrを追加する必要があります。

実装コードの例

ネガバイナリC＃に

static string ToNegabinary（int value）{string result = string.Empty; while（値！= 0）{int剰余=値％-2;値=値/ -2; if（remainder 0）{剰余+ = 2;値+ = 1; } result = remaining.ToString（）+ result; }結果を返す; }

C ++

auto to_negabinary（int value）{std :: bitset sizeof（int）* CHAR_BIT> result; std :: size_t bit_position = 0; while（value！= 0）{const auto div_result = std :: div（value、-2）; if（div_result.rem 0）value = div_result.quot + 1;それ以外の値= div_result.quot; result.set（bit_position、div_result.rem！= 0）; ++ bit_position; }結果を返す; }

ネガタナリC＃へ

static string negaternary（int value）{string result = string.Empty; while（値！= 0）{int剰余=値％-3;値=値/ -3; if（remainder 0）{剰余+ = 3;値+ = 1; } result = remaining.ToString（）+ result; }結果を返す; }

Visual Basic .NET

Private Shared Function ToNegaternary（value As Integer）As String Dim result As String = String.Empty While value > 0 Dim remaining As Integer = value Mod -3 value / = -3 If remaining 0 Then remaining + = 3 value + = 1終了If result = remaining.ToString（）＆result End While Return結果End関数

Python

def negaternary（i）：i == 0の場合：digits = else：digits = while i！= 0：i、剰余= divmod（i、-3）剰余0：i、剰余= i + 1、剰余+ 3桁のappend（str（remainder））return '' .join（digits）

Common Lisp

（defun negaternary（i）（if（zerop i） "0"（let（（digits ""）（rem 0）））（loop while（not（zerop i））do（progn（multiple-value-setq（i rem ）（i -3を切り捨てる）（when（minusp rem）（incf i）（incf rem 3））（setf digit（連結 'string（write-to-string rem）数字））））数字）））

負のベースJava

public String negativeBase（int integer、int base）{String result = ""; int number = integer; while（number！= 0）{int i = number％base;数値/ =基数; if（i 0）{i + = Math.abs（base）; number ++; } result = i + result; }結果を返す; }

AutoLisp

間隔から：

（defun negabase（num baz / dig rst）;; NUMは任意の数値です。BAZは区間内の任意の数値です。;; ;; NUMとBAZは、浮動小数点数の場合は整数に切り捨てられます（例14.25 ;; 14に切り捨てられ、-123456789.87から-123456789など）。（if（and（numberp num）（numberp baz）（=（fix baz）-2）（>（fix baz）-11））（progn（setq baz（float（fix baz））num（float（fix num））dig（if（= num 0） "0" ""））（while（/ = num 0）（setq rst（-num（* baz（setq num（fix（/ num baz）））））））if（minusp rst）（setq num（1+ num）rst（-rst baz）））（setq dig（strcat（itoa（fix rst））dig）））dig）（progn（prompt（cond（（and（not（numberp num））（not（numberp baz））） "\ n間違った番号とネガベース。"）（（not（numberp num）） "\ n間違った番号。）（（not（numberp baz）） "\ n間違ったネガベース。"）（t "\ nネガベースは間隔内にある必要があります。"）））（princ）））））

PHP

整数から負のベースへの変換：

function toNegativeBase（$ no、$ base）{$ digits = array（）; $ base = intval（$ base）; while（$ no！= 0）{$ temp_no = $ no; $ no = intval（$ temp_no / $ base）; $ remainder =（$ temp_no％$ base）; if（$ remainder 0）{$ remainder + = abs（$ base）; $ no ++; } array_unshift（$ digits、$ remainder）; } $ digitsを返します。 }

Visual Basic .NET

関数toNegativeBase（Number As Integer、base As Integer）As System.Collections.Generic.List（Of Integer）As Dim digits As New System.Collections.Generic.List（Of Integer）while Number > 0 Dim剰余As Integer = Number Mod base Number = CInt（Number / base）剰余0の場合、剰余+ = system.math.abs（base）Number + = 1 end digits.digits.Insert（0、剰余）end while return return end関数

ショートカット計算

次のアルゴリズムは、

入力はビット文字列で利用でき、（ベース+2;桁∈{0,1} {\ displaystyle \ in \; \ {0,1 \}}）（今日のほとんどのデジタルコンピューターと同様）でコード化されています。
このようなビット文字列を操作する加算（+）およびxor（^）操作があります（今日のほとんどのデジタルコンピューターのように）。
出力数字のセットD {\ displaystyle D}は標準です。 e。 D = {0、| b | -1} {\ displaystyle D = \ {0、| b | -1 \}}基数b∈{−2、−4} {\ displaystyle b \ in \ {-2、 -4 \}}、
出力は同じビット文字列形式でコーディングされますが、場所の意味は別のものです。

ネガバイナリへ

ネガバイナリへの変換（基数-2;桁∈{0,1} {\ displaystyle \ in \; \ {0,1 \}}）は、顕著なショートカット（C実装）を可能にします。

unsigned int toNegaBinary（unsigned int value）//標準バイナリの入力{unsigned int Schroeppel2 = 0xAAAAAAAA; // = 2/3 *（（2 * 2）^ 16-1）= ... 1010 return（value + Schroeppel2）^ Schroeppel2; // eXclusive OR //要素の文字列として解釈される結果の符号なしintε{0,1}（ビット）}

D. Librik（Szudzik）によるものです。ビット単位のXOR部分は、元々Schroeppel（1972）によるものです。

同じショートカット計算用のJavaScriptポート：

function toNegaBinary（number）{var Schroeppel2 = 0xAAAAAAAA; // NegaBinary文字列に変換return（（number + Schroeppel2）^ Schroeppel2）.toString（2）; }

ネガクォータナリーへ

ネガ四元への変換（基数-4;桁∈{0,1,2,3} {\ displaystyle \ in \; \ {0,1,2,3 \}}）は同様のショートカット（C実装）を許可します：

unsigned int toNegaQuaternary（unsigned int value）//標準バイナリの入力{unsigned int Schroeppel4 = 0xCCCCCCCC; // = 4/5 *（（2 * 4）^ 8-1）= ... 11001100 = ... 3030 return（value + Schroeppel4）^ Schroeppel4; // eXclusive OR //要素の文字列として解釈される結果の符号なしintε{0,1,2,3}（ビットのペア）}

同じショートカット計算用のJavaScriptポート：

function toNegaQuaternary（number）{var Schroeppel4 = 0xCCCCCCCC; // NegaQuaternary Stringに変換return（（number + Schroeppel4）^ Schroeppel4）.toString（4）; }

算術演算

次に、ネガバイナリの算術演算について説明します。大きなベースでの計算も同様です。

添加

負数の追加は、最下位ビットからビット単位で進みます。各加数からのビットは、前のビット（LSBで0）からの（バランスのとれた3進）キャリーと合計されます。次に、この合計は出力ビットに分解され、表に示すように次の反復に持ち越されます。

和		出力			コメント
和		ビット	運ぶ		コメント
−2	010−2	0	1	01−2	-2は、減算中にのみ発生します。
−1	011-2	1	1	01−2
0	000−2	0	0	00-2
1	001−2	1	0	00-2
2	110-2	0	−1	11−2
3	111-2	1	−1	11−2	3は追加時にのみ発生します。

たとえば、この表の2行目は、 -1 = 1 + 1 ×-2という事実を表しています。 5行目は、 2 = 0 + -1 ×-2と表示されます。等

例として、1010101-2（1 + 4 + 16 + 64 = 85）および1110100-2（4 + 16-32 + 64 = 52）を追加するには、

キャリー：1 -1 0 -1 1 -1 0 0 0最初の加数：1 0 1 0 1 0 1 2番目の加数：1 1 1 0 1 0 0 + --------------- -----------番号：1 -1 2 0 3 -1 2 0 1ビット（結果）：1 1 0 0 1 1 0 0 1キャリー：0 1 -1 0 -1 1 -1 0 0

結果は110011001-2（1 − 8 + 16 − 128 + 256 = 137）です。

別の方法

2つの負の数を追加するときに、キャリーが生成されるたびに、余分なキャリーが次のビットに伝搬されます。上記と同じ例を考えます

追加キャリー：1 1 0 1 0 0 0キャリー：1 0 1 1 0 1 0 0 0最初の加数：1 0 1 0 1 0 1 2番目の加数：1 1 1 0 1 0 0 + -------- ------------------回答：1 1 0 0 1 1 0 0 1ネガバイナリ全加算器

負の数を加算するように、全加算回路を設計できます。次のロジックを使用して、合計とキャリーを計算します。

si =ai⊕bi⊕ci+⊕ci− {\ displaystyle s_ {i} = a_ {i} \ oplus b_ {i} \ oplus c_ {i} ^ {+} \ oplus c_ {i} ^ {-}} ci + 1 + =ai¯bi¯ci+¯ci-{\ displaystyle c_ {i + 1} ^ {+} = {\ overline {a_ {i}}} {\ overline {b_ {i}}} {\ overline { c_ {i} ^ {+}}} c_ {i} ^ {-}} ci + 1− = aibici−¯ +（ai⊕bi）ci + ci−¯ {\ displaystyle c_ {i + 1} ^ {- } = a_ {i} b_ {i} {\ overline {c_ {i} ^ {-}}} +（a_ {i} \ oplus b_ {i}）c_ {i} ^ {+} {\ overline {c_ {i} ^ {-}}}}負数の増分

負数のインクリメントは、次の式を使用して実行できます。

2x⊕（（2x⊕x）+1）{\ displaystyle 2x \ oplus（（2x \ oplus x）+1）}

減算

減算するには、2番目の数値の各ビットに-1を乗算し、上記と同じ表を使用して数値を加算します。

例として、1101001-2（1-8-32 + 64 = 25）-1110100-2（4 + 16-32 + 64 = 52）を計算するには、

キャリー：0 1 -1 1 0 0 0最初の数：1 1 0 1 0 0 1 2番目の数：-1 -1 -1 0 -1 0 0 + --------------- -----数：0 1 -2 2 -1 0 1ビット（結果）：0 1 0 0 1 0 1キャリー：0 0 1 -1 1 0 0

そのため、結果は100101-2（1 + 4 -32 = -27）です。

単項否定-xは 、ゼロからのバイナリ減算0- xとして計算できます。

乗算と除算

左にシフトすると-2で乗算され、右にシフトすると-2で除算されます。

乗算するには、通常の10進数または2進数のように乗算しますが、数字を追加するときにキャリーの追加にネガバイナリルールを使用します。

最初の番号：1 1 1 0 1 1 0 2番目の番号：1 0 1 1 0 1 1×----------------------------- -------- 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 + ------ -------------------------------キャリー：0 −1 0 −1 −1 −1 −1 −1 -1 0 −1 0 0番号：1 0 2 1 2 2 2 3 2 0 2 1 0ビット（結果）：1 0 0 1 0 0 0 1 0 0 0 1 0キャリー：0 -1 0 −1 −1 −1 −1 − 1 0 -1 0 0

各列で、 キャリーをnumberに追加し、合計を-2で除算して、新しいキャリーを取得し、結果のビットを剰余として取得します。

負数の比較

通常の符号なしバイナリコンパレータをわずかに調整することにより、ネガバイナリ数を比較することができます。数字A {\ displaystyle A}とB {\ displaystyle B}を比較するとき、両方の数字の奇数位置の各ビットを反転します。この後、標準の符号なしコンパレーターを使用して、A {\ displaystyle A}とB {\ displaystyle B}を比較します。

小数

基数-r表現は、基数ポイントを超えて運ばれ、非整数の表現が可能になります。

正のベースシステムと同様に、終端表現は分母がベースのべき乗である分数に対応します。同じ理由で、繰り返し表現は他の理論的根拠に対応します。

一意でない表現

負の基数システムで整数と終端分数が一意でない表現（たとえば、10進数で0.999…= 1）を持つ正の基数システムとは異なり、整数は1つの表現のみを持ちます。ただし、非一意の表現を使用した論理的根拠が存在します。数字{0、1、…、 t }の場合、t：= r-1 = -b-1 {\ displaystyle \ mathbf {t}：= r \！-\！\！1 = -b \！-\ ！\！1}最大桁

T：=0.01¯b= ∑i = 1∞b−2i = 1b2−1 = 1r2−1 {\ displaystyle T：= 0。{\ overline {01}} _ {b} = \ sum _ {i = 1 } ^ {\ infty} b ^ {-2i} = {\ frac {1} {b ^ {2} -1}} = {\ frac {1} {r ^ {2} -1}}}

我々は持っています

0.0t¯b= tT = r−1r2−1 = 1r + 1 {\ displaystyle 0。{\ overline {0 \ mathbf {t}}} _ {b} = \ mathbf {t} T = {\ frac {r \！-\！\！1} {r ^ {2} -1}} = {\ frac {1} {r + 1}}}および1.t0¯b= 1 + tbT =（r2−1 ）+（r−1）br2−1 = 1r + 1。{\ displaystyle 1。{\ overline {\ mathbf {t} 0}} _ {b} = 1 + \ mathbf {t} bT = {\ frac { （r ^ {2} -1）+（r \！-\！\！1）b} {r ^ {2} -1}} = {\ frac {1} {r + 1}}。}

そのため、すべての数字1r + 1 + z {\ displaystyle {\ frac {1} {r + 1}} + z}に終了分数z∈ZrZ{\ displaystyle z \ in \ mathbb {Z} r ^ {\ mathbb { Z}}}には、2つの異なる表現が追加されています。

たとえば、ネガタナリ、つまりb = -3 {\ displaystyle b = -3}およびt = 2 {\ displaystyle \ mathbf {t} = 2}には、

1.02¯（−3）= 54 =2.20¯（−3）{\ displaystyle 1。{\ overline {02}} _ {（-3）} = {\ frac {5} {4}} = 2。{\ {20}} _ {（-3）}}に上線を引きます。

このような一意でない表現は、それぞれ整数部分0と1を持つ可能な最大と最小の表現を検討し、それらが等しいことに注意することで見つけることができます。（実際、これはすべての整数ベースシステムで機能します。）このように一意に表現できない合理性は、形式のものです。

z（r + 1）+ 1bi（r + 1）{\ displaystyle {\ frac {z（r + 1）+1} {b ^ {i}（r + 1）}}}

with z、i∈Z。{\ displaystyle z、i \ in \ mathbb {Z}。}

架空の基地

負の基数を使用すると、明示的な負符号なしで負の数を表現できるように、虚数の基数を使用するとガウス整数を表現できます。ドナルド・クヌースは、1955年に4乗の虚数ベース（ベース2i）を提案しました。