TECHNIQUE: BIT ARRAY ENCODED AS DECIMAL NUMBER

Assume the bit array

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

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