TECHNIKA: BITOVÉ POLE ZAKÓDOVANÉ DO ČÍSLA

Uvažme bitové pole

A.1 = 0; A.2 = 1; A.3 = 0; A.4 = 1; A.5 = 0
A.6 = 1; A.7 = 1; A.8 = 0; A.9 = 0; A.10 = 1

Toto pole můžeme zakódovat jako bitový řetězec 0101011001 nebo jako desítkové číslo

1*2**1 + 1*2**3 + 1*2**5 + 1*2**6 + 1*2**9 = 618

Naopak, číslo 618 může být rozkódováno jako bitový řetězece nebo dokonce jako bitové pole tímto postupem:

618 // 2 = 0; 618 % 2 = 309
309 // 2 = 1; 309 % 2 = 154
154 // 2 = 0; 154 % 2 =  77
 77 // 2 = 1;  77 % 2 =  38
 38 // 2 = 0;  38 % 2 =  19
 19 // 2 = 1;  19 % 2 =   9
  9 // 2 = 1;   9 % 2 =   4
  4 // 2 = 0;   4 % 2 =   2
  2 // 2 = 0;   2 % 2 =   1
  1 // 2 = 1;   1 % 2 =   0

 

A zde je funkce BITARRAY2D, která vrátí desítkové číslo jako reprezentaci zadaného bitové pole A.:
 

BITARRAY2D: procedure expose A.
parse arg N
/* for N <= 10000 */
numeric digits 3011; Nd = 2 ** N - 1
numeric digits LENGTH(Nd)
D = 0; B = 1
do J = 1 to N
  if A.J then D = D + B
  B = 2 * B
end
return D

 

Inverzní podprogram D2BITARRAY vytvoří bitové pole ze zadaného desítkového čísla:
 

D2BITARRAY: procedure expose A.
parse arg D, N
/* for N <= 10000 */
numeric digits 3011; Nd = 2 ** N - 1
numeric digits LENGTH(Nd)
do J = 1 while D > 0
  A.J = D // 2
  D = D % 2
end
do J = J to N; A.J = 0; end
return

 

Poznámka:
To, co jsem tu popsal, je technika, ne nejlepší algoritmus převodu bitového pole na číslo a naopak. Následující funkce BITARRAY2D_B je rychlejší pro N=10000 než BITARRAY2D.

BITARRAY2D_B: procedure expose A.
parse arg N
/* for N <= 10000 */
numeric digits 3011; Nd = 2 ** N - 1
numeric digits LENGTH(Nd)
String = ""
do J = N to 1 by -1
  String = String || A.J
end
return X2D(B2X(String))

 

SOUVISLOSTI

Literatura
Martello S., Toth P., Knapsack Problems: Algorithms nad Computer Implementations
Chichester, John Wiley & sons 1990


Obálka Obsah Index Hlavní stránka

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