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 Webcast APIs can be a great source of competitive advantage. The practice of exposing backend services as APIs has become pervasive, however their use varies widely across companies and industries. Some companies leverage APIs to create internal, operational and development efficiencies, while others use them to drive ancillary revenue channels. Many companies successfully support both public and private programs from the same API by varying levels of access to different constituents. Nearly all …

  • On-demand Event Event Date: December 18, 2014 The Internet of Things (IoT) incorporates physical devices into business processes using predictive analytics. While it relies heavily on existing Internet technologies, it differs by including physical devices, specialized protocols, physical analytics, and a unique partner network. To capture the real business value of IoT, the industry must move beyond customized projects to general patterns and platforms. Check out this webcast and join industry experts as …

Most Popular Programming Stories

More for Developers

RSS Feeds