Bitlar bilan ishlash - Kompyuter arxitekturasi

Protsessor sonlarni qo'sha oladi, lekin uning eng tabiiy ishi boshqa: bitlar ustida bir vaqtda amal bajarish.

Bu amallar eng arzon va eng tez - ular bir taktda bajariladi.

To'rtta asosiy amal #

Bu amallar bir vaqtda butun bayt ustida ishlaydi. Ikkita son olaylik:

	Ikkilikda	O'nlikda
`a`	`11001010`	202
`b`	`10110110`	182

Endi to'rt amalni qo'llaymiz:

Amal	Natija	O'nlikda	Qoidasi
`a VA b`	`10000010`	130	ikkalasi ham 1 bo'lsa
`a YOKI b`	`11111110`	254	bittasi 1 bo'lsa yetarli
`a XOR b`	`01111100`	124	farq qilsa 1
`EMAS a`	`00110101`	53	hamma bit teskari

Har bir bit juftligi uchun qoida shunday:

a	b	VA	YOKI	XOR
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

Bu jadval 8-bo'limda temirda qurgan elementlarning aynan o'zi - faqat u yerda bitta bit, bu yerda esa sakkiztasi birdan.

Eng muhim: & va && bir xil emas.

Amal	Nima qiladi	Natijasi
`&`	Har bit ustida alohida	Son
`and`	Butun qiymat ustida	Rost yoki yolg'on

6 & 3 ikkita bo'ladi (110 & 011 = 010), 6 and 3 esa 3 qaytaradi. Butunlay boshqa amallar.

XOR ning uchta xossasi

^ (eksklyuziv YOKI) - "faqat bittasi 1 bo'lsa" degani. Uning uchta xossasi juda ko'p ishlatiladi:

Xossa	Natija
`a ^ a`	0 - har doim
`a ^ 0`	`a` - o'zgarmaydi
`a ^ b ^ b`	`a` - qaytarib olinadi

Uchinchisi eng qimmatli: XOR o'z-o'zini bekor qiladi.

Shuning uchun u juftlik tekshiruvida (parity), RAID massivlarida va eng sodda shifrlashda ishlatiladi.

E'tibor bering: oddiy XOR shifrlash emas. Kalit takrorlansa uni buzish oson. Haqiqiy shifrlash "Amaliy kriptografiya" darsligida ko'rilgan.

Surish - eng arzon ko'paytirish #

Surish - ko'paytirishdan tez, chunki bu shunchaki simlarni siljitish

Raqamlarda ko'rsak:

Surish	Ikkilikda	Qiymati	Bu nima
`22` chapga 0	`00010110`	22	22 × 1
`22` chapga 1	`00101100`	44	22 × 2
`22` chapga 2	`01011000`	88	22 × 4
`22` chapga 3	`10110000`	176	22 × 8

O'ngga surish esa teskarisi:

Surish	Ikkilikda	Qiymati	Bu nima
`22` o'ngga 0	`00010110`	22	22 ÷ 1
`22` o'ngga 1	`00001011`	11	22 ÷ 2
`22` o'ngga 2	`00000101`	5	22 ÷ 4
`22` o'ngga 3	`00000010`	2	22 ÷ 8

Chapga surganda bitlar yo'qolishi mumkin

Sakkiz bitli sonni chapga surganda, chap chetidan chiqib ketgan bitlar qaytmaydi:

Surish	8 bitda qoladi	Nima bo'ldi
0	`10110000`	joyida
1	`01100000`	bir bit yo'qoldi
2	`11000000`	yana bir bit yo'qoldi

Shuning uchun surishni ko'paytirish o'rniga ishlatganda, natija razryadga sig'ishiga ishonch hosil qiling.

"Surish tezroq" - bu tushuntirish, maslahat emas

Surish ko'paytirishdan arzon ekani rost. Lekin bundan "demak har doim surishni ishlatish kerak" degan xulosa chiqmaydi.

Sabab: zamonaviy kompilyator × 8 ni ko'rsa, uni o'zi surishga aylantiradi - va buni sizdan yaxshiroq qiladi, chunki u butun kontekstni ko'radi.

Surish bitlar bilan ishlaganda o'z o'rnida: maydon ajratish, niqob yasash, bayroqlar bilan ishlash. Oddiy hisob-kitobda esa odatdagi ko'paytirish tushunarliroq.

Bayroqlar va niqoblar #

Bir nechta "ha/yo'q" qiymatini bitta songa sig'dirish - eng ko'p uchraydigan naqsh:

Sakkiz bitli bitta baytga sakkizta mustaqil belgi sig'adi

Bitta baytda bir nechta "ha/yo'q" javobini saqlash mumkin. Har bitga bitta ma'no biriktiriladi:

Amal	Bitlar	Qiymat	Ma'nosi
Boshlanish	`000`	0	hech narsa
O'qish qo'shildi	`100`	4	o'qish
Yozish qo'shildi	`110`	6	o'qish, yozish
Yozish olib tashlandi	`100`	4	o'qish
Bajarish almashtirildi	`101`	5	o'qish, bajarish
Yana almashtirildi	`100`	4	o'qish

Har amal uchun o'z biti bor:

Nima qilmoqchisiz	Qaysi amal
Bayroq qo'shish	`YOKI`
Bayroq bormi deb tekshirish	`VA`
Bayroqni olib tashlash	`VA` + `EMAS`
Bayroqni almashtirish	`XOR`

