Ïðèìåð

Îäíèì èç ïðèìåíåíèé áèòîâûõ ñòðîê â ïðîãðàììèðîâàíèè ÿâëÿåòñÿ ïðåäñòàâëåíèå ïîäìíîæåñòâ èç êîíå÷íîãî ÷èñëà èñõîäíûõ ýëåìåíòîâ; ïî-ïðîñòó ãîâîðÿ, ó íàñ èìååòñÿ êîíå÷íîå ìíîæåñòâî îáúåêòîâ (íàïðèìåð, ñîòðóäíèêè êàêîãî-íèáóäü ïðåäïðèÿòèÿ, èëè òóìáëåðû íà êàêîì-íèáóäü ïóëüòå óïðàâëåíèÿ, èëè äàæå ïðîñòî ÷èñëà îò 0 äî N) è íàì â ïðîãðàì-ìå íóæíà âîçìîæíîñòü ïðåäñòàâëÿòü ïîäìíîæåñòâî ýòîãî ìíîæåñòâà:

êàêèå èç ñîòðóäíèêîâ â íàñòîÿùåå âðåìÿ íàõîäÿòñÿ íà ðàáîòå; êàêèå èç òóìáëåðîâ íà ïóëüòå óñòàíîâëåíû â ïîëîæåíèå ¾âêëþ÷åíî¿; êàêèå èç N ñïîðòñìåíîâ, ó÷àñòâóþùèõ â ìàðàôîíå, ïðîøëè î÷åðåäíîé êîíòðîëü-íûé ïóíêò; è ò. ï. Íàèáîëåå î÷åâèäíîå ïðåäñòàâëåíèå äëÿ ïîäìíîæåñòâà ìíîæåñòâà N ýëåìåíòîâ ýòî îáëàñòü ïàìÿòè, ñîäåðæàùàÿ N äâîè÷íûõ ðàçðÿäîâ (òàê, åñëè â ìíîæåñòâî ìîãóò âõîäèòü ÷èñëà îò 0 äî 511, íàì ïîòðåáóåòñÿ 512 ðàçðÿäîâ, òî åñòü 64 îäíîáàéòîâûõ ÿ÷åéêè), ãäå êàæäî-ìó èç N âîçìîæíûõ ýëåìåíòîâ ïðèïèñûâàåòñÿ îäèí ðàçðÿä, è ýòîò ðàçðÿä áóäåò ðàâåí åäèíèöå, åñëè ñîîòâåòñòâóþùèé ýëåìåíò âõîäèò â ïîäìíîæå-ñòâî, è íóëþ â ïðîòèâíîì ñëó÷àå. Ãîâîðÿò, ÷òî êàæäîìó èç N îáúåêòîâ ïðèñâîåí îäèí èç äâóõ ñòàòóñîâ: ëèáî ¾âõîäèò â ìíîæåñòâî¿ (1), ëèáî

¾íå âõîäèò â ìíîæåñòâî¿ (0).

Èòàê, ïóñòü íàì ïîòðåáîâàëîñü ïîäìíîæåñòâî ìíîæåñòâà èç 512 ýëå-ìåíòîâ; ýòî ìîãóò áûòü ñîâåðøåííî ïðîèçâîëüíûå îáúåêòû, íàñ èíòåðå-ñóåò òîëüêî òî, ÷òî ó êàæäîãî èç íèõ åñòü óíèêàëüíûé íîìåð ÷èñëî îò 0 äî 511. ×òîáû õðàíèòü òàêîå ìíîæåñòâî, ìû îïèøåì ìàññèâ èç 16

