Bit Vectors in C

Change Log

This is a record of changes to the code since its publication in Dr. Dobb's Journal #233 (August 1995) Volume 20 Issue 8.

bitarr.c

25 July 1995

CANONIZE macro

The new version is

#define CANONIZE(Array,NumInts,NumElem) \
   (Array)[NumInts - 1] &= (bit)~0 >> (BITS_SZ - ((NumElem % BITS_SZ)   \
                                                  ? (NumElem % BITS_SZ) \
                                                  : BITS_SZ));

ba_count()

Replaced
if (8 == BITS_SZ)
with
if (bitcount[(sizeof bitcount / sizeof bitcount[0]) - 1] == BITS_SZ)
, i.e. replaced the `magic number' 8 with a computed constant.

The last element of the array represents the count of bits that are 1 in the largest integer that can be encoded by type `bit'. That integer will have all of its bits 1. Therefore, the count of 1s in that integer will be how many bits are in the type `bit'. The sizeof expression evaluates to the last element of the array.

31 August 1995

ba_value()

Replaced
return(arr[elem / BITS_SZ] & (1 << (elem % BITS_SZ)));
with
return( (arr[elem / BITS_SZ] & (1 << (elem % BITS_SZ))) ?TRUE: FALSE );.

This is on the advice of Geir Horn <Geir.Horn@si.sintef.no>. The change does not affect ANSI C implementations but might have an impact on some other compilers.

26 January 1996

NELEM macro

Frans F.J. Faase <faase@cs.utwente.nl> suggested that the macro would be more efficent as
((N + BITS_SZ - 1)/BITS_SZ) (In C, division of positive integers truncates.)

(See 8 Jan 1999 for new address.)

10 March 1996

ba_count()

Replaced
for (count = 0L; i < size; i++)
with
for (count = 0L, i = 0; i < size; i++)

Otherwise the variable i is uninitialized in the second loop. My thanks to Dan Pop <danpop@mail.cern.ch> for telling me that the gcc compiler needs a -O switch to enable all the error checking of -Wall. Curiously, the Solaris distribution of lint didn't catch the error.

20 July 1996

Including proper headers

malloc() should properly be defined in <stdlib.h> not <malloc.h>. Furthermore, although the article referred to <limits.h> it was not included in the code. The cast of malloc in ba_b2str() is unnecessary.

13 August 1996

Better BITS_SZ definition

It occurred to me today that (sizeof bit) * (CHAR_BIT) would be exactly the number of bits in each variable of bit type. I don't know why I didn't think of it before -- it seems obvious. If the changes were made then the code would be independent of the type used (as long as it is one of the unsigned integral types).

8 January 1999

New address for Frans F.J. Faase

Frans F.J. Faase's new address is <Frans_LiXia@wxs.nl>

(See 26 January 1996 for original citation.)

Changes not made yet

1. #define BITS_SZ (CHAR_BIT)

   (sizeof bit) * (CHAR_BIT) is more versatile.

2. elem_t BITS_SZ = 0

   BITS_SZ should be static (because: (a) it would be like the #ifdef version; and (b) the symbol should not be external anyway.)

3. casts of calloc() and malloc() are unnecessary and set a bad example.

4. further encapsulation

   I think a combination of this code and its wrapper (see the comment at the top of bitarr.c) would be good examples of the method I demonstrate in my Using C to Encapsulate an Abstract Data Type page.

5. return (arr); /* etc. */

   My programming style has changed since I wrote the code. I no longer use parens that make return look like a function when it is not required. About the most minor matter of style there can be.