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  
 void Init(int nStart, int nSize)
  int nLen = nSize / 8;
  if (nSize & 0x07)

  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;
   m_pData[nOffset] &= ~nMask;
  if (bSet && !bAlreadySet)
  else if (!bSet && bAlreadySet)

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

 BYTE* m_pData;
 int m_nStart;
 int m_nSize;
 int m_nSet;


  • std::bitset<N>

    Posted by Legacy on 08/31/2001 12:00am

    Originally posted by: andi payn

    As someone else already pointed out, vector<bool> does everything you want and more. But you may want to use another class from the standard, bitset. Both provide more features than your CGBitArray, are more efficient (switching from BYTE to DWORD would speed up your code immensely on Pentium-class machines, for example), and have been tested and used by thousands of developers.

    Here's what your code would look like using each of the two. First pick one of the following:

    std::vector<bool> gba(MAX);
    std::bitset<MAX> gba;


    for (int i = 2; i < MAX / 2; i++)
    for (int j = 2 * i; j < MAX; j += i)
    gba[j] = true;

    for (i = 1; i < MAX; i++)
    if (!gba[i])
    printf("%d is prime\n", i);

    What's the difference between vector<bool> and bitset? Well, if you want to treat a bunch of bits as if they were a sequence (in the STL sense)--iterate through them, call STL algorithms on them, etc.--then vector<bool> is the way to go. If you want to treat them as if they were a big unsigned integer that you use the usual bitwise operators on, use bitset. In more detail:

    1. vector<bool> is (almost) a container, a sequence, and a vector. It provides iterators (which act like pointers to individual bits, which is pretty cool when you need it) that can be passed to STL algorithms. bitset can give you a bit reference (so you can say bs[19134] = true), but that doesn't give you everything you may need.

    2. vector<bool> handles dynamic allocation, so you can resize it on the fly, or build it up one bit at a time.

    3. bitset is much simpler. It will take less time to compile, any errors you run into using it will be easier to understand, etc.

    4. bitset provides overloaded operators that work the way you'd expect: bs1 &= bs2, bs1 = bs2 & 0x01f, bs1 <<= 3113, etc. In other words, you can treat it like a big giant unsigned int.

    5. bitset can convert itself to or from a string of 0's and 1's, and stream itself in and out. So you can say cout << (bitset<34>(string("0100101011010101101011011010111011")) ^ 0x2f) and it'll do exactly what you expect. (Pretend I did a "using namespace std;" somewhere above.)

    6. vector<bool> is a horribly non-standard part of the standard, and there are a bunch of rules about containers, sequences, and vectors that work everywhere except with vector<bool>. In the next version of the standard, those exceptions may be made explicit, or vector<bool> may be replaced with the old bit_vector class (which it originally replaced), or it may be dropped entirely. (Actually, it'll probably stay in the standard, but be deprecated.)

    7. Microsoft's implementation of vector<bool> isn't nearly as good as their implementation of bitset. In large part this is because the bugs in their compiler are harder to work around in developing vector<bool>.

    On a completely unrelated note, your code would not compile on a real C++ compiler, because the first i is supposed to be out of scope at the end of its for loop. I usually do something like this to write code that will work on both VC and a real compiler:

    #ifndef _MSC_VER
    #define MS_SCOPE_HACK if (0) { } else
    #define MS_SCOPE_HACK

    for (int i = 2; i < MAX / 2; i++)
    for (int j = 2 * i; j < MAX; j += i)
    gba[j] = true;

    for (int i = 1; i < MAX; i++)
    if (!gba[i])
    printf("%d is prime\n", i);

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Live Event Date: October 29, 2014 @ 11:00 a.m. ET / 8:00 a.m. PT Are you interested in building a cognitive application using the power of IBM Watson? Need a platform that provides speed and ease for rapidly deploying this application? Join Chris Madison, Watson Solution Architect, as he walks through the process of building a Watson powered application on IBM Bluemix. Chris will talk about the new Watson Services just released on IBM bluemix, but more importantly he will do a step by step cognitive …

  • Businesses are moving more and more of their customer transactions to the web. Security is understandably a top concern as online transactions increase, so it is important to make sure your electronic signature provider meets the highest security standards. That means more than simply passing a security audit or obtaining a certification. This white paper provides recommendations for taking a broader view of e-signature security, and answers key questions that help identify the security requirements against …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds