TECHNIKA: BITOVÉ OPERACE

Přiřazením V="A" je do proměnné V uložen znak "A". O tom se můžeme jednoduše přesvědčit příkazem say V. V počítači je hodnota "A" uložena do jednoho bytu jako bitový řetězec. Uvidíme ho příkazem say X2B(C2X(V)). Přitom samotný příkaz say C2X(V) zobrazí hexadecimální reprezentaci znaku "A". Funkce C2D(V) vrátí hodnotu V interpretovanou jako desítkové číslo. V ASCII má "A" hodnotu, zapsáno hexadecimálně, 41. Tj. v desítkové reprezentaci 4*16+1=65.

Seznam implementací bitových operací

AND
Funkce BITAND vrací bitový součin operandů.

OR
Funkce BITOR vrací bitový součet operandů.

XOR
Funkce BITXOR vrací výsledek operace eXclusive OR (XOR) prováděné po bitech.

Posun vlevo
Posun operandu N o B bitů doleva se provede pomocí výrazu

D2C(C2D(N)*(2**B))

B musí být nezáporné celé číslo.

Posun vpravo
Posun operandu N o B bitů doprava se provede pomocí výrazu

D2C(C2D(N)%(2**B))

B musí být nezáporné celé číslo.

PŘÍKLAD 1 - Vernamova metoda
BITXOR funkce je vlastně slavná Vernamova metoda šifrování a dešifrování dat. Chceme-li zašifrovat zprávu Text, vytvoříme nejdříve náhodný řetězec bitů Klic stejné délky jako je zpráva. Pak Text zašifrujeme příkazem

Sifra=BITXOR(Text,Klic)

Dešifrování provedeme příkazem

Puvodni_text=BITXOR(Sifra,Klic)

Pak Text==Puvodni_Text. Zkuste následující program.
 

/* VERNAM */
parse arg Text
L = LENGTH(Text) * 8; Key = ""
do J = 1 to L
  Key = Key || RANDOM(0, 1)
end
Key = X2C(B2X(Key))
Ciphertext = BITXOR(Text, Key)
Plaintext  = BITXOR(Ciphertext, Key)
if Plaintext == Text
  then say "Vernamova metoda pracuje"
  else say "Eh?"

 

PŘÍKLAD 2 - Gray code
Grayův kód (podle autora Franka Graye) je celočíselnou funkcí G(I), která je bijekcí pro každé celé číslo

N>=0, 0<=I<=2**(N-1)

a má vlastnost: Binární reprezentace G(I) a G(Ip1), pro Ip1=I+1, se liší pouze v jediném bitu.

Algoritmus generující Grayův kód využívá operace exclusive or (BITXOR) operandů I a I%2 (celá část po dělení I/2), což je bitový posun doprava o jeden bit.

Program GRAY zobrazí, pro hodnotu vstupního argumentu 15

00000000 00000001 00000011 00000010 00000110 00000111 00000101 00000100 00001100 00001101 00001111 00001110 00001010 00001011 00001001 00001000

Pro výpočet potřebujeme znát počet bitů kódu zaokrouhlený nahoru na hranici bytu. Zjistíme tedy počet bitů nutných k zápisu čísla N pomocí

LENGTH(X2B(D2X(N)))

Funkce BYTES vrací potřebný počet bytů pro zadaný počet bitů.
 

/* GRAY_CODE */
parse arg N
S = BYTES(LENGTH(X2B(D2X(N))))
Gray_code = ""
do I = 0 to N
  Ibrs1 = I % 2
  A = D2C(I, S); B = D2C(Ibrs1, S)
  C = BITXOR(A, B)
  Gray_code = Gray_code X2B(C2X(C))
end
say Gray_code
exit
 
BYTES: procedure
parse arg B
R = B // 8
if R <> 0 then B = B + 8 - R
return B % 8

 

 

PŘÍKLAD 3 - Dekompresní funkce
Vstupem pro tuto funkci je kompresovaný text C. Obsahuje dva typy kódových slov (příkazů) - LITERAL X and COPY X,-Y.

LITERAL X
znamená: připoj beze změny následujících X znaků v kompresovaném textu C na konec dekompresovaného textu D.

COPY X,-Y
znamená: vrať se zpět v D o Y znaků a zkopíruj X následujících znaků na konec D.

Pro kódování příkazu LITERAL použijeme 8 bitů a pro kódování příkazu COPY 16 bitů. Pokud v dalším příkazu jsou první 4 bity nulové, pak je to LITERAL a další 4 bity určují jeho délku X v intervalu 116 (ale kóduje se 015). Následujících X znaků je literál.
Jinak jde o příkaz COPY. V prvních 4 bitech je délka X. Ta může být 317, ale kóduje se 115. V dalších 12-ti bitech je posunutí Y, hodnota 14096, ale kóduje se 04095.

Tak třeba vstupní řetězec AAAAAABBBBCCCAABBBBC s 20-ti znaky může být kompresován na řetězec

'00'X || "A" ||,     /* literal */
'3000'X || ,         /* copy    */
'00'X || "B" || ,    /* literal */
'1000'X || ,         /* copy    */
'02'X || "CCC" || ,  /* literal */
'5008'X

s 14-ti znaky.
 

DECOMPRESS: procedure
parse arg C
D = ""; LengthC = LENGTH(C); Pc = 1; Pd = 1
do while Pc < LengthC
  Byte = SUBSTR(C, Pc, 1)
  if BITOR(Byte, '0F'X) = '0F'X
  then call LITERAL Byte
  else call COPY Byte
end
return D

LITERAL: procedure expose C D Pc Pd
parse arg L
L = C2D(L) + 1
D = D || SUBSTR(C, Pc + 1, L)
Pc = Pc + L + 1
Pd = Pd + L
return
 
COPY: procedure expose C D Pc Pd
parse arg L
L1 = C2D(L) % 16 + 2; L = L1
X = C2D(BITAND('0FFF'X, SUBSTR(C, Pc, 2))) + 1
Y = Pd - X
do while L > X
  D = D || SUBSTR(D, Y, X)
  L = L - X
  X = 2 * X
end
if L > 0 then D = D || SUBSTR(D, Y, L)
Pc = Pc + 2; Pd = Pd + L1
return

 

Literatura
Fiala E.R., Greene D.H., Data Compression with Finite Windows
CACM, April 1989, Vol. 32, No. 4, pp. 490-505
Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P., Numerical Recipes in C : the art of scientific computing
- 2nd ed. University Press, Cambridge, 1992


Obálka Obsah Index Hlavní stránka

změněno 30. července 2001
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.