libg++ provides several different classes supporting the use and manipulation of collections of bits in different ways.
Integer
provides "integer" semantics. It supports
manipulation of bits in ways that are often useful when treating bit arrays
as numerical (integer) quantities. This class is described elsewhere.
BitSet
provides "set" semantics. It supports operations
useful when treating collections of bits as representing potentially
infinite sets of integers.
BitSet32
supports fixed-length BitSets holding exactly
32 bits.
BitSet256
supports fixed-length BitSets holding exactly
256 bits.
BitString
provides "string" (or "vector") semantics.
It supports operations useful when treating collections of bits as
strings of zeros and ones.
These classes also differ in the following ways:
~, &,
|, ^, -
, the semantics differ. BitSets perform bit operations that
precisely mirror those for infinite sets. For example, complementing an
empty BitSet returns one representing an infinite number of set bits.
Operations on BitStrings and Integers operate only on those bits
actually present in the representation. For BitStrings and Integers,
the the &
operation returns a BitString with a length equal to
the minimum length of the operands, and |, ^
return one with
length of the maximum.
BitSets are objects that contain logically infinite sets of nonnegative integers. Representational details are discussed in the Representation chapter. Because they are logically infinite, all BitSets possess a trailing, infinitely replicated 0 or 1 bit, called the "virtual bit", and indicated via 0* or 1*.
BitSet32 and BitSet256 have they same properties, except they are of fixed length, and thus have no virtual bit.
BitSets may be constructed as follows:
BitSet a;
BitSet a = atoBitSet("001000");
BitSet a = atoBitSet("00101*");
BitSet a = longtoBitSet((long)23);
BitSet a = utoBitSet((unsigned)23);
The following functions and operators are provided (Assume the declaration of BitSets a = 0011010*, b = 101101*, throughout, as examples).
~a
a.complement()
a & b; a &= b;
a | b; a |= b;
a - b; a -= b;
a ^ b; a ^= b;
a.empty()
a == b;
a <= b;
a < b;
a != b; a >= b; a > b;
a.set(7)
a.clear(2)
a.clear()
a.set()
a.invert(0)
a.set(0,1)
a.test(3)
a.test(3, 5)
int i = a[3]; a[3] = 0;
a.first(1) or a.first()
a.first(0)
a.next(2, 1) or a.next(2)
first
and next
may be used as
iterators, as in
for (int i = a.first(); i >= 0; i = a.next(i))...
.
a.last(1)
a.prev(3, 0)
a.count(1)
a.virtual_bit()
a = atoBitSet("ababX", 'a', 'b', 'X');
a.printon(cout, '-', '.', 0)
a
to cout
represented with
'-'
for falses, '.'
for trues, and no replication marker.
cout << a
a
to cout
(representing lases by 'f'
,
trues by 't'
, and using '*'
as the replication marker).
diff(x, y, z)
and(x, y, z)
or(x, y, z)
xor(x, y, z)
complement(x, z)
BitStrings are objects that contain arbitrary-length strings of zeroes and ones. BitStrings possess some features that make them behave like sets, and others that behave as strings. They are useful in applications (such as signature-based algorithms) where both capabilities are needed. Representational details are discussed in the Representation chapter. Most capabilities are exact analogs of those supported in the BitSet and String classes. A BitSubString is used with substring operations along the same lines as the String SubString class. A BitPattern class is used for masked bit pattern searching.
Only a default constructor is supported. The declaration
BitString a;
initializes a to be an empty BitString.
BitStrings may often be initialized via atoBitString
and longtoBitString
.
Set operations ( ~, complement, &, &=, |, |=, -, ^, ^=
)
behave just as the BitSet versions, except that there is no
"virtual bit": complementing complements only those bits in the
BitString, and all binary operations across unequal length
BitStrings assume a virtual bit of zero. The &
operation
returns a BitString with a length equal to the minimum length of
the operands, and |, ^
return one with length of the
maximum.
Set-based relational operations (==, !=, <=, <, >=, >
)
follow the same rules. A string-like lexicographic comparison
function, lcompare
, tests the lexicographic relation between
two BitStrings. For example, lcompare(1100, 0101) returns 1,
since the first BitString starts with 1 and the second with 0.
Individual bit setting, testing, and iterator operations
(set, clear, invert, test, first, next, last, prev
)
are also like those for BitSets. BitStrings are automatically
expanded when setting bits at positions greater than their
current length.
The string-based capabilities are just as those for class String.
BitStrings may be concatenated (+, +=
), searched
(index, contains, matches
), and extracted into
BitSubStrings (before, at, after
) which may be assigned and
otherwise manipulated. Other string-based utility functions
(reverse, common_prefix, common_suffix
) are also provided.
These have the same capabilities and descriptions as those
for Strings.
String-oriented operations can also be performed with a mask via class BitPattern. BitPatterns consist of two BitStrings, a pattern and a mask. On searching and matching, bits in the pattern that correspond to 0 bits in the mask are ignored. (The mask may be shorter than the pattern, in which case trailing mask bits are assumed to be 0). The pattern and mask are both public variables, and may be individually subjected to other bit operations.
Converting to char* and printing ((atoBitString,
atoBitPattern, printon, ostream <<)
) are also as in BitSets,
except that no virtual bit is used, and an 'X' in a BitPattern means
that the pattern bit is masked out.
The following features are unique to BitStrings.
Assume declarations of BitString a = atoBitString("01010110") and b = atoBitSTring("1101").
a = b + c;
a = b + 0; a = b + 1;
a += b;
a += 0; a += 1;
a << 2; a <<= 2
a >> 3; a >>= 3
a.left_trim(0)
a.right_trim(0)
cat(x, y, z)
diff(x, y, z)
and(x, y, z)
or(x, y, z)
xor(x, y, z)
lshift(x, y, z)
rshift(x, y, z)
complement(x, z)