Ikisinin tamamlayıcısı - Two's complement

İkinin tümleyeni , ikili sayılar üzerinde matematiksel bir işlemdir ve bir sayı tabanı tamamlayıcısının bir örneğidir . Hesaplamada imzalı sayı gösterimi yöntemi olarak kullanılır .

Bir ikinin tümleyici K bitlik sayı olan olarak tanımlanır tamamlayıcı göre 2 ^N ; bir sayının ikinin tümleyeni ile toplamı 2 ^N'dir . Örneğin, üç bitlik 010 ₂ sayısı için, ikisinin tümleyeni 110 _2'dir , çünkü 010 ₂ + 110 ₂ = 1000 ₂ = 8 ₁₀ , 2 ^3'e eşittir . İkisinin tamamlayıcısı, bitlerin ters çevrilmesi ve bir eklenmesiyle hesaplanır.

İki'nin tamamlayıcısı, bilgisayarlarda işaretli tam sayıları ve daha genel olarak sabit nokta ikili değerlerini temsil etmenin en yaygın yöntemidir . Bu şemada, ikili sayı 010 ₂ işaretli tamsayı 2 _10'u kodluyorsa, bunun ikisinin tümleyeni 110 ₂ tersini kodlar: −2 ₁₀ . Başka bir deyişle, çoğu tamsayının işareti (biri hariç tümü), bu şemada ikili gösteriminin ikisinin tümleyeni alınarak tersine çevrilebilir. Sağdaki tablolar bu özelliği göstermektedir.

(İşaretli sayıları temsil diğer sistemlere kıyasla , örneğin olanlar tamamlayıcı ), ikiye tümleme temel aritmetik işlemler avantajına sahiptir ekleme , çıkarma ve çarpma sürece girişler olarak temsil edilir (işaretsiz ikili sayılar için özdeştir çıktıyla aynı sayıda bit ve bu bitlerin ötesindeki herhangi bir taşma sonuçtan atılır). Bu özellik, özellikle yüksek hassasiyetli aritmetik için sistemin uygulanmasını kolaylaştırır. Birlerin tümleyen sistemlerinden farklı olarak, ikinin tümleyeninin eksi sıfır temsili yoktur ve bu nedenle onunla ilişkili zorluklardan etkilenmez.

Uygun bir şekilde, bir sayının ikisinin tümleyenini bulmanın başka bir yolu, onun birlere tümleyenini alıp bir eklemektir: bir sayının ve onun birlerin tümleyeninin toplamı '1' bit veya 2 ^N − 1'dir ; ve tanım gereği, bir dizi ve toplamı ikinin tamamlayıcı olan 2 ^K .

Tarih

Tamamlayıcı yöntemi uzun ondalık içinde çıkarma gerçekleştirmek için kullanılan olmuştu ekleyerek makineleri ve mekanik hesap makineleri . John von Neumann , elektronik depolanmış programlı bir dijital bilgisayar için EDVAC önerisi üzerine 1945 İlk Rapor Taslağı'nda ikinin tümleyen ikili gösteriminin kullanılmasını önerdi . İlk Taslak'tan esinlenen 1949 EDSAC , ikili sayıların ikinin tümleyen gösterimini kullandı.

CDC 6600 , LINC , PDP-1 ve UNIVAC 1107 dahil olmak üzere birçok eski bilgisayar, birlerin tamamlayıcı gösterimini kullanır; UNIVAC 1107'nin torunları olan UNIVAC 1100/2200 serisi bunu yapmaya devam etti. IBM 700/7000 serisi bilimsel makineler ikinin tamamlayıcısı olan İndeks kaydına hariç, işaret / büyüklüğü notasyonu kullanın. İlk ticari ikilinin tamamlayıcı bilgisayarları arasında Digital Equipment Corporation PDP-5 ve 1963 PDP-6 bulunur . Sistemi / 360 tarafından 1964 yılında tanıtılan, IBM , daha sonra bilgisayar endüstrisinde baskın bir oyuncu, iki bilgisayar endüstrisinde en yaygın olarak kullanılan ikili gösterimini tamamlar yaptı. İlk mini bilgisayar, 1965'te tanıtılan PDP-8 , 1969 Data General Nova , 1970 PDP-11 ve hemen hemen tüm sonraki mini bilgisayarlar ve mikrobilgisayarlarda olduğu gibi ikinin tamamlayıcı aritmetiğini kullanır .

