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


Cover Contents Index Main page

last modified 30th July 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic