/* Suppose that we want to represent sets of integers where:
* Integers in the set are always between 0 and N-1 for some N.
* We expect the set to typically have many members.
Instead of represeting the set as, say, an array of integers
that are in the set, we can represent the set as an array
of *bits*. An empty set is all 0 bits. A set with the `i`th
bit as 1 means that `i` is in the set, and a set with the `i`th
bit as 0 means that `i` is in the set.
The set {1, 5} using 8 bits:
7 6 5 4 3 2 1 0 <- bit position
-----------------
|0|0|1|0|0|0|1|0| <- bits
-----------------
The set {0, 3, 7} using 8 bits:
7 6 5 4 3 2 1 0 <- bit position
-----------------
|1|0|0|0|1|0|0|1| <- bits
-----------------
If N was always 64 or less, we could just use an integer. But
for large N, we'll have to allocate a general array of bytes,
and to find the right bit, we'll have to first find the right
byte --- and then the bit within the byte.
The set {5, 12} using 16 bits, which is 2 bytes:
0 1 <- byte index
,-------------. ,-------------.
7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 <- bit within byte
----------------- -----------------
|0|0|1|0|0|0|0|0| |0|0|0|1|0|0|0|0| <- bits
----------------- -----------------
7 6 5 4 3 2 1 0 1 1 1 1 1 1 9 8 <- overall bit value
5 4 3 2 1 0
For example, a set of numbers between 0 and 1029 will need
129 bytes, and adding the number 42 to the set will be
represented (not by putting a "42" anywhere, but) by setting
the 42nd bit --- that is, the 3rd bit of the 6th bytes (i.e.,
the bit at index 2 within the byte at index 5, since 42/8 = 5
and 42%8 = 2). */
#include
#include
#include
char * make_empty_bit_set(int capacity)
{
return (char*)calloc(1, capacity/8 + 1);
/* Or:
char *p;
p = (char*)malloc(capacity/8 + 1);
memset(p, 0, capacity/8 + 1);
return p;
*/
}
void add_to_set(char* s, int digit)
{
s[digit>>3] = s[digit>>3] | (1 << (digit%8));
}
int is_in_set(char* s, int digit)
{
return s[digit>>3] & (1 << (digit%8));
}
int main()
{
char *s = make_empty_bit_set(1029);
add_to_set(s, 75);
printf("45 in set? %d\n", is_in_set(s, 45));
printf("75 in set? %d\n", is_in_set(s, 75));
return 0;
}