İkinin tümleyen gösteriminden dönüştürme

İkinin tümleyen sayı sistemi, pozitif ve negatif sayıları ikili sayı gösteriminde kodlar. Her bir bitin ağırlığı, ağırlığı ikinin kuvvetinin negatifi olan en önemli bit dışında ikinin kuvvetidir.

Değeri  ağırlık bir bölgesinin K bitlik bir tamsayı , aşağıdaki formül ile verilir: ${\displaystyle a_{N-1}a_{N-2}\dots a_{0}}$

${\displaystyle w=-a_{N-1}2^{N-1}+\sum _{i=0}^{N-2}a_{i}2^{i}}$

En anlamlı bit, sayının işaretini belirler ve bazen işaret biti olarak adlandırılır . İşaret ve büyüklük gösteriminin aksine , işaret biti ayrıca yukarıda gösterilen −(2 ^{N  − 1} ) ağırlığına sahiptir . N bit kullanarak , −(2 ^{N  − 1} ) ile 2 ^{N  − 1} − 1 arasındaki tüm tamsayılar temsil edilebilir.

İkinin tümleyen gösterimine dönüştürme

İkinin tümleyen gösteriminde, negatif olmayan bir sayı, olağan ikili gösterimi ile temsil edilir ; bu durumda, en anlamlı bit 0'dır. Bununla birlikte, temsil edilen sayıların aralığı, işaretsiz ikili sayılarla aynı değildir. Örneğin, 8 bitlik işaretsiz bir sayı, 0 ila 255 (111111111) arasındaki değerleri temsil edebilir. Bununla birlikte, ikinin tümleyeni 8 bitlik bir sayı yalnızca 0 ila 127 (01111111) arasındaki pozitif tam sayıları temsil edebilir, çünkü '1' olarak en anlamlı biti olan bit kombinasyonlarının geri kalanı -1 ila -128 arasındaki negatif tam sayıları temsil eder.

İkisinin tümleyen işlemi toplamalı ters işlemdir, bu nedenle negatif sayılar mutlak değerin ikisinin tümleyeni ile temsil edilir .

Bunların tamamlayıcısından

Negatif bir ikili sayının ikisinin tümleyenini elde etmek için bitler ters çevrilir veya bit düzeyinde DEĞİL işlemi kullanılarak "çevrilir" ; 1 değeri daha sonra, ikisinin tümleyeni 0 alınırken meydana gelen taşma göz ardı edilerek elde edilen değere eklenir.

Örneğin, 1 bayt (=8 bit) kullanılarak, ondalık sayı 5 şu şekilde temsil edilir:

0000 0101 ₂

En anlamlı bit 0'dır, bu nedenle model negatif olmayan bir değeri temsil eder. İkinin tamamlayıcı notasyonunda -5'e dönüştürmek için önce bitler ters çevrilir, yani: 0 1 olur ve 1 0 olur:

1111 1010 ₂

Bu noktada temsil, -5 ondalık değerinin birlerin tümleyenidir . İkisinin tümleyenini elde etmek için sonuca 1 eklenir ve aşağıdakileri verir:

1111 1011 ₂

Sonuç, ikinin tamamlayıcısı biçiminde -5 ondalık değerini temsil eden işaretli bir ikili sayıdır. En anlamlı bit 1'dir, dolayısıyla temsil edilen değer negatiftir.

Negatif bir sayının ikisinin tümleyeni, özel bir durum dışında, karşılık gelen pozitif değerdir. Örneğin, -5 (yukarıda) bitlerini ters çevirmek şunları verir:

0000 0100 ₂

Ve bir tane eklemek son değeri verir:

0000 0101 ₂

Benzer şekilde, ikisinin sıfıra tümleyeni sıfırdır: ters çevirme tüm birleri verir ve bir eklemek, olanları sıfıra döndürür (çünkü taşma göz ardı edilir).

Temsil edilebilen en negatif sayının ikisinin tümleyeni (örneğin, en anlamlı bit olarak bir ve diğer tüm bitler sıfır) kendisidir. Bu nedenle, ikinin tümleyeninin olumsuzlama vermediği bir 'fazladan' negatif sayı vardır, aşağıdaki § En negatif sayıya bakın.

2 ^N'den çıkarma

