dcsimg

CGBitArray : A Packed Array of Flags

#define MAX 1000000 CGBitArray gba(MAX); for (int i = 2; i < MAX / 2; i++) for (int j = 2 * i; j < MAX; j += i) gba.SetBit(j); for (i = 1; i < MAX; i++) if (!gba.GetBit(i)) printf("%d is prime\n", i);

And here's the actual class:

class CGBitArray  
{
public:
 void Init(int nStart, int nSize)
 {
  int nLen = nSize / 8;
  if (nSize & 0x07)
  nLen++;

  m_pData = new BYTE[nLen];
  memset(m_pData, 0, nLen);
  m_nStart = nStart;
  m_nSize = nSize;
  m_nSet = 0;
 }

 CGBitArray(int nSize) { Init(0, nSize); }
 CGBitArray(int nStart, int nSize) { Init(nStart, nSize); }
 ~CGBitArray() { delete [] m_pData; }

 void SetBit(int nIndex, BOOL bSet = TRUE)
 {
  nIndex -= m_nStart;
  int nOffset = nIndex / 8;
  int nMask = (1 << (nIndex & 0x07));
  BOOL bAlreadySet = m_pData[nOffset] & nMask;
  
  if (bSet)
   m_pData[nOffset] |= nMask;
  else
   m_pData[nOffset] &= ~nMask;
  
  if (bSet && !bAlreadySet)
   m_nSet++;
  else if (!bSet && bAlreadySet)
   m_nSet--;
 }

 BOOL GetBit(int nIndex)
 {
  nIndex -= m_nStart;
  return m_pData[nIndex / 8] & (1 << (nIndex & 0x07));
 }

 BOOL& operator[](ULONG nIndex)
 {
  static BOOL bRet;
  return bRet = GetBit(nIndex);
 }

 int GetSize() { return m_nSize; }
 int GetStart() { return m_nStart; }
 int GetSetCount() { return m_nSet; }
 int GetClearCount() { return m_nSize - m_nSet; }

protected:
 BYTE* m_pData;
 int m_nStart;
 int m_nSize;
 int m_nSet;
};


This article was originally published on October 16th, 2000

Most Popular Programming Stories

More for Developers

RSS Feeds

Thanks for your registration, follow us on our social networks to keep up-to-date