Manfiy sonlar va to'ldiruvchi kod - Kompyuter arxitekturasi

Ikkilik yozuvda minus belgisi yo'q - faqat nollar va birlar. Manfiy sonni qanday yozish kerak?

Javob birinchi qarashda aniq ko'rinadi, lekin u noto'g'ri chiqadi.

Sodda yechim va uning muammosi #

Eng tabiiy g'oya: eng chap bitni ishora uchun ajratamiz.

Eng tabiiy fikr - eng chap bitni ishora uchun ajratish. Bu usul ishora va kattalik deb ataladi:

Son	Bitlari
+5	`00000101`
−5	`10000101`
+127	`01111111`
−127	`11111111`

Oddiy ko'rinadi, lekin ikkita jiddiy muammosi bor.

1-muammo: nolning ikki ko'rinishi bor.

Son	Bitlari
+0	`00000000`
−0	`10000000`

Bitlari har xil, qiymati esa bir xil - nol. Demak "ikki son tengmi?" degan oddiy tekshiruv ham murakkablashadi.

2-muammo: qo'shish oddiy ishlamaydi.

5 va −5 ni qo'shsak, nol chiqishi kerak edi:

Natija

  00000101      (+5)
+ 10000101      (-5)
= 10001010      (-10 ?)

Natija 10001010 - ya'ni bu usulda -10 degani. Nol emas.

Demak protsessorga qo'shish sxemasidan tashqari alohida ayirish sxemasi kerak bo'lardi. Bu esa qimmat.

Ikkita jiddiy muammo:

Ikkita nol - +0 va -0. Taqqoslash murakkablashadi.
Qo'shish buziladi - 5 + (-5) nol bermaydi.

Ikkinchisi hal qiluvchi. Protsessorga ayirish uchun alohida sxema kerak bo'lardi - qo'shimcha tranzistorlar, qo'shimcha murakkablik.

To'ldiruvchi kod #

Amaldagi yechim boshqacha va u ajoyib darajada nafis. To'ldiruvchi kod (two's complement) deb ataladi.

Qoida: manfiy son uchun barcha bitlarni teskari qiling va bittani qo'shing.

Soat siferblati kabi: eng kattadan keyin eng kichigi keladi

Son	Bitlari	O'n oltilikda
5	`00000101`	`0x05`
1	`00000001`	`0x01`
0	`00000000`	`0x00`
−1	`11111111`	`0xFF`
−2	`11111110`	`0xFE`
−5	`11111011`	`0xFB`
127	`01111111`	`0x7F`
−128	`10000000`	`0x80`

Manfiy sonni qo'lda yasash uchun ikki qadam yetarli. Masalan −5:

Qadam	Natija
1. `5` ning bitlarini yozamiz	`00000101`
2. Hamma bitni teskarilaymiz	`11111010`
3. Bittani qo'shamiz	`11111011`

Chiqqan 11111011 - aynan jadvaldagi −5.

Endi eng muhim foydasi. 12 + (−5) ni oddiy qo'shish bilan hisoblaymiz:

Natija

   00001100      (12)
 + 11111011      (-5)
 = 100000111     (9 bit chiqdi)

Natija sakkiz bitga sig'madi - to'qqizinchi bit paydo bo'ldi. Uni shunchaki tashlab yuboramiz:

00000111 = 7. To'g'ri javob.

Ya'ni ayirish uchun alohida sxema kerak emas - qo'shish sxemasining o'zi yetarli. 8-bo'limda buni temirda ko'ramiz.

Butun g'oyaning mohiyati

To'ldiruvchi kodda manfiy son shunday tanlanadiki, a + (-a) qo'shilganda natija noldan oshib, aylanib qaytadi.

Soat strelkasiga o'xshatish qulay: 12 soatlik siferblatda "3 soat orqaga" va "9 soat oldinga" bir xil natija beradi.

Aynan shuning uchun:

Foyda	Izoh
Ayirish sxemasi kerak emas	`a - b` = `a + (-b)`
Nol bitta	`00000000` - yagona ko'rinish
Taqqoslash oddiy	Bitlarni solishtirish yetarli

Bitta sumator bilan qo'shish ham, ayirish ham bajariladi - bu 8-bo'limda o'zimiz quradigan sxemadir.

-1 ning bitlari hammasi bir bo'lishiga e'tibor bering: 11111111. Bu juda ko'p uchraydigan naqsh - xotira dampida FF FF FF FF ko'rsangiz, bu ko'pincha -1.

Chegaralar va aylanib ketish #

8 bitli ishorali son quyidagi chegaralarda yashaydi:

	Qiymat
Eng kichik	−128
Eng katta	127
Jami qiymatlar	256

Manfiylar bittaga ko'p, chunki nol musbat tomonda turadi.

Chegaradan oshib ketsa, son aylanib ketadi:

Kutilgan qiymat	Haqiqiy natija
126	126
127	127	chegara
128	−128	aylanib ketdi
129	−127	aylanib ketdi
255	−1	aylanib ketdi
256	0	aylanib ketdi