Bir sayının toplamı ve onun birlerinin tümleyeni , (işaretsiz bir ikili sayı olarak okuma) 2 ^N − 1 olan tüm 1 biti olan bir N- bitlik kelimedir . Daha sonra, ikisinin tümleyenine bir sayı eklenmesi, N en düşük bitin 0'a ve taşıma bitinin 1'e ayarlanmasıyla sonuçlanır ; burada ikincisinin ağırlığı (işaretsiz bir ikili sayı olarak okunur) 2 ^{N olur} . Bu nedenle, işaretsiz ikili aritmetikte, bir pozitif x'in ikinin tümleyen negatif sayısının x * değeri, x * = 2 ^N − x eşitliğini sağlar .

Örneğin, −5'in 4 bitlik temsilini bulmak için (abonelikler temsilin tabanını belirtir ):

x = 5 ₁₀ öyleyse x = 0101 ₂

Dolayısıyla, N = 4 ile :

x * = 2 ^N − x = 2 ⁴ − 5 ₁₀ = 16 ₁₀ - 5 ₁₀ = 10000 ₂ − 0101 ₂ = 1011 ₂

Hesaplama tamamen 10 tabanında yapılabilir ve sonunda 2 tabanına dönüştürülür:

x * = 2 ^N − x = 2 ⁴ − 5 ₁₀ = 11 ₁₀ = 1011 ₂

LSB'den MSB'ye doğru çalışma

Bir ikili sayıyı ikinin tümleyenine manuel olarak dönüştürmek için bir kısayol , en az anlamlı bitten (LSB) başlamak ve ilk 1'e ulaşılana kadar LSB'den en anlamlı bite (MSB) doğru çalışarak tüm sıfırları kopyalamaktır; sonra 1'i kopyalayın ve kalan tüm bitleri çevirin (ilk sayı işaret ve büyüklük temsilindeyse MSB'yi 1 olarak bırakın). Bu kısayol, bir kişinin önce birlerin tümleyenini oluşturmadan bir sayıyı ikinin tümleyenine dönüştürmesine izin verir. Örneğin: ikinin tümleyen gösteriminde, "0011 1100"ün olumsuzlaması "1100 0 100 " olur, burada altı çizili basamaklar kopyalama işlemiyle değişmemiştir (geri kalan basamaklar ters çevrilirken).

Bilgisayar devrelerinde bu yöntem, "tamamla ve bir tane ekle" yönteminden daha hızlı değildir; her iki yöntem de mantık değişikliklerini yayarak sağdan sola sırayla çalışmayı gerektirir. Birini tamamlama ve ekleme yöntemi, standart bir ileriye dönük toplayıcı devresi ile hızlandırılabilir ; MSB yöntemine yönelik LSB, benzer bir mantık dönüşümü ile hızlandırılabilir.

İşaret uzantısı

Belirli sayıda bit içeren ikinin tamamlayıcısı sayısını daha fazla bit içeren bir sayıya dönüştürürken (örneğin, 1 baytlık bir değişkenden 2 baytlık bir değişkene kopyalarken), en anlamlı bit tüm ekstra bitlerde tekrarlanmalıdır. . Bazı işlemciler bunu tek bir komutta yapar; diğer işlemcilerde, ilgili bitleri veya baytları ayarlamak için bir koşul ve ardından kod kullanılmalıdır.

Benzer şekilde, ikinin tümleyen sayısı sağa kaydırıldığında, büyüklük ve işaret bilgisini içeren en anlamlı bit korunmalıdır. Bununla birlikte, sola kaydırıldığında, bir 0 içeri kaydırılır. Bu kurallar, sola kaydırmaların sayıyı ikiyle çarptığı ve sağa kaydırmaların sayıyı ikiye böldüğü ortak anlamını korur.

Hassasiyeti hem kaydırmak hem de ikiye katlamak bazı çarpma algoritmaları için önemlidir. Toplama ve çıkarmadan farklı olarak, genişlik genişletme ve sağa kaydırmanın işaretli ve işaretsiz sayılar için farklı şekilde yapıldığını unutmayın.

En negatif sayı

Sadece bir istisna dışında, ikinin tümleyen gösteriminde herhangi bir sayıdan başlayarak, tüm bitler çevrilir ve 1 eklenirse, o sayının negatifinin ikinin tümleyici gösterimi elde edilir. Artı 12 eksi 12 olur, artı 5 eksi 5 olur, sıfır sıfır olur(+taşma), vb.

