This array can be encoded as bit string
0101011001 or as decimal number
1*2**1 + 1*2**3 + 1*2**5 + 1*2**6 + 1*2**9 = 618
And vice versa: the number 618 can be decoded as the bit string or array:
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
|
And there is the BITARRAY2D function, it returns a decimal representation of bit array 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
|
And the D2BITARRAY subroutine creates a bit array representation of decimal number:
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
|
Note: This was the example of using of technique. The BITARRAY2D isn't the most effective algorithm. The following BITARRAY2D_B function is more quick for N=10000 than 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))
|
CONNECTIONS
Literature
Martello S., Toth P., Knapsack Problems: Algorithms nad Computer Implementations
Chichester, John Wiley & sons 1990
