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