¾äâîéíûõ ñëîâ¿ (íàïîìíèì, ÷òî ¾äâîéíîå ñëîâî¿ ñîäåðæèò 32 áèòà è ìî-æåò, ñîîòâåòñòâåííî, õðàíèòü ñòàòóñ 32 ðàçíûõ îáúåêòîâ). Êàê îáû÷íî, ýëåìåíòû ìàññèâà áóäåì ñ÷èòàòü çàíóìåðîâàííûìè (èëè èìåþùèìè èí-äåêñû) îò 0 äî 15. Ýëåìåíò ìàññèâà ñ èíäåêñîì 0 áóäåò õðàíèòü ñòàòóñ îáúåêòîâ ñ íîìåðàìè îò 0 äî 31, ýëåìåíò ñ èíäåêñîì 1 ñòàòóñ îáúåêòîâ ñ íîìåðàìè îò 32 äî 63, è ò. ä. Ïðè ýòîì âíóòðè ñàìîãî ýëåìåíòà áèòû áóäåì ñ÷èòàòü çàíóìåðîâàííûìè ñïðàâà íàëåâî, òî åñòü ñàìûé ìëàäøèé ðàçðÿä áóäåò èìåòü íîìåð 0, ñàìûé ñòàðøèé íîìåð 31. Íàïðèìåð, ñòà-òóñ îáúåêòà ñ íîìåðîì 17 áóäåò õðàíèòüñÿ â 17-ì áèòå íóëåâîãî ýëåìåíòà ìàññèâà; ñòàòóñ îáúåêòà ñ íîìåðîì 37 â 5-ì áèòå ïåðâîãî ýëåìåíòà; ñòà-òóñ îáúåêòà ñ íîìåðîì 510 â 29-ì áèòå 15-ãî ýëåìåíòà ìàññèâà. Âîîáùå,

÷òîáû ïî íîìåðó îáúåêòà X óçíàòü, â êàêîì áèòå êàêîãî ýëåìåíòà ìàñ-ñèâà õðàíèòñÿ åãî ñòàòóñ, äîñòàòî÷íî ðàçäåëèòü X íà 32 (êîëè÷åñòâî áèò â êàæäîì ýëåìåíòå) ñ îñòàòêîì. ×àñòíîå áóäåò ñîîòâåòñòâîâàòü íîìåðó ýëåìåíòà â ìàññèâå, îñòàòîê íîìåðó áèòà â ýòîì ýëåìåíòå. Ýòî ìîæíî áûëî áû ñäåëàòü ñ ïîìîùüþ êîìàíäû div, íî ëó÷øå áóäåò âñïîìíèòü,

÷òî ÷èñëî 32 åñòü ñòåïåðü äâîéêè (2⁵), òàê ÷òî åñëè âçÿòü ìëàäøèå ïÿòü áèò ÷èñëà X, ìû ïîëó÷èì îñòàòîê îò åãî äåëåíèÿ íà 32, à åñëè âûïîëíèòü äëÿ íåãî ïîáèòîâûé ñäâèã âïðàâî íà 5 ïîçèöèé ðåçóëüòàò áóäåò ðàâåí

