Chuck Allison is a regular columnist withand a software architect for the Family History Department of the Church of Jesus Christ of Latter Day Saints Church Headquarters in Salt Lake City. He has a B.S. and M.S. in mathematics, has been programming since 1975, and has been teaching and developing in C since 1984. His current interest is object-oriented technology and education. He is a member of X3J16, theCUJStandards Committee. Chuck can be reached on the Internet at allison@decus.org, or at (801)240-4510.ANSI C++## The

The standard C++ library has two classes for bit manipulation:Class Templatebitsbitstringandbits. Last month I discussed thebitstringclass, which defines objects that behave like an array of bits that expands or contracts according to your needs. This month's installment explains thebitsclass, an abstraction which extends C's bitwise semantics by allowing easy access to bits, by allowing an arbitrary (but fixed) number of bits in a bitset, and by adding important new functionality. Following last month's format, I present here an excerpt from the official proposal accepted by the standards committee, a working implementation, and examples of how to use the class.Class

bitsaccommodates a fixed-length collection of bits. You can think of abitsobject as an arbitrarily large unsigned integer. It is actually a class template, with the number of bits in the collection as the template parameter. (See the sidebar "Templates in a Nutshell.") It is highly suitable for interfacting with the host operating system, and is designed for efficiency. (It can be stack-based.) Here's a sample program run on a machine with 16-bit integers:

// tbits.cpp: // Set some bits and display the result #include <iostream.h> #include <stddef. h> #include <limits.h> #include "bits.h" main() { const size_t SIZE = CHAR_BIT * sizeof(int); bits<SIZE> flags; enum open_mode {in, out, ate, app, trunc, binary}; 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: 0000000000100001 (0x21) binary? yes## Member Function Descriptions

This section is a modified excerpt from the official proposal which describes the semantics of each member function. For a quick look at the class interface, see Listing 6. Since the library group of the joint C++ standards committee is still deciding how to integrate exceptions into the standard library, I just mention them briefly here. The names and uses of exceptions are subject to change. I useassertsin place of exceptions in the implementation (see Listing 7) .

## 1.0 Constructors

## Synopsis

bits()bits(unsigned long n)bits(const string& s)bits(const bits<N>& b)## 1.1 Constructor

bits()## Description

Initializes all bits to zero.

## 1.2 Constructor

bits(unsigned long n)## Description

Initializes the object with thebits of n. If N >sizeof(unsigned long) * CHAR_BIT, sets the extra bits to zero.