Linux dagi tanish 755 ruxsati aynan shu: 0o755 ikkilikda 111101101 - uch guruhga bo'lingan to'qqizta bayroq.

To'rtta asosiy amalni yodlab qo'ying:

Maqsad	Amal
Bitni yoqish	`qiymat \|= BAYROQ`
Bitni o'chirish	`qiymat &= ~BAYROQ`
Bitni almashtirish	`qiymat ^= BAYROQ`
Bitni tekshirish	`qiymat & BAYROQ`

Linux fayl huquqlari (755), TCP bayroqlari (SYN, ACK), protsessor holat registri - hammasi shu naqsh.

Maydonlarni ajratib olish #

Bir nechta qiymat bitta songa joylashtirilganda, ularni surish va niqob bilan ajratib olinadi:

#AF3C6D rangi aslida bitta 24 bitli son. Undagi uchta rangni ajratib olish uchun surish va niqoblash yetarli:

Qism	Bitlari	Qiymati
To'liq son	`101011110011110001101101`	-
Qizil	`10101111`	175
Yashil	`00111100`	60
Ko'k	`01101101`	109

Qizilni olish uchun sonni 16 bitga o'ngga suramiz va oxirgi 8 bitni niqoblab olamiz. Yashil uchun 8 bitga, ko'k uchun umuman surmaymiz.

Teskari yo'l ham shunday - uchta qiymatni joyiga surib, birlashtirsak, yana #AF3C6D chiqadi.

Bit amallari bilan bir nechta foydali hiyla ham bor:

Son	Juftmi	2 ning darajasimi	Nechta biri 1
6	ha	yo'q	2
7	yo'q	yo'q	3
8	ha	ha	1
16	ha	ha	1
17	yo'q	yo'q	2

Juftlikni bilish uchun eng oxirgi bitga qarash yetarli: u 0 bo'lsa - son juft.

son & (son - 1) nima uchun ishlaydi?

Bu hiyla "son 2 ning darajasimi?" degan savolga javob beradi.

2 ning darajasida faqat bitta bit yoqilgan:

Natija

8     = 1000
8 - 1 = 0111      # eng past bitlar to'ldi
8 & 7 = 0000      # umumiy bit yo'q

Boshqa sonlarda esa hamisha umumiy bit qoladi:

Natija

6     = 0110
6 - 1 = 0101
6 & 5 = 0100      # nol emas

Bu naqsh xesh-jadvallarda keng ishlatiladi: jadval hajmi 2 ning darajasi bo'lsa, hash % hajm o'rniga hash & (hajm - 1) yozish mumkin - va bu ancha tez.

Ishorali sonni o'ngga surish - tuzoq

Manfiy sonni o'ngga surganda ikki xil xulq bo'lishi mumkin:

Turi	Bo'sh joyga nima keladi	Natija
Arifmetik	Ishora biti takrorlanadi	Manfiy qoladi
Mantiqiy	Nol keladi	Katta musbat son

Protsessorlarda ikkala komanda ham bor va ular alohida kodlar bilan belgilanadi. Qaysi biri ishlatilishi sonning turiga bog'liq: ishorali son uchun arifmetik, ishorasiz son uchun mantiqiy surish tanlanadi.

Shuning uchun bir xil bitlar, bir xil surish - lekin son ishorali yoki ishorasiz deb e'lon qilinganiga qarab natija butunlay boshqa bo'ladi.

Amaliy topshiriq

11001010 va 10110110 uchun uchala amalni qo'lda bajaring.
a XOR b XOR b nima uchun yana a berishini tushuntiring.
22 ni chapga 4 marta surganda 8 bitda nima qoladi?
200 ni o'ngga 3 marta suring - natija qancha?
Ruxsat bayroqlariga to'rtinchi huquq qo'shsangiz, qiymat qanday bo'ladi?
755 ruxsatini to'qqizta bitga yoyib yozing.
0x1A2B3C4D dan to'rtta baytni ajratib yozing.
#FF8000 rangining uch qismini toping.
Sonning juftligini bitta bitga qarab qanday bilish mumkin?
Arifmetik va mantiqiy surish farqini uch qatorda yozing.

Xulosa #

Bit amallari eng arzon: ular bir taktda bajariladi.
& har bit ustida ishlaydi, and esa butun qiymat ustida - aralashtirmang.
^ (XOR) o'z-o'zini bekor qiladi: a ^ b ^ b == a.
Chapga surish 2 ga ko'paytiradi, o'ngga surish 2 ga bo'ladi.
Qat'iy o'lchamli turda chapga surganda bitlar chiqib ketadi.
Surish arzon, lekin oddiy ko'paytirishni surishga almashtirish shart emas.
Bayroqlar naqshi: yoqish |=, o'chirish &= ~, almashtirish ^=, tekshirish &.
Maydon ajratish: avval surish, keyin niqoblash.
son & (son - 1) == 0 - son 2 ning darajasi ekanini tekshiradi.
Manfiy sonni o'ngga surish tilga bog'liq - shubhali joyda bo'lishni ishlating.

Keyingi bo'limda haqiqiy sonlarga o'tamiz va nima uchun 0.1 + 0.2 aniq 0.3 bermasligini ko'ramiz.