Aralıktaki minimum sayının ikisinin tümleyenini almak, sayıyı olumsuzlamak için istenen etkiye sahip olmayacaktır. Örneğin, 8 bitlik bir sistemde ikisinin −128'in tümleyeni −128'dir. -128'in olumsuzlanmasından beklenen sonuç +128 olmasına rağmen, 8 bit iki tümleyen sistemiyle +128'in temsili yoktur ve bu nedenle aslında olumsuzlamayı temsil etmek imkansızdır. İkisinin tümleyeninin aynı sayı olması bir taşma koşulu olarak algılanır, çünkü en anlamlı bitte bir taşıma vardır, ancak bu bitin dışında değildir.

Bu fenomen temelde ikili sayıların matematiği ile ilgilidir, ikinin tümleyeni olarak gösterimin ayrıntılarıyla değil. Matematiksel olarak, bu, 0'ın negatifinin tekrar 0 olduğu gerçeğini tamamlayıcıdır. Belirli bir k bit sayısı için çift sayıda ikili sayı vardır 2 ^k , negatif almak, üzerinde bir grup eylemidir (2. dereceden grubun) ikili sayılar ve sıfırın yörüngesi 1. sıraya sahip olduğundan, yörüngelerin sıralarının kümenin sırasına eklenmesi için en az bir diğer sayının yörüngesi 1 olmalıdır. Bu nedenle, (resmi olarak, yörünge sabitleyici teoremi tarafından) negatifleri alırken başka bir sayı değişmez olmalıdır . Geometrik olarak, k- bit ikili sayıları bir daire (veya düzgün bir 2 ^k- gon) olarak görselleştirilebilen döngüsel grup olarak görebilir ve negatifleri almak, sıra bölme 2'nin öğelerini sabitleyen bir yansımadır: 0 ve zıt nokta veya görsel olarak başucu ve nadir. ${\displaystyle \mathbb {Z} /2^{k}}$

En negatif sayının varlığı, sonucun beklenmeyen bir işarete sahip olduğu beklenmeyen programlama hatalarına veya beklenmeyen bir taşma istisnasına veya tamamen garip davranışlara yol açabilir. Örneğin,

• tekli olumsuzlama operatörü sıfırdan farklı bir sayının işaretini değiştiremez. örneğin, −(−128) → −128.

• mutlak değer uygulaması negatif bir sayı döndürebilir. örneğin, abs(−128) → −128.

• Benzer şekilde, -1 ile çarpma beklendiği gibi çalışmayabilir. örneğin, (−128) × (−1) → −128.

• −1'e bölme bir istisnaya neden olabilir (0'a bölmenin neden olduğu gibi). Kalanı (veya moduloyu) -1 ile hesaplamak bile bu istisnayı tetikleyebilir. örneğin, (−128) ÷ (−1) → kilitlenme, (−128) % (−1) → kilitlenme.

In C ve C ++ programlama dilleri, yukarıdaki davranışlar vardır tanımsız ve sadece onlar garip sonuçlar döndürebilir, ancak derleyici programcı tanımlanmamış hesaplamalar asla sağlamıştır varsayalım ve varsayımından çıkarımlar yapmak serbesttir. Bu, bir dizi optimizasyonu mümkün kılar, ancak aynı zamanda bu tür tanımsız programlarda bir dizi garip hataya da yol açar.

İkinin tümleyenindeki en negatif sayı, tek istisna olduğu için bazen "garip sayı" olarak adlandırılır. Sayı bir istisna olmasına rağmen, normal ikinin tümleyen sistemlerinde geçerli bir sayıdır. Tüm aritmetik işlemler onunla hem işlenen hem de (taşma olmadıkça) sonuç olarak çalışır.

neden işe yarıyor

Tüm olası N -bit değerlerinin bir kümesi verildiğinde , alt (ikili değere göre) yarıyı 0 ile (2 ^{N  − 1} − 1) dahil tam sayılar ve üst yarıyı −2 ^{N  − 1} olarak atayabiliriz. -1 dahil. Üst yarı (yine ikili değere göre) -2 ^{N  − 1} ile -1 arasındaki negatif tam sayıları temsil etmek için kullanılabilir, çünkü 2 ^N modulo eklendiğinde bunlar bu negatif tamsayılarla aynı şekilde davranırlar. Yani i + j mod 2 ^N = i + ( j + 2 ^N ) mod 2 ^N olduğu için {  j + k  2 ^N | k bir tamsayıdır }  j yerine kullanılabilir  .