## 1.3 Constructor

)bits(const string& s## Description

Each character ofsis interpreted as a bit (a string of1s and0s is expected). In typical integral fashion, treats the last (right-most) character ofsasbit 0.

## Exceptions

Throwsinvalid_argumentif a character other than1or0is encountered.

## 1.4 Constructor

bits(const bits<N>& b)## Description

Standardcopyconstructor.

## 2.0 Destructor

No destructor required.

## 3.0 Other Member Functions

## 3.1 Function

unsigned short to_ushort() const## Description

Converts thenleast significant bits of*this(wheren == sizeof(unsigned short) * CHAR_BIT) to an unsignedshort. This is useful when the bits represent flags in a word passed to the operating system.

## Exceptions

ThrowsoverflowifN>nand any of the bits above positionn-1are set.

## 3.2 Function

unsigned long to_ulong() const## Description

Converts thenleast significant bits of*this(wheren == sizeof(unsigned long) * CHAR_BIT) to an unsignedlong.

## Exceptions

ThrowsoverflowifN > nand any of the bits above positionn-1are set.

## 3.3 Function

string to_string() const## Description

Creates a string of1s and0s representing the contents of*this. As with unsigned integers, treats the last character as bit0.

## Returns

The temporary string of1s and0s.

## 3.4 Function

bits<N>& operator:(const bits<N>& b)## Description

Standard assignment operator.

## Returns

A reference to*this.

## 3.5 Function

int operator==(const bits<N>& b) const## Description

Compares*thistobfor equality. Two bitsets are equal if and only if their bit patterns are identical.

## Returns

Non-zero if the bitsets are equal, zero otherwise.

## 3.6 Function

int operator!=(const bits<N>& b) const## Description

Compares*thistobfor inequality. Equivalent to!operator==().

## Returns

Zero if the bitsets are equal, non-zero otherwise.

## 3.7 Functions

set## Synopsis

bits<N>& set(size_t n, int val = 1)bits<N>& set()## Description

These functions set one or more bits. The functionset(size_t, int)can reset a bit, depending onval.

## 3.7.1 Function

bits<N>& set[size_t n, int val)## Description

Sets thenthbit ifvalis non-zero, otherwise resets the bit.

## Returns

A reference to*this.

## Exceptions

Throwsout_of_rangeifnis not in[0,N-1].

## 3.7.2 Function

bits<N>& set()## Description

Sets all bits.

## Returns

A reference to*this.

## 3.8 Functions

reset## Synopsis

bits<N>& reset(size_t n) bits<N>& reset()## Description

These functions reset one or more bits.

## 3.8.1 Function

bits<N>& reset(size_t n)## Description

Resets thenthbit.

## Returns

A reference to*this.

## Exceptions

Throwsout_of_rangeifnis not in[0, N-1].

## 3.8.2 Function

bits<N>& reset()## Description

Resets all bits.

## Returns

A reference to*this.

## 3.9 Functions

toggle## Synopsis

bits<N>& toggle(size_t n) bits<N>& toggle()## Description

These functions toggle one or more bits.

## 3.9.1 Function

bits<N>& toggle(size_t n)## Description

Toggles thenthbit.

## Returns

A reference to*this.

## Exceptions

Throwsout_of_rangeifnis not in[0,N-1].

## 3.9.2 Function

bits<N>& toggle()## Description

Toggles all bits.

## Returns

A reference to*this.

## 3.10 Function

bits operator~() const## Description

Toggles all the bits of a copy of*this.

## Returns

A toggled copy of*this.

## 3.11 Function

int test(size_t n) const## Description

Tests if bitnis set.

## Returns

Non-zero if the bit is set, zero otherwise.

## Exceptions

Throwsout_of_rangeifnis not in[0,N-1].

## 3.12 Function

int any() const## Description

Tests if any bits at all are set.

## Returns

0if all bits are0, non-zero otherwise.

## 3.13 Function

int none() const## Description

Tests if no bits at all are set.

## Returns

Non-zero if all bits are0, 0otherwise.

## 3.14 Function

bits<N>& operator&=(const bits<N>& b)## Description

Performs a destructivebitwise-ANDofbinto*this.

## Returns

A reference to*this.

## 3.15 Function

bits<N>& operator/=(const bits<N>& b)## Description

Performs a destructivebitwise-ORofbinto*this.

## Returns

A reference to *this.

## 3.16 Function

bits<N>& operator^=(const bits<N>& b)## Description

Performs a destructive bitwiseexclusive-ORofbinto*this.

## Returns

A reference to*this.

## 3.17 Function

bits<N>& operator>>=(size_t n)## Description

Shifts *thisright destructively (i.e., in place) bynbit positions. Resets all bits ifn > N. To shift "right" bynmeans that bit0receives the value of bitn, bit1receives bit(n+1), etc.

## Returns

A reference to *this.

## 3.18 Function

bits<N>& operator<<=(size_t n)## Description

Shifts *thisleft destructively bynbit positions. Resets all bits ifn>N. To shift "left" bynmeans that bitnreceives the value of bit0, bit(n+1)receives bit1, etc.

## Returns

A reference to *this.

## 3.19 Function

bits<N> operator>>(size_t n) const## Description

A non-destructive version ofoperator>>=().

## Returns

The results of the shift in a temporarybitsobject.

## 3.20 Function

bits<N> operator<<(size_t n) const## Description

A non-destructive version ofoperator<<=().

## Returns

The results of the shift in a temporarybitsobject.

## 3.21 Function

size_t count( ) const## Description

Counts the number of bits that are set.

## Returns

The number of1bits in*this.

## 3.22 Function

size_t length( ) const## Description

Returns the fixed-size length of the object.

## Returns

N.## 4.0 Global Functions

## 4.1 Function

ostream& operator<<(ostream& os, const bits<N>& b)## Description

Sends a sequence ofN 1s and0s corresponding to the bit pattern of*thisto the streamos,

## Returns

A reference to the streamos.

## 4.2 Function

istream& operator>>(istream& is, bits<N>& b)## Description

Reads a sequence of up toN 1s and0s from the streamis,after skipping whitespace. The first non-bit character thereafter terminates the read and remains in the stream. The corresponding bit pattern is reproduced inb. Treats the last1or0read from the stream as bit0ofb.

## Returns

A reference to the streamis.

## 4.3 Function

bits<N>operator& (const bits<N>& b1, const bits<N>& b2)## Description

Performs abitwise-ANDofb1andb.

## Returns

The results of thebitwise-ANDin a temporarybitsobject.

## 4.4 Function

bits<N>operator / (const bits<N>& b1, const bits<N>& b2)## Description

Performs abitwise-ORofb1andb.

## Returns

The results of thebitwise-ORin a temporarybitsobject.

## 4.5 Function

bits <N> operator^ (const bits<N>& b1, const bits<N>& b2)## Description

Performs a bitwiseexclusive-ORofb1andb.

## Returns

The results of theexclusive-ORin a temporarybitsobject.

## Design Notes

Having an expression instead of a type as a template parameter has the following effects:

Since a

- A
bits-object can be stack-based, since its size is known at compile time. This means less run-time overhead and therefore better performance thanbitstringobjects.- Objects of different sizes (i.e., with a different number of bits) are different types, and therefore can't be combined in operations.
- No global functions taking
bitsarguments are allowed under the current definition of the language unless you define them inline in the class definition. The standards committee is working to fix this. See the sidebar, "Templates in a Nutshell," for more detail.bitsobject is an extension of unsigned integers as far as bitwise operations are concerned, a collection of bits behaves like a number, in that bit0is the right-most bit. To be consistent with C bitwise operations, the statements

bits<8> b; b | = 5; cout << b << endl;give the result

00000101that is, the bits of5areORed withb(via the constructorbits(unsigned long)).As you can see in Listing 7, I've taken some liberties in the implementation of this class by changing the type of the template parameter to a

size_t. The reason for originally making the number of bits anunsigned longwas to guarantee a minimum size across platforms (the ANSI C standard states that anunsigned longmust be at least 32 bits wide). However, this would require thatcountandlengthreturn anunsigned long. As proof that this is unnatural, I offer the fact that I forgot to do so (the functions return asize_tbecause it "feels right") and no one on the committee noticed. (Actually, Bill Plauger finally noticed while he was editing the standard library documents, but that was four months after thebitsclass became official.) Furthermore, the corresponding functions in thestringandbitstringclasses also return asize_t. (They have no choice.) To be consistent with these classes, therefore, and because it just makes sense, I shall propose to the committee that we approve the obvious and make the template parameter asize_t.I'm also thinking of changing the name from

bitstobitset. This would allow you to refer to an object as a "bitset" instead of always having to say a "bitsobject." (Who would ever call it a "bits"?) And one could argue that the functionto_ushort( )is superfluous, since it is equivalent to(unsigned short) to_ulong( ).

## Implementation Notes

The Code Capsule "Bit Handling in C" (CUJ, November, 1993) provides a thorough explanation of the internals of using an integral array to store and access individual bits, so I won't repeat it here. The techniques found therein serve both thebitstringandbitsclasses. The implementation of thestringclass is in last month's installment ("Bit Handling in C++, Part 1,"CUJ, December 1993). Listing 8 has a test program that exercises most of the member functions of thebitsclass.

## Sets of Integers

For those of you who miss some of the high-level features of Pascal and Modula-2, thebitsclass gives you sets of integers almost for free. Just define abitsobject of a size appropriate for your application and do the following:

For theoperation: Do this:set

insert x into sIf this still seems too "low-level," it is a trivial matter to define a set-like interface to thes. set(x)remove x from ss. reset(x)x member of s?s. test(x)complement of ss. toggle() or ~ss1 + s2 (union)s1 / s2s1 * s2 (intersection)s2 & s2s1 - s2 (difference) see below s1 <= s2 (subset) see below s1 >= s2 (superset) see belowbitsclass. Listing 9 defines a class template calledIntsetthat has all the basicsetoperations along with anostreaminserter. The only operations that take any thought at all (but only very little) areset differenceandsubset. To remove froms1the elements ofs2, just reset ins1the bits that are set ins2:

s1.bitset &= ~s2.bitset; // see Intset<N>::operator-Ifs1is a subset ofs2, thens1is nothing more nor less than the intersection of the two sets:

s1 == s1 & s2 // true iff s1 <= s2The test program in Listing 10 shows how to use theIntsetclass.

## Conclusion

The acceptance of these two bit handling classes by the C++ standards committee shows that the needs of the system programmer have not been forgotten. Much of the hullabaloo over object-oriented technology emphasizes inheritance hierarchies of polymorphic, high-level abstract data types. These concepts are best left to specialized libraries and applications while the standard rightly focuses on commonly needed, low-level abstractions. If you have any comments on these classes, please contact me at the email address in the by-line at the bottom of the first page of this article.