Bit Vectors in C

  • File Overview
  • Source Code
  • Updates
  • 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

    J. Blustein
    Faculty of Computer Science Department,
    Dalhousie University
    Halifax, Nova Scotia B3H 1W5
    Canada

    E-mail: <jamie@cs.dal.ca>