Örneğin, sekiz bit ile, işaretsiz baytlar 0 ila 255 arasındadır. Üst yarıdan (128 ila 255) 256 çıkarıldığında, −128 ila −1 işaretli baytlar elde edilir.

İkinin komplementine ilişki olduğunu belirterek gerçekleştirilmektedir 256 = 255 + 1 , ve - (255 x ) olduğu olanlar tamamlayıcı bir  x .

Örnek

Bu alt bölümde, ondalık sayıların sonuna ondalık nokta "." eklenir.

Örneğin, 8 bitlik bir sayı yalnızca -128 arasındaki her tamsayıyı temsil edebilir. 127'ye kadar, dahil, (2 ^{8 − 1} = 128.) . -95. modulo 256. , 161'e eşdeğerdir.

-95. + 256.

= -95. + 255. + 1

= 255. - 95. + 1

= 160. + 1.

= 161.

   1111 1111 255.
 - 0101 1111 - 95.
 =========== =====
   1010 0000 (birlerin tamamlayıcısı) 160.
 + 1 + 1
 =========== =====
   1010 0001 (ikinin tümleyeni) 161.

Temel olarak, sistem geriye doğru sayarak ve etrafına sararak negatif tam sayıları temsil eder . Pozitif ve negatif sayılar arasındaki sınır isteğe bağlıdır, ancak geleneksel olarak tüm negatif sayıların en soldaki biti ( en anlamlı bit ) birdir. Bu nedenle, en pozitif 4 bitlik sayı 0111 (7.) ve en negatif 1000 (-8.)'dir. İşaret biti olarak en soldaki bitin kullanılması nedeniyle, en negatif sayının (|-8.| = 8.) mutlak değeri temsil edilemeyecek kadar büyüktür. İkinin tümleyen sayısını reddetmek basittir: Tüm bitleri ters çevirin ve sonuca bir tane ekleyin. Örneğin, 1111'i olumsuzlayarak 0000 + 1 = 1 elde ederiz . Bu nedenle ikili olarak 1111, ondalık olarak -1'i temsil etmelidir.

Sistem, bilgisayar donanımında aritmetiğin uygulanmasını basitleştirmede faydalıdır. İlk başta 0011 (3.)'e 1111 (-1.) eklemek, 10010'un yanlış cevabını veriyor gibi görünüyor. Ancak donanım, 0010'un (2.) doğru cevabını vermek için en soldaki biti görmezden gelebilir. 0100 ve 0100 toplama gibi işlemleri yakalamak için taşma kontrolleri hala mevcut olmalıdır.

Bu nedenle sistem, bir çıkarma devresi veya bir sayının işaretini algılayan bir devre olmaksızın negatif işlenenlerin eklenmesine izin verir. Ayrıca, bu toplama devresi, yalnızca ek bir döngü veya kendi toplayıcı devresi gerektiren bir sayının ikisinin tümleyenini alarak (aşağıya bakın) çıkarma işlemi de yapabilir. Bunu gerçekleştirmek için devre yalnızca, fazladan en soldaki 1 biti varmış gibi çalışır.

Aritmetik işlemler

Ek

İkili tümleyen sayıların eklenmesi, işlenenlerin zıt işaretleri olsa bile özel bir işlem gerektirmez: sonucun işareti otomatik olarak belirlenir. Örneğin, 15 ve -5 ekleyerek:

  11111 111 (taşıma)
   0000 1111 (15)
 + 1111 1011 (−5)
 ===========
   0000 1010 (10)

Veya 5 − 15 = 5 + (−15) hesaplaması:

          1 (taşıma)
   0000 0101 (5)
 + 1111 0001 (−15)
 ===========
   1111 0110 (-10)

Bu işlem, 8 bit kesinlik ile sınırlandırılmasına bağlıdır; (var olmayan) 9. en anlamlı bit'e yapılan taşıma yok sayılır ve bu da 10 _10'un aritmetik olarak doğru sonucunu verir .

Taşıma satırının son iki biti (sağdan sola okuma) hayati bilgiler içerir: hesaplamanın aritmetik bir taşma ile sonuçlanıp sonuçlanmadığı , ikili sistemin temsil etmesi için çok büyük bir sayı (bu durumda 8 bitten büyük). Bu son iki bit birbirinden farklı olduğunda bir taşma durumu mevcuttur. Yukarıda belirtildiği gibi, sayının işareti sonucun MSB'sinde kodlanmıştır.

