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

  • Not long ago, the biggest concern when considering moving workloads to the cloud was security. Today, the main obstacle to cloud adoption is different but familiar: the pain of migrating data. But, migrating data doesn't have to be painful. Purpose-built tools enable efficient data migration without downtime or the risks for data loss. This eBook summarizes the major pain points for IT pros tasked with performing migrations, breaks down the flaws in traditional approaches, and illustrates how modern tools help …

  • Thanks to the pervasive use of virtualization, hybrid cloud, and software–defined architectures — enterprise IT infrastructures are impossibly complex. Performance monitoring solutions are critical for enabling IT teams to identify key bottlenecks and emergent issues, for understanding which workloads are more demanding in terms of resource contention, and for cost effective capacity and resource planning. Read this IDC Customer Spotlight for a glimpse into real–world implementations and use …

Most Popular Programming Stories

More for Developers

RSS Feeds

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