Bit Vectors in C

File Overview

The original code is © copyright 1995 by Miller Freeman, Inc.

Description

ANSI C functions to create and manipulate arrays of bits, i.e. bit vectors. Functions to: dynamically create arrays, access (read and write) elements; convert from numbers to bit vectors and bit vectors to strings. Additional mathematical functions (union, intersection, complement, number of set bits) are provided that are more efficient than naïve implementations.

The module was designed to be robust enough to work with machines of different word sizes. Only a couple of minor changes are required to change it from using unsigned char for `bits' to another integral type. See ba_init() and the definition of BITS_SZ for details.

Only minimal optimization has been attempted.

Author

James Blustein <jamie@csd.uwo.ca>

Notes

A version of this code appeared in Dr. Dobb's Journal #233 (August 1995) Volume 20 Issue 8 in an article entitled Implementing Bit Vectors in C by James Blustein. The article is on pages 42, 44 and 46. The original code is on pages 96, 98-100.

The code at the DDJ FTP site (and, presumably, on the diskette) is incorrect and not as published. I told them about it when the article was first published but, as of one year later, nothing has changed.

My address has changed since the publication in DDJ. Please do not send mail to <jamie@uwo.ca> anymore. Instead use <jamie@cs.dal.ca>.

Source Code

This bitvector code consists of three files:

types.h (about 1 Kb)

Definitions of the variable types used in the other files.

bitarr.c (about 24 Kb)

Functions that encapsulate an implementation of a bitvector abstract data type.

bitarr.h (about 2 Kb)

Function prototypes for the functions in bitarr.c that have external linkage.

The original code is (c) copyright 1995 by Miller Freeman, Inc.

Updates

changes.html

List of changes to the code since publication.

New.html

New code and pointers to related resources.

SeeAlso.html

shortcut to the pointers to related resources at other sites