Doc. No. X3J16/93-0012-R2 ISO/WG21/N0220-R2 Date: December 8, 1993 Project: Programming Language C++ Reply to: Chuck Allison allison@decus.org (801) 240-4510 A Proposal for Two Bitset Classes 1.0 Introduction Many vendors currently supply bit-handling classes to compensate for = the deficiencies of the bitwise operators of the C programming language. This paper proposes = two bitset classes for the standard C++ library. Class bits accommodates a fixed-length collection of bits. It extends= C bitwise semantics by allowing easy access to bits, by allowing an arbitrary number of bits= in a bitset, and by add- ing important new functionality. It is defined as a template class, w= ith the number of bits in the collection as the template parameter. It is highly suitable for i= nterface with the host operating system, and is designed for efficiency (it can be stack-bas= ed). Here's a sample program run on a machine with 16-bit integers: // tbits.cpp: Set some bits and display the result - #include #include #include #include #include "bits.h" main() { const size_t SIZE == CHAR_BIT*sizeof(int); bits flags; enum open_mode {in, out, ate, app, trunc, nocreate, noreplace, bi= nary}; flags.set(in); flags.set(binary); cout << "flags: " << flags << " (0x" << hex << flags.to_ushort() = << ")\n"; cout << "binary? " << (flags.test(binary) ? "yes" : "no") << endl= ; return 0; } Output flags: 0000000010000001 (0x81) binary? yes While the above example uses a word-sized object, bits objects can be= as large as your stack allows.=20 Class bitstring can be used when the number of bits is not known at c= ompile time, or if a dynamic-length bitset is needed. Although it supports the usual bit-h= andling operations, it is above all a string, and as such incorporates much of the functionalit= y of the proposed string class. I use this class as part of a user interface library, w= here a picklist widget has an underlying bitstring that tracks users choices: class Picklist : public Popmenu { bitstring picks; . . . public: Picklist(... nitems ...) : picks(0,nitems), ... {} . . . }; Neither of these classes attempts to provide complete semantics for m= athematical sets, but member functions exist that provide the equivalent of union, intersec= tion, and symmetric difference as well as insert, remove and test for membership. Exception classes are global to bits so that they aren't tied to the = template parameter nbits. Namespaces will make this cleaner. 2.0 Class bits #include #include // Exception base class #include // C++ string class class istream; class ostream; class out_of_range : public xmsg { }; class invalid_argument : public xmsg { }; class overflow : public xmsg { }; template class bits { public: // Constructors bits(); bits(unsigned long n); bits(const bits& b); bits(const string& s); // Conversions unsigned short to_ushort() const throw (overflow); unsigned long to_ulong() const throw (overflow); string to_string() const throw (xalloc); =20 // Assignment bits& operator==(const bits& b); // Equality bool operator====(const bits& b) const; bool operator!==(const bits& b) const; // Basic bit operations bits& set(size_t n) throw (out_of_range); bits& set(size_t n, int val) throw (out_of_range); bits& set(); bits& reset(size_t n) throw (out_of_range); bits& reset(); bits& toggle(size_t n) throw (out_of_range); bits& toggle(); bits operator~() const; int test(size_t n) const throw (out_of_range); bool any() const; bool none() const; // Bit-wise operators bits& operator&==(const bits& b); bits& operator|==(const bits& b); bits& operator^==(const bits& b); =20 // Shift operators bits& operator<<==(size_t n); bits& operator>>==(size_t n); bits operator<<(size_t n) const; bits operator>>(size_t n) const; // Miscellaneous size_t count() const; size_t length() const; }; // Global functions ostream& operator<<(ostream& os, const bits& b); istream& operator>>(istream& is, bits& b); bits operator&(const bits& b1, const bits& b2); bits operator|(const bits& b1, const bits& b2); bits operator^(const bits& b1, const bits& b2); 2.1 Constructors Synopsis bits() bits(unsigned long n) bits(const string& s) bits(const bits& b) 2.1.1 Constructor bits() Description Initializes all bits to zero. 2.1.2 Constructor bits(unsigned long n) Description Initializes the object with the bits of n. If nbits > s= izeof(unsigned long) * CHAR_BIT, the extra bits are set to zero. 2.1.3 Constructor bits(const string& s) Description Reads up to nbits characters ('1's and '0's) from s unt= il a non-bit character is encoun- tered. The last bit read is considered to be bit-0. Hig= h order bits are zero-filled if less than nbits characters are read. Exceptions Throws invalid_argument if a character other than '1' o= r '0' is encountered. 2.1.4 Constructor bits(const bits& b) Description Standard copy constructor. 2.2 Destructor No destructor required. 2.3 Member Functions 2.3.1 Function unsigned short to_ushort() const throw (overflow) Description The least significant (n == sizeof(unsigned short) * CH= AR_BIT) bits of *this are converted to an unsigned short. This is useful when the= bits represent flags in a word passed to the operating system. Exceptions Throws overflow if nbits > n and any of the bits above = position n-1 are set. 2.3.2 Function unsigned long to_ulong() const throw (overflow) Description The least significant (n == sizeof(unsigned long)*CHAR_= BIT) bits of *this are converted to an unsigned long. This is useful when the = bits represent flags in a word passed to the operating system. Exceptions Throws overflow if nbits > n and any of the bits above = position n-1 are set. 2.3.3 Function string to_string() const throw (xalloc) Description Creates a string of '1's and '0's representing the cont= ents of *this. As with unsigned integers, the last character is interpreted as bit-0. Returns The temporary string of '1's and '0's. 2.3.4 Function bits& operator==(const bits& b) Description Standard assignment operator. Returns A reference to *this. 2.3.5 Function bool operator====(const bits& b) const Description Compares *this to b for equality. Two bitsets are equal= if and only if their bit patterns are identical. Returns true if the bitsets are equal, false otherwise. 2.3.6 Function bool operator!==(const bits& b) const Description Compares *this to b for inequality. Two bitsets are equ= al if and only if their bit patterns are identical. Returns false if the bitsets are equal, true otherwise. 2.3.7 Functions set Synopsis bits& set(size_t n) bits& set(size_t n, int val) bits& set() Description These functions set one or more bits. The function set(= size_t, int) can reset a bit, depending on val. 2.3.7.1 Function bits& set(size_t n) throw (out_of_range= ) Description Sets the nth bit. Returns A reference to *this. Exceptions Throws out_of_range if n is not in [0,nbits-1]. 2.3.7.2 Function bits& set(size_t n, int val) throw (out= _of_range) Description Sets the nth bit if val is non-zero, otherwise r= esets the bit. Returns A reference to *this. Exceptions Throws out_of_range if n is not in [0,nbits-1]. 2.3.7.3 Function bits& set() Description Sets all bits. Returns A reference to *this. 2.3.8 Functions reset Synopsis bits& reset(size_t n) bits& reset() Description These functions reset one or more bits. 2.3.8.1 Function bits& reset(size_t n) throw (out_of_ran= ge) Description Resets the nth bit. Returns A reference to *this. Exceptions Throws out_of_range if n is not in [0,nbits-1]. 2.3.8.2 Function bits& reset() Description Resets all bits. Returns A reference to *this. 2.3.9 Functions toggle Synopsis bits& toggle(size_t n) bits& toggle() Description These functions toggle on or more bits. 2.3.9.1 Function bits& toggle(size_t n) throw (out_of_ra= nge) Description Toggles the nth bit. Returns A reference to *this. Exceptions Throws out_of_range if n is not in [0,nbits-1]. 2.3.9.2 Function bits& toggle() Description Toggles all bits. Returns A reference to *this. 2.3.10 Function bits operator~() const Description Toggles all the bits of a copy of *this. Returns A toggled copy of *this. 2.3.11 Function int test(size_t n) const throw (out_of_range) Description Tests if bit-n is set. Returns 1 if the bit is set, 0 otherwise. Exceptions Throws out_of_range if n is not in [0,nbits-1]. 2.3.12 Function bool any() const Description Tests if any bits at all are set. Returns false if all bits are 0, true otherwise. =20 2.3.13 Function bool none() const Description Tests if no bits at all are set. Returns true if all bits are 0, false otherwise. 2.3.14 Function bits& operator&==(const bits& b) Description Performs a destructive bitwise-AND of b into *this. Returns A reference to *this. =20 2.3.15 Function bits& operator|==(const bits& b) Description Performs a destructive bitwise-OR of b into *this. Returns A reference to *this. =20 2.3.16 Function bits& operator^==(const bits& b) Description Performs a destructive exclusive-OR of b into *this. Returns A reference to *this. =20 2.3.17 Function bits& operator>>==(size_t n) Description Shifts *this right destructively by n bit positions. If= n > nbits, then all bits are reset. Shifting "right" by n means that bit-0 receives the val= ue of bit-n, bit-1 receives bit-(n+1), etc. Returns A reference to *this. 2.3.18 Function bits& operator<<==(size_t n) Description Shifts *this left destructively by n bit positions. If = n > nbits, then all bits are reset. Shifting "left" by n means that bit-n receives the valu= e of bit-0, bit-(n+1) receives bit-1, etc. Returns A reference to *this. 2.3.19 Function bits operator>>(size_t n) const Description Shifts *this right non-destructively by n bit positions= . If n > nbits, then all bits are reset. Shifting "right" by n means that bit-0 receives = the value of bit-n, bit-1 receives bit-(n+1), etc. Returns The results of the shift in a temporary bits object. 2.3.20 Function bits operator<<(size_t n) const Description Shifts *this left non-destructively by n bit positions.= If n > nbits, then all bits are reset. Shifting "left" by n means that bit-n receives t= he value of bit-0, bit-(n+1) receives bit-1, etc. Returns The results of the shift in a temporary bits object. 2.3.21 Function size_t count() const Description Counts the number of bits that are set. Returns The number of 1-bits in *this. 2.3.22 Function size_t length() const Description Returns the fixed-size length of the object. Returns nbits. 2.4 Global Functions 2.4.1 Function ostream& operator<<(ostream& os, const bits& b= ) Description Sends a sequence of nbits '1's and '0's corresponding t= o the bit pattern of *this to the stream os. Returns A reference to the stream os. 2.4.2 Function istream& operator>>(istream& is, bits& b) Description Reads up to nbits characters from a sequence of '1's an= d '0's from into b. The first non-bit (non-white) character terminates the read and r= emains in the stream. Sets is.failbit if the first (non-white) character is not a = '1' or '1'. The last bit read is con- sidered to be bit-0. High-order bits are zero-filled if= less than nbits characters are read. Returns A reference to the stream is. Exceptions Throws invalid_argument if no '1's or '0's are found in= the stream. 2.4.3 Function bits operator&(const bits& b1, const bits& b2) Description Performs a bitwise-AND of b1 and b2. Returns The results of the bitwise-AND in a temporary bits obje= ct. 2.4.4 Function bits operator|(const bits& b1, const bits& b2) Description Performs a bitwise-OR of b1 and b2. Returns The results of the bitwise-OR in a temporary bits objec= t. 2.4.5 Function bits operator^(const bits& b1, const bits& b2) Description Performs a exclusive-OR of b1 and b2. Returns The results of the exclusive-OR in a temporary bits obj= ect. 2.5 Notes for Class bits 2.5.1 Having an expression as a template parameter has the following= effects: =FE a bits-object can be stack-based =FE objects of different sizes (i.e., with a different number of= bits) are different types (so such objects cannot be mixed in a common expression) =FE no global functions taking bits arguments are allowed under = the current definition of the language (because they become template functions, which ar= e not allowed to have expression parameters). I have included them anyway, in the ho= pe that this situation will get fixed someday. The current workaround is to define th= ese as inline friend functions. 2.5.2 Since this class is an "extension" of unsigned int as far as b= itwise operations are concerned, a collection of bits "behaves" like a number, i= n that bit-0 is con- sidered the rightmost bit. 2.5.3 To be consistent with C bitwise operations, the statements: bits<8> b; b |== 5; cout << b << endl; result in 00000101 that is, the bits of 5 are or'ed with b. 2.5.4 Some people prefer the word flip to toggle. 3.0 Class bitstring This abstraction represents a string of bits. It seems reasonable, th= erefore, for it to behave like a string, i.e., bit-0 is the leftmost, just like character-0 is = the leftmost item in character strings. I have proceeded under this assumption. If you want an abstr= action compatible with numeric conventions (i.e., where bit-0 is rightmost), use class bits = instead. Much of the functionality is identical to class bits. For binary oper= ations between two bit strings, the shorter is considered to be zero-padded on the right so = as to have the same length as the longer for the operation. All of the string class funct= ionality that seemed appropriate for bit strings has been integrated into this class, and = a new function, trim(), has been added. The constant NPOS is an implementation-dependent "SIZ= E_T_MAX", defined in the proposed string class. #include #include #include #include // C++ string class class bitstring { public: // Exceptions class invalid_argument : public xmsg { }; class out_of_range : public xmsg { }; // Constructors / Destructor bitstring() throw (xalloc); bitstring(unsigned long val, size_t n) throw (xalloc); bitstring(const string& s) throw (xalloc); bitstring(const bitstring& b) throw (xalloc); ~bitstring(); // Conversions string to_string() const throw (xalloc); // Assignment bitstring& operator==(const bitstring& b) throw (xalloc); // Equality bool operator====(const bitstring& b) const; bool operator!==(const bitstring& b) const; // Basic bit operations bitstring& set(size_t n) throw (out_of_range); bitstring& set(size_t n, int val) throw (out_of_range); bitstring& set(); bitstring& reset(size_t n) throw (out_of_range); bitstring& reset(); bitstring& toggle(size_t n) throw (out_of_range); bitstring& toggle(); int test(size_t n) const throw (out_of_range); bool any() const; bool none() const; bitstring operator~() const; size_t count() const; // Bitwise operators bitstring& operator&==(const bitstring& b) throw (xalloc); bitstring& operator|==(const bitstring& b) throw (xalloc); bitstring& operator^==(const bitstring& b) throw (xalloc); // Shift operators bitstring& operator<<==(size_t n); bitstring& operator>>==(size_t n); bitstring operator<<(size_t n) const throw (xalloc); bitstring operator>>(size_t n) const throw (xalloc); // String operations bitstring& operator+==(const bitstring& b) throw (xalloc); bitstring& insert(size_t pos, const bitstring& b) throw (xalloc, = out_of_range); bitstring& remove(size_t pos, size_t n == NPOS) throw (xalloc, ou= t_of_range); bitstring& get_remove(bitstring& b, size_t pos, size_t n == NPOS) throw (xalloc, out_of_range); bitstring& replace(size_t pos, size_t n, const bitstring& b) throw (xalloc, out_of_range); size_t find(int val, size_t pos == 0) const; size_t rfind(int val, size_t pos == NPOS) const; bitstring substr(size_t pos, size_t n == NPOS) const throw (xalloc, out_of_range); size_t length() const; size_t resize(size_t n, int val == 0); size_t trim(); }; // Global functions ostream& operator<<(ostream& os, const bitstring& b); istream& operator>>(istream& is, bitstring& b) throw (xalloc); bitstring operator&(const bitstring& b1, const bitstring& b2) throw (= xalloc); bitstring operator|(const bitstring& b1, const bitstring& b2) throw (= xalloc); bitstring operator^(const bitstring& b1, const bitstring& b2) throw (= xalloc); bitstring operator+(const bitstring& b1, const bitstring& b2) throw (= xalloc); 3.1 Constructors Synopsis bitstring() bitstring(unsigned long n, size_t nbits) bitstring(const string& s) bitstring(const bitstring& b) 3.1.1 Constructor bitstring() throw (xalloc) Description Creates an empty bit string. 3.1.2 Constructor bitstring(unsigned long n, size_t nbits) throw (xa= lloc) Description Creates a bit string of length() >== nbits, initialized= with the bits of n. No significant bits are lost, i.e., this->length() ==== max(nbits, N+1= ), where N is the bit position of the highest-order 1-bit. If n ==== 0, then it creates t= he bit string "0". Pads with zeroes in the higher order bits if necessary to fill out nbits bi= ts. The common usage of this con- structor would be to initialize a bitstring of a certai= n length with zeroes, e.g., bitstring x(0,16); Care should be taken when using a non-zero value for in= itialization, since the bits will be "reversed". For example, the numeric bit pattern for= the number 21025 is 101001000100001, but the output from the following code bitstring x(21025); cout << x << endl; is 100001000100101. 3.1.3 Constructor bitstring(const string& s) throw (xalloc) Description Reads bit characters ('1's and '0's) from s until a non= -bit (non-white) character is en- countered. The first bit read is considered to be bit-0= . Exceptions Throws invalid_argument if any character in the string = is not a '1' or '0'. 3.1.4 Constructor bitstring(const bitstring& b) throw (xalloc) Description Copy Constructor. 3.2 Destructor ~bitstring() Description Frees resources and destroys the object. 3.3 Member Functions 3.3.1 Function string to_string() throw (xalloc) Description Creates a string of '1's and '0's representing the cont= ents of *this. The first (left-most) character is interpreted as bit-0. Returns The temporary string of '1's and '0's. 3.3.2 Function bitstring& operator==(const bitstring&) throw (xalloc= ) Description Standard assignment operator. Returns A reference to *this. 3.3.3 Function bool operator====(const bitstring& b) const Description Compares *this to b for equality. Two bitstrings are eq= ual if and only if they have the same number of bits and their bit patterns are iden= tical. Returns true if the bitsets are equal, false otherwise. 3.3.4 Function bool operator!==(const bitstring& b) const Description Compares *this to b for inequality. Two bitsets are equ= al if and only if they have the same number of bits and their bit patterns are iden= tical. Returns false if the bitsets are equal, true otherwise. 3.3.5 Functions set Synopsis bitstring& set(size_t n, int val == 1) bitstring& set() Description These functions set one or more bits. The function set(= size_t, int) can reset a bit, depending on val. 3.3.5.2 Function bitstring& set(size_t n, int val==1) throw (ou= t_of_range) Description Sets the nth bit if val is non-zero, otherwise r= esets the bit. If n ==== length(), then a bit is appended. Returns A reference to *this. Exceptions Throws out_of_range if n > length(). 3.3.5.3 Function bitstring& set() Description Sets all bits. Returns A reference to *this. 3.3.6 Functions reset Synopsis bitstring& reset(size_t n) bitstring& reset() Description These functions reset one or more bits. 3.3.6.1 Function bitstring& reset(size_t n) throw (out_of_range= ) Description Resets the nth bit. If n ==== length() a bit is = appended. Returns A reference to *this. Exceptions Throws out_of_range if n > length(). 3.3.6.2 Function bitstring& reset() Description Resets all bits. Returns A reference to *this. 3.3.7 Functions toggle Synopsis bitstring& toggle(size_t n) bitstring& toggle() Description These functions toggle one or more bits. 3.3.7.1 Function bitstring& toggle(size_t n) throw (out_of_rang= e) Description Toggles the nth bit. Returns A reference to *this. Exceptions Throws out_of_range if n >== length(). 3.3.7.2 Function bitstring& toggle() Description Toggles all bits. Returns A reference to *this. 3.3.8 Function int test(size_t n) const throw (out_of_range) Description Tests if bit-n is set. Returns 1 if the bit is set, 0 otherwise. Exceptions Throws out_of_range if n >== length(). 3.3.9 Function bool any() const Description Tests if any bits at all are set. Returns false if all bits are 0, true otherwise. =20 3.3.10 Function bool none() const Description Tests if no bits at all are set. Returns true if all bits are 0, false otherwise. 3.3.11 Function bits operator~() const Description Toggles all the bits of a copy of *this. Returns A toggled copy of *this. 3.3.12 Function size_t count() const Description Counts the number of bits that are set. Returns The number of 1-bits in the string. 3.3.13 Function bitstring& operator&==(const bitstring& b) throw (xal= loc) Description The current object is replaced with the bitwise-AND of = b and *this. Behaves as if the shorter bitstring is filled with zeroes on the right so= that the lengths of the two oper- ands are equal for the operation. The new length of the= object is the maximum of the lengths of the old object and b. Returns A reference to *this. 3.3.14 Function bitstring& operator|==(const bitstring& b) throw (xal= loc) Description The current object is replaced with the bitwise-OR of b= and *this. Behaves as if the shorter bitstring is filled with zeroes on the right so= that the lengths of the two oper- ands are equal for the operation. The new length of the= object is the maximum of the lengths of the old object and b. Returns A reference to *this. 3.3.15 Function bitstring& operator^==(const bitstring& b) throw (xal= loc) Description The current object is replaced with the bitwise-XOR of = b and *this. Behaves as if the shorter bitstring is filled with zeroes on the right so= that the lengths of the two oper- ands are equal for the operation. The new length of the= object is the maximum of the lengths of the old object and b. Returns A reference to *this. 3.3.16 Function bitstring& operator>>==(size_t n) Description Shifts *this right destructively n bit positions. If n = > length(), then all bits are reset. Shifting "right" by n means that bit-n receives the val= ue of bit-0, bit-(n+1) receives bit-1, etc. (NOTE: because of the left-to-right ordering of th= e bits in a bitstring, this is "backwards" from the bitwise semantics of unsigneds, bu= t is visually correct). Returns A reference to *this. 3.3.17 Function bitstring& operator<<==(size_t n) Description Shifts *this left destructively n bit positions. If n >= length(), then all bits are reset. Shifting "left" by n means that bit-0 receives the valu= e of bit-n, bit-1 receives bit-(n+1), etc. (NOTE: because of the left-to-right ordering of th= e bits in a bitstring, this is "backwards" from the bitwise semantics of unsigneds, bu= t is visually correct). Returns A reference to *this. 3.3.18 Function bitstring operator>>(const bitstring& b, size_t n) co= nst throw (xalloc) Description Shifts b right non-destructively by n bit positions. (S= ee 3.1.30). Returns The shifted result in a temporary bitstring. 3.3.19 Function bitstring operator<<(const bitstring& b, size_t n) co= nst throw(xalloc) Description Shifts b left non-destructively by n bit positions. (Se= e 3.1.31). Returns The shifted result in a temporary bitstring. 3.3.20 Function bitstring& operator+==(const bitstring& b) throw (xal= loc) Description Appends b destructively to *this. length() ==== old_th= is->length() + b.length(). Returns A reference to *this. 3.3.21 Function bitstring& insert(size_t pos, const bitstring& b) throw (xalloc, out_of_range) Description Inserts b into *this starting at bit position pos. The = bits of *this starting at pos follow the inserted copy of b. Appends b if pos ==== length(). Returns A reference to *this. Exceptions Throws out_of_range if pos > length(). 3.3.22 Function bitstring& remove(size_t pos, size_t n == NPOS) throw (xalloc, out_of_range) Description Removes up to n bits from *this starting at bit positio= n pos. If length() - pos < n, the bitstring is truncated at position pos inclusive. Returns A reference to *this. Exceptions Throws out_of_range if pos >== length(). 3.3.23 Function bitstring& get_remove(bitstring& b, size_t pos, size_t n= == NPOS) throw (xalloc, out_of_range) Description Removes up to n bits from *this starting at bit positio= n pos. If length() - pos < n, the bitstring is truncated at position pos inclusive. T= he removed bits become the new bit pattern of b. Returns A reference to *this. Exceptions Throws out_of_range if pos >== length(). 3.3.24 Function bitstring& replace(size_t pos, size_t n, const bitstr= ing& b) throw (xalloc, out_of_range) Description Equivalent to a remove followed by a replace in the obv= ious way. Included for conve- nience and efficiency. Returns A reference to *this. Exceptions Throws out_of_range if pos >== length(). 3.3.25 Function size_t find(int val, size_t pos == 0) const Description Searches forward starting from position pos (inclusive)= for the first occurrence of a 0-bit (if val is zero) or a 1-bit (if val is non-zero). Returns The found bit position, if the search was successful, N= POS otherwise. Exceptions Throws out_of_range if pos >== length(). 3.3.26 Function size_t rfind(int val, size_t pos == NPOS) const Description Searches backwards from position pos (or from position = length()-1 if pos ==== NPOS) for the first occurrence of a 0-bit (if val is zero) or= a 1-bit (if val is non-zero). Returns The found bit position, if the search was successful, N= POS otherwise. Exceptions Throws out_of_range if pos > length(). 3.3.27 Function bitstring substr(size_t pos, size_t n == NPOS) const throw (xalloc, out_of_range) Description Creates a new bitstring consisting of the bit pattern f= ound starting at position pos. Up to n bits or until the end of the string are copied.= If n ==== NPOS, the bits up to the end of the string are copied. If pos ==== length(), an = empty bitstring is created. Returns The new bitstring. Exceptions Throws out_of_range if pos > length(). 3.3.28 Function size_t length() const Description Determines the number of bits in the string. Returns The number of bits. 3.3.29 Function size_t resize(size_t n, int val == 0) const throw(xal= loc) Description Resizes (either truncates or expands) the object so tha= t this->length() ==== n. In the case that the length increases, the object is extended = on the right with '0's if val ==== 0 or with '1's otherwise. Returns The old length(). 3.3.30 Function bitstring& trim() Description Truncates high-order zero bits. If N is the highest-num= bered 1-bit, then this->length() becomes N+1. Returns A reference to *this. 3.4 Global Functions 3.4.1 Function ostream& operator<<(ostream& os, const bitstring& b) Description Sends the sequence of '1's and '0's that corresponds to= b to the output stream os. Returns A reference to the stream os. 3.4.2 Function istream& operator>>(istream& is, bitstring& b) throw = (xalloc) Description Reads a contiguous sequence of '1's and '0's from a str= eam into b. The first bit read is considered to be bit-0. The first non-bit (non-white) c= haracter terminates the read and remains in the stream. Sets is.failbit if the first (no= n-white) character is not a '1' or '0'. Returns A reference to the stream is. 3.4.3 Function bitstring operator&(const bitstring& b1, const bitstr= ing& b2) throw (xalloc) Description Computes the bitwise-AND of b1 and b2. The length of th= e result is the length of the longer of the two operands. Behaves as if, prior to the= operation, the shorter operand is extended with high-order zero bits until its length equ= als that of the longer operand. Returns The result of the bitwise-AND in a temporary bitstring. 3.4.4 Function bitstring operator|(const bitstring& b1, const bitstr= ing& b2) throw (xalloc) Description Computes the bitwise-OR of b1 and b2. The length of the= result is the length of the longer of the two operands. Behaves as if, prior to the= operation, the shorter operand is extended with high-order zero bits until its length equ= als that of the longer operand. Returns The result of the bitwise-OR in a temporary bitstring. 3.4.5 Function bitstring operator^(const bitstring& b1, const bitstr= ing& b2) throw (xalloc) Description Computes the exclusive-OR of b1 and b2. The length of t= he result is the length of the longer of the two operands. Behaves as if, prior to the= operation, the shorter operand is extended with high-order zero bits until its length equ= als that of the longer operand. Returns The result of the exclusive-OR in a temporary bitstring= . 3.4.6 Function bitstring operator+(const bitstring& b1, const bitstr= ing& b2) throw (xalloc) Description Appends b non-destructively to *this. result.length()= ==== b1.length() + b2.length(). Returns The result of the concatenation in a temporary bitstrin= g.