libg++ provides several different classes supporting the use and manipulation of collections of bits in different ways.
Integerprovides "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.
BitSetprovides "set" semantics. It supports operations useful when treating collections of bits as representing potentially infinite sets of integers.
BitSet32supports fixed-length BitSets holding exactly 32 bits.
BitSet256supports fixed-length BitSets holding exactly 256 bits.
BitStringprovides "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 = 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 & b; a &= b;
a | b; a |= b;
a - b; a -= b;
a ^ b; a ^= b;
a == b;
a <= b;
a < b;
a != b; a >= b; a > b;
int i = a; a = 0;
a.first(1) or a.first()
a.next(2, 1) or a.next(2)
nextmay be used as iterators, as in
for (int i = a.first(); i >= 0; i = a.next(i))....
a = atoBitSet("ababX", 'a', 'b', 'X');
a.printon(cout, '-', '.', 0)
'.'for trues, and no replication marker.
cout << a
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)
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
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
returns a BitString with a length equal to the minimum length of
the operands, and
|, ^ return one with length of the
Set-based relational operations (
==, !=, <=, <, >=, >)
follow the same rules. A string-like lexicographic comparison
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
The string-based capabilities are just as those for class String.
BitStrings may be concatenated (
+, +=), searched
index, contains, matches), and extracted into
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
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 (
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
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)