Xuddi shu narsa 32 bitda ham sodir bo'ladi - va bu haqiqiy dasturlarda uchraydigan holat:

Amal	Natija
Eng katta 32 bitli son	2 147 483 647
Unga 1 qo'shsak	−2 147 483 648

-128 bor, +128 yo'q

Diqqat qiling: 8 bitda -128 dan 127 gacha. Manfiy tomonda bitta ko'p qiymat bor.

Sabab: nol musbat tomonda hisoblanadi, ya'ni musbatlar uchun 0...127 (128 ta qiymat), manfiylar uchun -128...-1 (yana 128 ta).

Bundan bitta kutilmagan oqibat chiqadi: -128 ning modulini olib bo'lmaydi. Uni musbatga o'girmoqchi bo'lsangiz, yana -128 chiqadi - chunki +128 bu turda mavjud emas.

Bu C va Java da haqiqiy xatolar manbai bo'lgan. 32 bitda ham xuddi shu holat takrorlanadi: eng kichik sonning moduli manfiy qoladi.

Chegaradan oshish - jiddiy zaiflik manbai

Aksariyat tizim dasturlarida butun sonlar qat'iy o'lchamda bo'ladi - ya'ni 8, 16, 32 yoki 64 bit.

Klassik xato shunday ko'rinadi: dastur foydalanuvchidan uzunlik qiymatini oladi va unga 1 qo'shib, shuncha joy ajratmoqchi bo'ladi.

Foydalanuvchi eng katta sonni bersa, +1 dan keyin natija manfiy bo'lib qoladi. Endi dastur manfiy hajmli joy so'raydi - va bu yerdan hamma narsa buziladi.

Bunday xatolar tarixda katta zaifliklarga olib kelgan.

Himoya usullari:

Usul	Izoh
Oldindan tekshirish	`if a > CHEGARA - b`
Xavfsiz funksiyalar	Rust dagi `checked_add`
Kengroq tur	`int64` ga o'tish
Kompilyator tekshiruvi	`-ftrapv`, sanitizatorlar

Ariane 5 raketasining 1996-yildagi qulashi ham shunga o'xshash turlar o'rtasidagi xato tufayli bo'lgan edi: 64 bitli haqiqiy son 16 bitli butun songa sig'magan.

Ishorali va ishorasiz #

Xuddi bir xil bitlar ikki xil o'qilishi mumkin:

Bitlar	Ishorasiz	Ishorali
`00000000`	0	0
`01111111`	127	127
`10000000`	128	-128
`11111111`	255	-1

Bitlarning o'zida "men manfiyman" degan ma'lumot yo'q. Uni qanday o'qish - turga bog'liq.

Aynan shuning uchun C da unsigned va signed turlarni aralashtirish xavfli: bir xil baytlar butunlay boshqa son bo'lib chiqadi.

Amaliy topshiriq

-7 ni 8 bitli to'ldiruvchi kodda qo'lda yozing.
Ikki qadamni (teskarilash va +1) yozib ko'rsating.
-1 ning bitlari nima uchun hammasi bir ekanini tushuntiring.
20 + (-30) ni to'ldiruvchi kodda qo'lda hisoblang.
12 - 5 ni 12 + (-5) ko'rinishida bajarib, natijani tekshiring.
4 bitli sonda diapazon qanday bo'lardi? Jadval tuzing.
4 bitda 7 + 1 nima beradi?
Ishora va kattalik usulining ikki muammosini yoddan sanang.
-128 ning modulini olib bo'lmasligini tushuntiring.
Sevimli tilingizda butun son chegarasidan oshsa nima bo'lishini tekshiring.

Xulosa #

Ikkilik yozuvda minus belgisi yo'q - manfiylikni bitlar ifodalashi kerak.
Sodda "ishora biti" usuli ikkita muammo beradi: ikkita nol va buzilgan qo'shish.
To'ldiruvchi kod: bitlarni teskari qilib, bittani qo'shish.
Uning asosiy foydasi - ayirish uchun alohida sxema kerak emas.
a - b shunchaki a + (-b) ga aylanadi.
-1 ning bitlari hammasi bir: 11111111 (0xFF).
8 bitda diapazon -128...127: manfiylar bittaga ko'p, chunki nol musbat tomonda.
Shuning uchun -128 ning moduli qat'iy o'lchamli turda yana -128 bo'ladi.
Chegaradan oshish (overflow) jimgina sodir bo'ladi va jiddiy zaiflik manbai.
Bir xil bitlar ishorali va ishorasiz turda butunlay boshqa son beradi.

Keyingi bo'limda bitlarni bevosita boshqarishni o'rganamiz: AND, OR, XOR va surish amallari.

Sodda yechim va uning muammosi #

To'ldiruvchi kod #

Chegaralar va aylanib ketish #

Ishorali va ishorasiz #

Xulosa #

Xatolik topdingizmi?