Minimal bitset implementation.

simple_bitset.cpp

#include <stdio.h>

#define BIT_SHIFTCNT   (5)
#define BIT_CNT        (1 << BIT_SHIFTCNT)
#define BIT_MASK       (BIT_CNT - 1)

// This code implementation is for learning purpose
// on how to perform bit masking with any bit length,
// and for snippet.
// Use at your own risk.


struct bitset
{
  int * B;
  int sz;
  bitset(int bit)
  {
    // divide by 32
    sz = (bit >> BIT_SHIFTCNT) + 1;
    B = new int[sz];
    for(int i = 0; i < sz; ++i)
      B[i] = 0;
  }

  bitset(const bitset * other)
  {
    sz = other->sz;
    B = new int[sz];
    for(int i = 0; i < sz; ++i)
      B[i] = other->B[i];
  }

  ~bitset()
  {
    delete[] B;
  }

  int get(int pos)
  {
    // mod by 32, remainder
    const int bitPos = pos & BIT_MASK;
    // divice by 32, locate array index
    const int arrPos = pos >> BIT_SHIFTCNT;
    // return the bit located at pos
    return (B[arrPos] & (1 << bitPos)) != 0;
  }

  void set(int pos)
  {
    // mod by 32, remainder
    const int bitPos = pos & BIT_MASK;
    // divice by 32, locate array index
    const int arrPos = pos >> BIT_SHIFTCNT;
    // return the bit located at pos
    B[arrPos] |= (1 << bitPos);
  }

  void unset(int pos)
  {
    // mod by 32, remainder
    const int bitPos = pos & BIT_MASK;
    // divice by 32, locate array index
    const int arrPos = pos >> BIT_SHIFTCNT;
    // return the bit located at pos
    B[arrPos] &= ~(1 << bitPos);
  }

  int operator [](int pos)
  {
    // mod by 32, remainder
    const int bitPos = pos & BIT_MASK;
    // divice by 32, locate array index
    const int arrPos = pos >> BIT_SHIFTCNT;
    // return the bit located at pos
    return (B[arrPos] & (1 << bitPos)) != 0;
  }

  // or
  bitset operator |(const bitset & rhs) const
  {
    const int max_sz = (sz > rhs.sz) ? sz : rhs.sz;
    const int min_sz = (max_sz == sz) ? rhs.sz : sz;
    const int gt_rhs = max_sz == sz;
    
    bitset result(gt_rhs ? this : &rhs);

    for(int i = 0; i < min_sz; ++i)
      result.B[i] = B[i] | rhs.B[i];
    
    return result;
  }

  // and
  bitset operator &(const bitset & rhs) const
  {
    const int max_sz = (sz > rhs.sz) ? sz : rhs.sz;
    const int min_sz = (max_sz == sz) ? rhs.sz : sz;
    const int gt_rhs = max_sz == sz;
    
    bitset result(gt_rhs ? this : &rhs);

    for(int i = 0; i < min_sz; ++i)
      result.B[i] = B[i] & rhs.B[i];
    
    return result;
  }

  // xor
  bitset operator ^(const bitset & rhs) const
  {
    const int max_sz = (sz > rhs.sz) ? sz : rhs.sz;
    const int min_sz = (max_sz == sz) ? rhs.sz : sz;
    const int gt_rhs = max_sz == sz;
    
    bitset result(gt_rhs ? this : &rhs);

    for(int i = 0; i < min_sz; ++i)
      result.B[i] = B[i] ^ rhs.B[i];
    
    return result;
  }

  // negation
  bitset operator ~() const
  {
    bitset result(this);

    for(int i = 0; i < sz; ++i)
      result.B[i] = ~B[i];
    
    return result;
  }

  bitset * operator =(const bitset & rhs)
  {
    sz = rhs.sz;
    B = new int[sz];
    for(int i = 0; i < sz; ++i)
      B[i] = rhs.B[i];
    return this;
  }
};

int main()
{
  bitset b = bitset(5000);
  b.set(10);
  printf("%d\n", b[10]);
  b.set(11);
  b.unset(10);
  printf("%d\n", b[10]);
  printf("%d\n", b[11]);
  printf("=========\n");

  bitset a = bitset(3000);
  a.set(100);
  a = b | a;
  b.unset(11);
  printf("%d\n", a[11]);
  printf("%d\n", a[100]);
  printf("%d\n", b[100]);
  printf("=========\n");

  bitset c = bitset(3000);
  c.set(200);
  c.set(11);
  b.set(100);
  c = c & a | b;
  printf("%d\n", c[11]);
  printf("%d\n", c[200]);
  printf("%d\n", c[100]);
  printf("=========\n");

  c.set(200);
  c.set(11);
  b.set(100);
  bitset d = ~(c & a | b);
  printf("%d\n", d[11]);
  printf("%d\n", d[200]);
  printf("%d\n", d[100]);
  return 0;
}