Bit Array Program

Question

So I'm in a summer OO class and we have a test tomorrow based around this project. Basically we need to create an array that holds an unspecified amount of bits and write four functions that perform operations on this array- Set() //set bit with given index to 1, Unset() //set bit with given index to 0, Flip() // change bit (with given index) and Query() // return true if the given bit is set to 1, false otherwise.

Here's a complete description if anyone is interested: http://pastebin.com/v7BCCYjh and some sample runs: http://pastebin.com/1ijh5p7p

The problem I'm having is with the high level concept. I'm pretty sure we're meant to store byte representations of the bits in each index of the array. If that is true, then I'm completely at a loss for how to implement the functions. If anyone can give me some pointers on how to approach this (I need to have a good understanding of it by tonight because I have to write out some pseudo code for it tomorrow for a midterm) I would be much, much appreciative.

Here's my .h if it helps

//   bitarray.h
//
//   BitArray class declaration

#ifndef _BITARRAY_H
#define _BITARRAY_H

#include <iostream>
using namespace std;

class BitArray
{
   friend ostream& operator<< (ostream& os, const BitArray& a);
   friend bool operator== (const BitArray&, const BitArray&);
   friend bool operator!= (const BitArray&, const BitArray&);

public:
   BitArray(unsigned int n);    // Construct an array that can handle n bits
   BitArray(const BitArray&);   // copy constructor
   ~BitArray();                 // destructor

   BitArray& operator= (const BitArray& a);  // assignment operator

   unsigned int Length() const;            // return number of bits in bitarray

   void Set   (unsigned int index);        // set bit with given index to 1
   void Unset (unsigned int index);        // set bit with given index to 0
   void Flip  (unsigned int index);        // change bit (with given index)
   bool Query (unsigned int index) const;  // return true if the given bit
                       //  is set to 1, false otherwise

private:
   unsigned char* barray;          // pointer to the bit array
   int arraySize;
};

#endif

And my constructor:

BitArray::BitArray(unsigned int n){
    int size = sizeof(char);

    if(n%(8*size) != 0)
        arraySize = ((n/(8*size))+1);
    else
        arraySize = n/(8*size);

    barray = new unsigned char[arraySize];

    for(int i = 0; i < arraySize; i++)
        barray[i] = 0;

}

krlmlr · Accepted Answer · 2012-07-12 00:03:51Z

2

For Set() and Query(), find the position of the word that holds the bit you are interested in. (Your code seems to use char as words.) Then, find the position of the bit within this word. Create a bitmask that addresses the specific bit, you will need a shifting operator for this. Recall the bitwise operators which will finally help you do the job. Sometimes the bitwise assignment operators will be more elegant.

Do you remember the bitwise XOR operator in C++? Use this with the concept learned from Set() to implement Flip(). Use the bitwise negation operator to finally implement Unset().

Note that your way of determining the array size is overly complicated. Recall that ceil(a/b) == floor((a+b-1)/b) in the cases that can happen here.

Consider using std::vector instead of a plain array if you are allowed to. SPOILER BELOW!

There is also an interesting specialization of this class.

Impress your teacher by turning your class into a template where you can specify the actual storage unit (char, uint16_t, ...) as parameter. For starters, say typedef char WORD_TYPE and see if your code later compiles when you change the definition of WORD_TYPE.

edited Jul 12, 2012 at 0:03

answered Jul 11, 2012 at 23:47

krlmlr

25.6k14 gold badges127 silver badges231 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Connor Black Over a year ago

The project isn't due for a couple weeks. I'm more interested in how bitwise operators work, and how to implement the functions in a pseudo code sense. Test tomorrow...

krlmlr Over a year ago

@ConnorBlack: But I read that you understand how Set() and Query() work?

Connor Black Over a year ago

Upon further investigation I realized that I do not haha

krlmlr Over a year ago

@ConnorBlack: Good luck with your test!

nullpotent · Accepted Answer · 2012-07-11 23:57:03Z

0

You could treat array of integers as an array of bits.

Say, you have an array A = [0xC30FF0C3, 0xC20FF0C3], and you want to access the 53. bit.
You could find the index of an int that holds the 53. bit doing floor(53 / 32) which is 1 and the bit position within that int doing 53 % 32, which is 21.

As for the Flip function...

Well, you already have Query(), Set(), Unset().

Simple

Flip(i) {
 Query(i) ? Unset(i) : Set(i)
}

would do the job.

answered Jul 11, 2012 at 23:57

nullpotent

9,2801 gold badge34 silver badges44 bronze badges

Collectives™ on Stack Overflow

Bit Array Program

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related