Diğer bir deyişle, sol iki taşıma biti (bu örneklerde en üst satırın en solundakiler) hem 1'ler hem de her ikisi de 0 ise, sonuç geçerlidir; sol iki taşıma biti "1 0" veya "0 1" ise, bir işaret taşması meydana gelmiştir. Uygun olarak, bu iki bit üzerindeki bir XOR işlemi, bir taşma koşulunun mevcut olup olmadığını hızlı bir şekilde belirleyebilir. Örnek olarak, 7 ve 3'ün imzalı 4 bitlik eklemesini düşünün:

  0111 (taşıma)
   0111 (7)
 + 0011 (3)
 ======
   1010 (−6) geçersiz!

Bu durumda, en soldaki iki (MSB) taşıma biti "01"dir; bu, ikinin tamamlayıcısı ekleme taşması olduğu anlamına gelir. Yani, 1010 ₂ = 10 ₁₀ , izin verilen -8 ila 7 aralığının dışındadır. İşaretsiz tamsayı olarak ele alınırsa sonuç doğru olur.

Genel olarak, herhangi iki N - bitlik sayı, taşma olmadan , önce her ikisini de N  + 1 bit'e işaret uzatarak ve sonra yukarıdaki gibi ekleyerek eklenebilir. N  + 1 bit Sonuç, her türlü olası bir miktar (temsil etmek yeterince büyük olan , N = 5 aralığında değerleri temsil edebilir -16 15'e ikinin tümleyici) taşma asla oluşmayacak olan çok. Daha sonra, istenirse, değeri korurken sonucu N bit'e geri 'kesmek' mümkündür, ancak ve ancak atılan bit, tutulan sonuç bitlerinin uygun bir işaret uzantısıysa. Bu, taşıma bitlerini karşılaştırma yöntemine eşdeğer olan, ancak eklemenin iç kısımlarına erişim gerektirmediğinden bazı durumlarda uygulanması daha kolay olabilen başka bir taşma algılama yöntemi sağlar.

Çıkarma

Bilgisayarlar, çıkarma işlemini gerçekleştirmek için genellikle tamamlayıcı yöntemini kullanır . Çıkarma için tamamlayıcıların kullanılması, negatif sayıları temsil etmek için tamamlayıcıların kullanılmasıyla yakından ilişkilidir, çünkü kombinasyon tüm işlenenlerin ve sonuçların işaretlerine izin verir; doğrudan çıkarma, ikinin tümleyen sayılarıyla da çalışır. Toplama gibi, ikiye tümleyeni kullanmanın avantajı, toplamanın mı yoksa çıkarmanın mı gerekli olduğunu belirlemek için işlenenlerin işaretlerini incelemenin ortadan kaldırılmasıdır. Örneğin, 15'ten -5'i çıkarmak gerçekten 5'i 15'e eklemektir, ancak bu, ikisinin tamamlayıcı temsili tarafından gizlenmiştir:

  11110 000 (ödünç alma)
   0000 1111 (15)
 − 1111 1011 (−5)
 ===========
   0001 0100 (20)

Taşma, ödünç alınanların en soldaki (en önemli) iki biti incelenerek, toplama işlemiyle aynı şekilde saptanır; farklıysa taşma meydana gelmiştir.

Başka bir örnek, sonucun negatif olduğu bir çıkarma işlemidir: 15 − 35 = −20:

  11100 000 (ödünç alma)
   0000 1111 (15)
 − 0010 0011 (35)
 ===========
   1110 1100 (−20)

Eklemeye gelince, çıkarma işleminde taşma, her iki girişi de fazladan bir bit ile ilk işaret uzatarak önlenebilir (veya işlemden sonra tespit edilebilir).

Çarpma işlemi

İki N bitlik sayının çarpımı, tüm olası değerleri içermesi için 2 N bit gerektirir .

İkinin tümleyenini kullanan iki işlenenin kesinliği çarpmadan önce ikiye katlanırsa, doğrudan çarpma (bu kesinliğin ötesindeki fazla bitleri atarak) doğru sonucu sağlayacaktır. Örneğin, 6 × (−5) = -30 alın . İlk olarak, hassasiyet dört bitten sekiz bit'e genişletilir. Ardından sayılar çarpılır, sekizinci bitin ötesindeki bitler atılır (" x " ile gösterildiği gibi ):

     00000110 (6)
 * 11111011 (−5)
 ============
          110
         1100
        00000
       110000
      1100000
     11000000
    x10000000
 + xx00000000
 ============
   xx11100010

