/* 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. 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. 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) { char *x = malloc(capacity/8 + 1); memset(x, 0, capacity/8 + 1); return x; } void add_to_set(char* s, int digit) { s[digit>>3] = (1<<(digit & 7)) | s[digit>>3]; } int is_in_set(char* s, int digit) { return !!(s[digit>>3] & (1<<(digit & 7))); } 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; }