bitset

How can I implement sets or arrays of bits?

Use arrays of char or int, with a few macros to access the desired bit in the proper cell of the array. Here are some simple macros to use with arrays of char:
#include /* for CHAR_BIT */

#define BITMASK(b) (1 << ((b) % CHAR_BIT)) #define BITSLOT(b) ((b) / CHAR_BIT) #define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b)) #define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b)) #define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b)) #define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT) (If you don't have , try using 8 for CHAR_BIT.)

Here are some usage examples. To declare an ``array'' of 47 bits:
char bitarray[BITNSLOTS(47)];

To set the 23rd bit:

BITSET(bitarray, 23);

To test the 35th bit:

if(BITTEST(bitarray, 35)) ...

To compute the union of two bit arrays and place it in a third array (with all three arrays declared as above):
for(i = 0; i <>
#include

#define MAX 10000

int main()
{
char bitarray[BITNSLOTS(MAX)];
int i, j;

memset(bitarray, 0, BITNSLOTS(MAX));

for(i = 2; i < j =" i">

How can I manipulate individual bits??

Bit manipulation is straightforward in C, and commonly done. To extract (test) a bit, use the bitwise AND (&) operator, along with a bit mask representing the bit(s) you're interested in:
value & 0x04
To set a bit, use the bitwise OR (| or |=) operator:

value |= 0x04

To clear a bit, use the bitwise complement (~) and the AND (& or &=) operators:
value &= ~0x04

(The preceding three examples all manipulate the third-least significant, or 2**2, bit, expressed as the constant bitmask 0x04.)
To manipulate an arbitrary bit, use the shift-left operator (<<) to generate the mask you need:

value & (1 << bitnumber)
value |= (1 << bitnumber)
value &= ~(1 << bitnumber)

Alternatively, you may wish to precompute an array of masks:

unsigned int masks[] =
{0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80};

value & masks[bitnumber]
value |= masks[bitnumber]
value &= ~masks[bitnumber]

To avoid surprises involving the sign bit, it is often a good idea to use unsigned integral types in code which manipulates bits and bytes.

What is a good data structure to use for storing lines of text?

Q: What's a good data structure to use for storing lines of text? I started to use fixed-size arrays of arrays of char, but they're just too restrictive.

A: One good way of doing this is with a pointer (simulating an array) to a set of pointers (each simulating an array) of char. This data structure is sometimes called a ``ragged array,'' and looks something like this:
[FIGURE GOES HERE]
You could set up the tiny array in the figure above with these simple declarations:
char *a[4] = {"this", "is", "a", "test"};
char **p = a;

(where p is the pointer-to-pointer-to-char and a is an intermediate array used to allocate the four pointers-to-char).
To really do dynamic allocation, you'd of course have to call malloc:
#include
char **p = malloc(4 * sizeof(char *));
if(p != NULL) {
p[0] = malloc(5);
p[1] = malloc(3);
p[2] = malloc(2);
p[3] = malloc(5);

if(p[0] && p[1] && p[2] && p[3]) {
strcpy(p[0], "this");
strcpy(p[1], "is");
strcpy(p[2], "a");
strcpy(p[3], "test");
}
}

(Some libraries have a strdup function which would streamline the inner malloc and strcpy calls. It's not Standard, but it's obviously trivial to implement something like it.)
Here is a code fragment which reads an entire file into memory, using the same kind of ragged array.
#include
#include
extern char *agetline(FILE *);
FILE *ifp;

/* assume ifp is open on input file */

char **lines = NULL;
size_t nalloc = 0;
size_t nlines = 0;
char *p;

while((p = agetline(ifp)) != NULL) {
if(nlines >= nalloc) {
nalloc += 50;
#ifdef SAFEREALLOC
lines = realloc(lines, nalloc * sizeof(char *));
#else
if(lines == NULL) /* in case pre-ANSI realloc */
lines = malloc(nalloc * sizeof(char *));
else lines = realloc(lines, nalloc * sizeof(char *));
#endif
if(lines == NULL) {
fprintf(stderr, "out of memory");
exit(1);
}
}

lines[nlines++] = p;
}

How can I ensure that integer arithmetic doesnt overflow?

The usual approach is to test the operands against the limits in the header file before doing the operation. For example, here is a ``careful'' addition function:

int
chkadd(int a, int b)
{
if(INT_MAX - b < a) {
fputs("int overflow\n", stderr);
return INT_MAX;
}
return a + b;
}

Why doesnt sizeof properly report the size of an array

Q: Why doesn't sizeof properly report the size of an array when the array is a parameter to a function? I have a test routine
f(char a[10])
{
int i = sizeof(a);
printf("%d\n", i);
}

and it prints 4, not 10.

A: The compiler pretends that the array parameter was declared as a pointer (that is, in the example, as char *a; , and sizeof reports the size of the pointer.