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

  • On-demand Event Event Date: March 27, 2014 Teams need to deliver quality software faster and need integrated agile planning, task tracking, source control, auto deploy with continuous builds and a configurable process to adapt to the way you work. Rational Team Concert and DevOps Services (JazzHub) have everything you need to build great software, integrated seamlessly together right out of the box or available immediately in the cloud. And with the Rational Team Concert Client, you can connect your …

  • The latest release of SugarCRM's flagship product gives users new tools to build extraordinary customer relationships. Read an in-depth analysis of SugarCRM's enhanced ability to help companies execute their customer-facing initiatives from Ovum, a leading technology research firm.

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds