Bit Vectors in C

What's New

Some other bit vector resources

  • C
  • C++
  • Arbitary Precision Numbers (BIGNUMs)
  • General Applications
  • Note: Unlike some of my other webpages this list does not contain any recommendations. I am collecting links to resources that I hope others will find helpful, but I do not carefully review all of the entries here.

    C Specific

    Proposal for Big Int Extension to C
    Dated 7 Feb 1995, a suggestion about how to include support for arbitrarily large integers in C.
    Some articles from the comp.lang.c* newsgroups
    A few articles that looked interesting to me. I have not given them the attention I think they deserve. The Usenet section of my bookmarks list should help you find other articles of interest.
    Bit::Vector
    A perl module with a C core. The module sounds most impressive and the C core can be used separately from the perl part. I have a copy of the announcement of the module. The announcment provides some description of the module. (6 March 1998, URLs updated 9 & 10 March 1998)
    Set of Integers Example in C: A Reference Manual
    The second and fourth editions include excellent code by Guy Steele that shows how to use C's unsigned types to represent sets and subsets. That code appears in section 7.6.7 (on pages 212 - 216) of the fourth edition. (A note in the fourth edition says that some of the code was adapted from HAKMEM. Because I have not read the second edition I can not say anything about it. I learned about the code in the second edition from a comment on page xvii of the fourth edition.)

    C++ Specific

    Description of Bit Vector part of SUIF Library
    `The SUIF compiler system is a flexible framework for advanced compiler research. The primary design goal for this compiler is that it be easy to use and build upon, without sacrificing its ability to compile real-world benchmark programs. Compared to other publicly-available compilers, SUIF may be somewhat inefficient and less robust, but it is much easier to modify and extend. This makes it an ideal platform for evaluating new compiler techniques.'
    (11 July 1996)
    HomeBrew BitVector C++ Class
    `HomeBrew was developed to provide a useful library of C++ classes for CAD projects. It is the brainchild of Andrew Seawright. Over the years many users have contributed to HomeBrew.'
    (11 July 1996)
    BitVec Class of GMD SIR/CASTLE System
    `SIR/CASTLE is the prototype platform for hardware/software codesign currently being under development at GMD within the research project SYDIS'
    (11 July 1996)
    A Class for Representing Large Integers
    In C/C++ Users Journal (Nov. 1996, Vol. 14, No. 11, pp. 61 - 68) Anthony Breitzman <brietzCHI@aol.com> wrote about a space-efficent representation for large integers. The code appears to be based on algorithms by Knuth, but I'm not sure.
    (24 Oct 1996)
    (CUG 463) Linteger: Arbitrary Precision Integer Class Lib

    Leonard Janke (University of British Columbia, Vancouver) contributes LInteger, a C++ library that empowers you to create and perform arithmetic on objects representing nearly arbitrary precision integers. Thanks to C++ support for operator overloading, the use of the large integers in this library should be nearly as easy as the use of regular int types. In many cases, converting your application to use LInteger can be as simple as substituting "LInteger" for "int" in your editor.

    The current version of this library requires Intel 386 or better CPU and is only guaranteed to compile perfectly with GNU C++. Though Linteger has only been tested on Linux, Janke predicts it should work with OS/2 or Windows NT. He has coded the multiprecision methods in assembly language for speed. Multiplication can be performed via recursion or Montgomery style. Linteger includes documentation in HTML for public methods. This library is free for both commercial and non-commercial use. LInteger v0.1 as released on 9/2/96 is now available on the CUG CD-ROM


    (5 Dec 1996)

    BIGNUMs

    Most of the comments I get about the code refer to arbitary precision integers (aka BIGNUMs) This section is for references to BIGNUM code whether or not they use of bit vectors.

    General Applications

    Abstract & Review: An efficient representation for sparse sets
    An abstract and review of an article in ACM Letters on Programming Languages and Systems vol.2, no. 1-4 (March-Dec. 1993) pp. 59-69.

    http://www.cs.dal.ca/~jamie/pubs/code/BitVectors/SeeAlso.html
    James Blustein <jamie@cs.dal.ca>