èñêîìîìó ÷àñòíîìó. Íàïðèìåð, ïóñòü ÷èñëî X çàíåñåíî â ðåãèñòð EBX, è íàì íåîáõîäèìî óçíàòü ñîîòâåòñòâóþùèé íîìåð ýëåìåíòà è íîìåð áèòà â ýëåìåíòå. Îáà íîìåðà íå ïðåâîñõîäÿò 255 (òî÷íåå, íîìåð ýëåìåíòà íå ïðåâîñõîäèò 15, à íîìåð áèòà íå ïðåâîñõîäèò 32), òàê ÷òî ðåçóëüòàò ìû ìîæåì ðàçìåñòèòü â îäíîáàéòîâûõ ðåãèñòðàõ; ïóñòü ýòî áóäóò BL (äëÿ íîìåðà áèòà) è BH (äëÿ íîìåðà ýëåìåíòà ìàññèâà). Ïîñêîëüêó çàíåñåíèå ëþáûõ íîâûõ çíà÷åíèé â BL è BH èñïîðòèò ñîäåðæèìîå ðåãèñòðà EBX êàê öåëîãî, ëîãè÷íî áóäåò ñíà÷àëà ñêîïèðîâàòü ÷èñëî êóäà-òî åù¼, íàïðèìåð â EDX, ïîòîì â EBX îáíóëèòü âñå áèòû, êðîìå ïÿòè ìëàäøèõ (ïðè ýòîì è çíà÷åíèå EBX êàê öåëîãî, è çíà÷åíèå åãî ìëàäøåãî áàéòà ðåãèñòðà BL ñòàíóò ðàâíû èñêîìîìó îñòàòêó îò äåëåíèÿ; ïîòîì â EDX ìû âûïîëíèì ñäâèã âïðàâî è ðåóëüòàò (êîòîðûé ïîëíîñòüþ óìåñòèòñÿ â ìëàäøåì áàéòå ðåãèñòðà EDX, òî åñòü â ðåãèñòðà DL) ñêîïèðóåì â BH:

mov edx, ebx

and ebx, 11111b ; âçÿëè 5 ìëàäøèõ ðàçðÿäîâ shr edx, 5 ; ðàçäåëèëè îñòàëüíîå íà 32 mov bh, dl

Îäíàêî òî æå ñàìîå ìîæíî ñäåëàòü è êîðî÷å, áåç èñïîëüçîâàíèÿ äîïîë-íèòåëüíûõ ðåãèñòðîâ, âåäü âñå íóæíûå áèòû ó íàñ ñ ñàìîãî íà÷àëà íàõî-äÿòñÿ â EBX. Ìëàäøèå ïÿòü ðàçðÿäîâ ÷èñëà X ýòî íóæíûé íàì îñòàòîê îò äåëåíèÿ, à íóæíîå íàì ÷àñòíîå ýòî ñëåäóþùèå íåñêîëüêî (â äàííîì ñëó÷àå íå áîëåå ÷åòûð¼õ) ðàçðÿäîâ. Êîãäà â EBX çàíåñëè ÷èñëî X, ýòè ðàçðÿäû îêàçàëèñü â ïîçèöèÿõ, íà÷èíàÿ ñ ïÿòîé, à íàì íóæíî, ÷òîáû îíè îêàçàëèñü â ðåãèñòðå BH, êîòîðûé åñòü íè ÷òî èíîå êàê âòîðîé áàéò ðåãèñòðà EBX, òàê ÷òî äîñòàòî÷íî ñäâèíóòü âñ¼ ñîäåðæèìîå EBX âëåâî íà òðè ïîçèöèè, è íóæíûé íàì ðåçóëüòàò äåëåíèÿ àêêóðàòíî ¾âïèøåòñÿ¿ â BH; ïîñëå ýòîãî ñîäåðæèìîå BL ìû ñäâèíåì îáðàòíî íà òå æå òðè áèòà,

÷òî çàîäíî è î÷èñòèò íàì åãî ñòàðøèå áèòû:

shl ebx, 3 shr bl, 3

Íàó÷èâøèñü ïðåîáðàçîâûâàòü íîìåð îáúåêòà â íîìåð ýëåìåíòà ìàññè-âà è íîìåð ðàçðÿäà â ýëåìåíòå, âåðí¼ìñÿ ê èñõîäíîé çàäà÷å. Äëÿ íà÷àëà îïèøåì ìàññèâ:

section .bss set512 resd 16

Òåïåðü ó íàñ åñòü ïîäõîäÿùàÿ îáëàñòü ïàìÿòè, è ñ àäðåñîì å¼ íà÷àëà ñâÿ-çàíà ìåòêà set512. Ãäå-òî â íà÷àëå ïðîãðàììû (à âîçìîæíî, è íå òîëüêî â íà÷àëå) íàì, âèäèìî, ïîíàäîáèòñÿ îïåðàöèÿ î÷èñòêè ìíîæåñòâà, òî åñòü òàêîé íàáîð êîìàíä, ïîñëå êîòîðîãî ñòàòóñ âñåõ ýëåìåíòîâ îêàçûâàåòñÿ

íóëåâîé (â ìíîæåñòâî íå âõîäèò íè îäèí ýëåìåíò). Äëÿ ýòîãî äîñòàòî÷íî çàíåñòè íóëè âî âñå ýëåìåíòû ìàññèâà, íàïðèìåð, òàê:

section .text

; ...

xor eax, eax ; eax := 0

mov ecx, 15 mov esi, set512 lp: mov [esi+4*ecx], eax

loop lp

Ïóñòü òåïåðü ó íàñ â ðåãèñòðå EBX èìååòñÿ íîìåð ýëåìåíòà X, è íàì íåîáõîäèìî âíåñòè ýëåìåíò â ìíîæåñòâî, òî åñòü óñòàíîâèòü ñîîòâåòñòâó-þùèé áèò â åäèíèöó. Äëÿ ýòîãî ìû ñíà÷àëà íàéä¼ì íîìåð áèòà â ýëåìåí-òå ìàññèâà è âû÷èñëèì ìàñêó òàêîå ÷èñëî, â êîòîðîì òîëüêî îäèí áèò (êàê ðàç íóæíûé íàì) ðàâåí åäèíèöå, à â îñòàëüíûõ ðàçðÿäàõ íó-ëè. Çàòåì ìû íàéä¼ì íóæíûé ýëåìåíò ìàññèâà è ïðèìåíèì ê íåìó è ê ìàñêå îïåðàöèþ ¾èëè¿, ðåçóëüòàò êîòîðîé çàíåñ¼ì îáðàòíî â ýëåìåíò ìàññèâà. Ïðè ýòîì íóæíûé íàì áèò â ýëåìåíòå îêàæåòñÿ ðàâåí åäèíèöå, à îñòàëüíûå íå èçìåíÿòñÿ. Äëÿ âû÷èñëåíèÿ ìàñêè ìû âîçüì¼ì åäèíèöó è ñäâèíåì å¼ íà íóæíîå êîëè÷åñòâî ðàçðÿäîâ âëåâî. Íàïîìíèì, ÷òî èç ðåãèñòðîâ òîëüêî CL ìîæåò áûòü âòîðûì àðãóìåíòîì êîìàíä ïîáèòîâûõ ñäâèãîâ, òàê ÷òî íîìåð áèòà èìååò ñìûñë ñðàçó âû÷èñëÿòü â CL. Èòàê, ïèøåì:

; âíåñòè â ìíîæåñòâî set512 ýëåìåíò,

; íîìåð êîòîðîãî íàõîäèòñÿ â EBX

mov cl, bl ; ïîëó÷àåì íîìåð áèòà

and cl, 11111b ; â ðåãèñòðå CL

mov eax, 1 ; ñîçäà¼ì ìàñêó

shl eax, cl ; â ðåãèñòðå EAX

mov edx, ebx ; âû÷èñëÿåì íîìåð ýë-òà

shr edx, 5 ; â ðåãèñòðå edx

or [set512+4*edx], eax ; ïðèìåíÿåì ìàñêó

Àíàëîãè÷íî ðåøàåòñÿ è çàäà÷à ïî èñêëþ÷åíèþ ýëåìåíòà èç ìíîæåñòâà, òîëüêî ìàñêà íà ýòîò ðàç áóäåò èíâåðòèðîâàíà (0 â íóæíîì ðàçðÿäå, åäèíèöû âî âñåõ îñòàëüíûõ), à ïðèìåíÿòü ìû å¼ áóäåì ñ êîìàíäîé and (ëîãè÷åñêîå ¾è¿), â ðåçóëüòàòå ÷åãî íóæíûé áèò îáíóëèòñÿ, îñòàëüíûå íå èçìåíÿòñÿ:

; óáðàòü èç ìíîæåñòâà set512 ýëåìåíò,

; íîìåð êîòîðîãî íàõîäèòñÿ â EBX

mov cl, bl ; ïîëó÷àåì íîìåð áèòà

and cl, 11111b ; â ðåãèñòðå CL

mov eax, 1 ; ñîçäà¼ì ìàñêó

shl eax, cl ; â ðåãèñòðå EAX

not eax ; èíâåðòèðóåì ìàñêó

mov edx, ebx ; âû÷èñëÿåì íîìåð ýë-òà

shr edx, 5 ; â ðåãèñòðå edx

and [set512+4*edx], eax ; ïðèìåíÿåì ìàñêó

Óçíàòü, âõîäèò ëè ýëåìåíò ñ çàäàííûì íîìåðîì â ìíîæåñòâî, ìîæíî òîæå ñ ïîìîùüþ ìàñêè (åäèíèöà â íóæíîì ðàçðÿäå, íóëè â îñòàëüíûõ) è êîìàíäû test. Ðåçóëüòàò ïîêàæåò ôëàã ZF: åñëè îí áóäåò âçâåä¼í çíà÷èò, ñîîòâåòñòâóþùåãî ýëåìåíòà â ìíîæåñòâå íå áûëî, è íàîáîðîò:

; óçíàòü, âõîäèò ëè â ìíîæåñòâî set512 ýëåìåíò,

; íîìåð êîòîðîãî íàõîäèòñÿ â EBX

mov cl, bl ; ïîëó÷àåì íîìåð áèòà

and cl, 11111b ; â ðåãèñòðå CL

mov eax, 1 ; ñîçäà¼ì ìàñêó

shl eax, cl ; â ðåãèñòðå EAX

mov edx, ebx ; âû÷èñëÿåì íîìåð ýë-òà

shr edx, 5 ; â ðåãèñòðå edx

test [set512+4*edx], eax ; ïðèìåíÿåì ìàñêó

; òåïåðü ZF=1 îçíà÷àåò, ÷òî ýëåìåíò â ìíîæåñòâå

; îòñóòñòâîâàë, à ZF=0 - ÷òî ïðèñóòñòîâàë

Ðàññìîòðèì åù¼ îäèí ïðèìåð. Ïóñòü íàì ïîòðåáîâàëîñü ñîñ÷èòàòü, ñêîëüêî ýëåìåíòîâ âõîäÿò â ìíîæåñòâî. Äëÿ ýòîãî ïðèä¼òñÿ ïðîñìîòðåòü âñå ýëåìåíòû ìàññèâà è â êàæäîì èç íèõ ñîñ÷èòàòü åäèíè÷íûå áèòû. Ïðî-ùå âñåãî ýòî ñäåëàòü, çàãðóçèâ çíà÷åíèå èç ýëåìåíòà ìàññèâà â ðåãèñòð, à ïîòîì ñäâèãàÿ çíà÷åíèå âïðàâî íà îäèí áèò è êàæäûé ðàç ïðîâåðÿÿ, åäè-íèöà ëè â ìëàäøåì ðàçðÿäå; ýòî ìîæíî äåëàòü ðîâíî 32 ðàçà, íî ïðîùå çàêîí÷èòü, êîãäà â ðåãèñòðå îñòàíåòñÿ íîëü. Ìàññèâ ìû áóäåì ïðîñìàò-ðèâàòü ñ êîíöà, èíäåêñèðóÿ ïî ECX: ýòî ïîçâîëèò íàì ïðèìåíèòü êîìàíäó jecxz.  êà÷åñòâå ñ÷¼ò÷èêà ðåçóëüòàòà âîñïîëüçóåìñÿ ðåãèñòðîì EBX, à äëÿ àíàëèçà ýëåìåíòîâ ìàññèâà ïðèìåíèì EAX.

; ñîñ÷èòàòü ýëåìåíòû â ìíîæåñòâå set512 xor ebx, ebx ; EBX := 0

mov ecx, 15 ; ïîñëåäíèé èíäåêñ

lp: mov eax, [set512+4*ecx] ; çàãðóçèëè ýëåìåíò lp2: test eax, 1 ; åäèíèöà â ìëàäøåì ðàçðÿäå?

jz notone ; åñëè íåò, ïðûãàåì

inc ebx ; åñëè äà, óâåëè÷èâàåì ñ÷¼ò÷èê notone: shr eax, 1 ; ñäâèíóëè EAX

test eax, eax ; òàì åù¼ ÷òî-òî îñòàëîñü?

jnz lp2 ; åñëè äà, ïðîäîëæàåì

; âíóòðåííèé öèêë

jecxz quit ; åñëè â ECX íîëü, çàêàí÷èâàåì

dec ecx ; èíà÷å óìåíüøàåì åãî

jmp lp ; è ïðîäîëæàåì âíåøíèé öèêë quit:

; òåïåðü ðåçóëüòàò ïîäñ÷¼òà íàõîäèòñÿ â EBX