/* 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 <stdio.h>
#include <stdlib.h>
#include <string.h>

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;
}