Bu çok verimsizdir; Kesinliği önceden ikiye katlayarak, tüm eklemeler çift duyarlıklı olmalı ve bilgisayarlarda fiilen uygulanan daha verimli algoritmalardan en az iki kat daha fazla kısmi ürüne ihtiyaç duyulmalıdır. Bazı çarpma algoritmaları, özellikle Booth'un çarpma algoritması olmak üzere, ikinin tümleyeni için tasarlanmıştır . İşaret büyüklüğündeki sayıları çarpma yöntemleri, uyarlama olmadan ikinin tümleyen sayılarıyla çalışmaz. Çarpan (çarpıyı oluşturmak için tekrar tekrar eklenen) negatif olduğunda genellikle bir sorun yoktur; sorun, çarpan negatif olduğunda ürünün ilk bitlerini doğru şekilde ayarlamaktır. Algoritmaları, ikinin tümleyen sayılarını işlemek üzere uyarlamak için iki yöntem yaygındır:

• İlk önce çarpanın negatif olup olmadığını kontrol edin. Eğer öyleyse, çarpmadan önce her iki işleneni de olumsuzlayın ( yani , ikisinin tümleyenini alın). Çarpan daha sonra pozitif olacak, böylece algoritma çalışacak. Her iki işlenen de olumsuzlandığından, sonuç yine de doğru işarete sahip olacaktır.
• Diğer kısmi ürünler gibi eklemek yerine, MSB'den (sözde işaret biti) elde edilen kısmi ürünü çıkarın. Bu yöntem, sağa kaydırma eylemleri sırasında korunan, çarpanın işaret bitinin bir konum genişletilmesini gerektirir.

İkinci yönteme örnek olarak çarpma için ortak ekleme ve kaydırma algoritmasını alın. Kalem ve kağıtta olduğu gibi kısmi ürünleri sola kaydırmak yerine, biriken ürün sağa kaydırılır, sonunda ürünün en az önemli yarısını tutacak ikinci bir kayıt içine alınır. En az anlamlı bitler hesaplandıktan sonra değiştirilmediği için, eklemeler tek kesinlikli olabilir ve sonuçta ürünün en önemli yarısını tutacak olan kayıtta birikir. Aşağıdaki örnekte, yine 6 ile -5 çarpıldığında, iki kayıt ve genişletilmiş işaret biti "|" ile ayrılır:

  0 0110 (6) (genişletilmiş işaret bitli çoğul)
  × 1011 (−5) (çarpan)
  =|====|====
  0|0110|0000 (ilk kısmi çarpım (en sağdaki bit 1))
  0|0011|0000 (sağa kaydır, genişletilmiş işaret bitini koruyarak)
  0|1001|0000 (ikinci kısmi çarpımı ekle (sonraki bit 1))
  0|0100|1000 (sağa kaydır, genişletilmiş işaret bitini koruyarak)
  0|0100|1000 (üçüncü kısmi ürün ekleyin: 0 yani değişiklik yok)
  0|0010|0100 (sağa kaydır, uzatılmış işaret bitini koruyarak)
  1|1100|0100 (işaret bitinden olduğu için son kısmi çarpımı çıkar)
  1|1110|0010 (sağa kaydır, uzatılmış işaret bitini koruyarak)
   |1110|0010 (genişletilmiş işaret bitini atın, son yanıtı verin, -30)

Karşılaştırma (sıralama)

Karşılaştırma genellikle, bilgisayarın durum kaydındaki bayrakların kontrol edildiği, ancak ana sonucun göz ardı edildiği yapay bir çıkarma ile uygulanır . Sıfır bayrağı iki değeri eşit karşılaştırıldığında gösterir. İşaret ve taşma bayraklarının dışlayıcı-veya değeri 1 ise, çıkarma sonucu sıfırdan küçük, aksi takdirde sonuç sıfır veya daha büyüktü. Bu kontroller genellikle bilgisayarlarda koşullu şube talimatlarında uygulanır.

İşaretsiz ikili sayılar, 0 bit değerinin 1 bit değerinden küçük olarak tanımlandığı basit bir sözlüksel sıralama ile sıralanabilir. İkinin tümleyen değerleri için, en anlamlı bitin anlamı tersine çevrilir (yani 1, 0'dan küçüktür).

Aşağıdaki algoritma ( n -bit ikinin tümleyen mimarisi için), A < B ise sonuç kaydı R'yi -1'e, A > B ise +1'e ve A ve B eşitse 0'a ayarlar:

// reversed comparison of the sign bit

if A(n-1) == 0 and B(n-1) == 1 then
    return +1
else if A(n-1) == 1 and B(n-1) == 0 then
    return -1
end
 
// comparison of remaining bits

for i = n-2...0 do
    if A(i) == 0 and B(i) == 1 then
        return -1
    else if A(i) == 1 and B(i) == 0 then
        return +1 
    end
end
 
return 0

İkinin tümleyeni ve 2-adic sayılar

1972'de MIT AI Laboratuvarı tarafından yayınlanan klasik bir HAKMEM'de Bill Gosper, bir makinenin iç temsilinin ikinin tamamlayıcısı olup olmadığının, ikinin ardışık güçlerinin toplanarak belirlenebileceğini kaydetti. Bir fantezi uçuşunda, bunu cebirsel olarak yapmanın sonucunun "cebir, ikinin tümleyeni olan bir makinede (evren) çalıştırıldığını" belirtti.

Gosper'ın nihai sonucu mutlaka ciddiye alınmak zorunda değildir ve matematiksel bir şakaya benzer . Kritik adım "...110 = ...111 − 1", yani "2 X = X  − 1" ve dolayısıyla X  = ...111 = -1'dir. Bu, temel aritmetikte sonlu yer-değer kavramlarının bir uzantısını gerektiren, sonsuz bir 1'ler dizisinin bir sayı olarak kabul edildiği bir yöntemi varsayar. Tipik bir 2- adic sayı olarak, tüm tamsayılar için ikinin tümleyen gösteriminin bir parçası olarak veya hatta 1 + 2 + 4 + 8 + ıraksak gerçek sayılar serisi için tanımlanan genelleştirilmiş toplamlardan biri olarak anlamlıdır. · . Sonsuz (2'nin pozitif güçlerine uzanan) bit dizileriyle çalışmak üzere idealleştirilen dijital aritmetik devreler, ikinin tümleyen gösterimi ile uyumlu 2-adic toplama ve çarpma üretir. 2-adic metrikte ikili aritmetik ve bitsel işlemlerin sürekliliği , kriptografide de bazı kullanımlara sahiptir.

kesir dönüştürme

.0101 gibi kesirli bir sayıyı dönüştürmek için, normal bir dönüştürmede olduğu gibi sağdan sola 1'leri ondalık sayıya dönüştürmek gerekir. Bu örnekte 0101, ondalık olarak 5'e eşittir. Kayan noktadan sonraki her rakam, paydanın 2'nin çarpanı olduğu bir kesri temsil eder. Yani, birincisi 1/2, ikincisi 1/4 ve bu böyle devam eder. Ondalık değeri yukarıda belirtildiği gibi hesapladıktan sonra, sadece LSB'nin paydası (LSB = sağdan başlayarak) kullanılır. Bu dönüşümün nihai sonucu 5/16'dır.

Örneğin, bu yöntemin çalışması için .0110 değişken değerine sahip olmak, sağdan son 0'ı düşünmemelidir. Bu nedenle, 0110 için ondalık değeri hesaplamak yerine, ondalık olarak 3 olan 011 değerini hesaplıyoruz (sonda 0 bırakarak, sonuç, payda 2 ⁴  = 16 ile birlikte 6 olurdu , bu da 3/8). Payda 8'dir ve 3/8 ise nihai sonucu verir.

Ayrıca bakınız

• İkinin tamamlayıcı temsillerinde geri yükleme ve geri yükleme olmayan bölümü içeren bölme algoritması
• Ofset ikili
• p-adic numarası
• Mekanik hesap makinelerinde kullanılan tümler yöntemi, diğer sayı tabanlarına genelleme

Referanslar

daha fazla okuma

• Two's Complement Açıklama, (Thomas Finley, 2000)

• Koren, İsrail (2002). Bilgisayar Aritmetik Algoritmaları . AK Peters. ISBN'si 1-56881-160-8.
• Flores, Ivan (1963). Bilgisayar Aritmetiğinin Mantığı . Prentice-Hall.

Dış bağlantılar

• İkinin tamamlayıcı dizi çarpanı JavaScript simülatörü