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


Comments

  • 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);
    OR
    std::bitset<MAX> gba;

    then:

    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
    #else
    #define MS_SCOPE_HACK
    #endif

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

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

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

Top White Papers and Webcasts

  • Today's agile organizations pose operations teams with a tremendous challenge: to deploy new releases to production immediately after development and testing is completed. To ensure that applications are deployed successfully, an automatic and transparent process is required. We refer to this process as Zero Touch Deployment™. This white paper reviews two approaches to Zero Touch Deployment--a script-based solution and a release automation platform. The article discusses how each can solve the key …

  • The hard facts on SaaS adoption in over 80,000 enterprises: Public vs. private companies Mid-market vs. large enterprise GoogleApps, Office365, Salesforce & more Why security is a growing concern Fill out the form to download the full cloud adoption report.

Most Popular Programming Stories

More for Developers

RSS Feeds