25 Temmuz 2018 Çarşamba

Two's Complement

1. Complement Kelimesi Ne Anlama Gelir
Tamamlayıcı anlamına gelir. Two's Complement'te sanırım Adder devresinden dolayı bu isimle anılıyor. One's Complement yazısına da bakabilirsiniz.

Örnek
Elimizde şöyle bir dizi olsun.
l =  [1,3,5,7,10]
complement(l)
Diziyi 1-10 olarak tamamlamak için şu sayılar gerekir.
[2, 4, 6, 8, 9]
2. Two's Complement'e Giriş
Two's complement eksi sayıları en solda 1 değeri olacak şekilde saklar.

Örnek
Elimizde 3 bitlik sayılar olsun. Two's complement ile temsil etmek için şöyle yaparız. Eksi sayıların en solundaki bit her zaman 1 olur.
011 =  3
010 =  2
001 =  1
000 =  0
111 = -1
110 = -2
101 = -3
100 = -4
Örnek
4 bitlik int değerleri temsil etmek için şöyle yaparız
|  i |  bin | comp | -i | 
+----+------+------+----+
|  0 | 0000 | 0000 | -0 |
|  1 | 0001 | 1111 | -1 |
|  2 | 0010 | 1110 | -2 |
|  3 | 0011 | 1101 | -3 |
|  4 | 0100 | 1100 | -4 |
|  5 | 0101 | 1011 | -5 |
|  6 | 0110 | 1010 | -6 |
|  7 | 0111 | 1001 | -7 |
| -8 | 1000 | 1000 | -8 |
| -7 | 1001 | 0111 |  7 |
| -6 | 1010 | 0110 |  6 |
| -5 | 1011 | 0101 |  5 |
| -4 | 1100 | 0100 |  4 |
| -3 | 1101 | 0011 |  3 |
| -2 | 1110 | 0010 |  2 |
| -1 | 1111 | 0001 |  1 |
3. Neden Two's Complement
Açıklaması şöyle. Bize faydası op-code sayısını azaltması.
With 2s complement arithmetic, many operations (including addition and subtraction) don't come in "signed" or "unsigned" variants. That's why 2s complement: It doesn't need as many op-codes to support both signed and unsigned numbers
Two's Complement için Adder Devresi (Adder Circuit) kullanılır. Adder Devresi'nin açıklaması şöyle. Adder devresi sayıların toplama işlemini çok hızlı hale getiriyor. Yani sayıların toplamasını kolaylaştırmak için var. Hatta sayıların bitlerini tersine çevirmek kadar hızlı hale getiriyor.
Inside the computer, there is an Adder circuit that can combine two bits and produce a result plus carry bit. These circuits are chained together, so that the processor can add two entire words. The carry bit from this addition is exposed to via a processor status register, but is not normally available to high-level languages.
Örnek
Şöyle yaparız.Carry bit dikkate alınmazsa herşey çok kolay.
 2  010      2  010     2   010
 1  001     -1  111     2   010
== ====     == ====    ==  ====
 3  011      1 C001    -4   100
4. Signed Int Division
Kural şöyle.
Signed int division in two's complement is undefined if:

- the divisor is zero, OR
- the dividend is INT_MIN (==0x80000000 if int is int32_t) and the divisor is -1
(in two's complement, -INT_MIN > INT_MAX, which causes integer overflow, which is undefined behavior in C)
Yani şu kod Undefined Behavior verir.
int a = 0x80000000;
int b = -1;
int c = a / b;

5. En Küçük Eksi Sayı'nın Eksisi Yine Kendisine Eşittir
Açıklaması şöyle
twos-complement negation flips all of the bits in a number and then adds one.
Şöyle yaparız.
100 = MIN_VALUE //-4
011 = all bits flipped //3
100 = after adding 1 //-4
Dolayısıyla şu kod true döner.
-Integer.MIN_VALUE == Integer.MIN_VALUE

Hiç yorum yok:

Yorum Gönder