6
\$\begingroup\$

What are the issues/better ways to do this? I was just trying to implement this for practice and learn C++. Can anyone suggest efficient implementations of other functions such as count, size, all, none, etc?

#define NO_OF_BITS (8 * sizeof(unsigned int))

#include <iostream>
#include <assert.h>

template<ssize_t n>
class BitArray {
  private:
    int array[n];

  public:
    BitArray();
    void set(unsigned int);
    void reset(unsigned int);
    void flip(unsigned int);
    int test(unsigned int);
};

template<ssize_t n>
BitArray<n>::BitArray() {
  memset(array, 0, sizeof(array));
}

template<ssize_t n>
void BitArray<n>::set(unsigned int k) {
  array[k/NO_OF_BITS] |= (1U << (k%NO_OF_BITS));
}

template<ssize_t n>
void BitArray<n>::reset(unsigned int k) {
  array[k/NO_OF_BITS] &= ~(1U << (k%NO_OF_BITS));
}

template<ssize_t n>
int BitArray<n>::test(unsigned int k) {
  return ( (array[k/NO_OF_BITS] & (1U<<(k%NO_OF_BITS))) != 0 );
}

template<ssize_t n>
void BitArray<n>::flip(unsigned int k) {
  array[k/NO_OF_BITS] ^= (1U <<(k%NO_OF_BITS));
}


int main() {
  BitArray<10>* bs = new BitArray<10>();
  bs->set(100);
  assert(bs->test(100)>=1);
  bs->reset(100);
  assert(bs->test(100)==0);
  bs->flip(100);
  assert(bs->test(100)>=1);
}
\$\endgroup\$
  • \$\begingroup\$ No need to use new: BitArray<10>* bs = new BitArray<10>();. Just declare an automatic variable: BitArray<10> bs; \$\endgroup\$ – Martin York Apr 14 '15 at 19:36
7
\$\begingroup\$

Prefer typed constants over #defines:

NO_OF_BITS should be a const unsigned int or const size_t and should also be a private member of BitArray, since it is not used elsewhere.

Also, NO_OF_BITS is a bad name for the constant. Num of bits in what? Num of bits in an integer. So named it accordingly.

As it was already suggested, use CHAR_BIT from <climits>. Also, adding unsigned to the sizeof call doesn't really make a difference.

The ALL_UPPERCASE notation should be reserved for macros and macro constants, to differentiate those from actual C++ entities (the preprocessor is like a mini-language inside C++ that doesn't live by the same rules). PascalCase or even camelCase are more modern notations for typed constants.

Summing up, it could look something like this:

    class BitArray {
    private:
        static const unsigned int IntBits = CHAR_BIT * sizeof(int);
    ...
    };

Side note: constexpr would have been my choice over const if this was C++11.

Use unsigned types if a value should never be negative:

ssize_t is the "signed" variant of size_t. You are using ssize_t as the template parameter for the size of your bit array. The message you pass to readers of your code with this is that the size of a bit array could be negative. I don't think this would make any sense. Either use std::size_t or a plain unsigned int.

Make consistent use of const and bool:

BitArray<n>::test() does not modify the bit array, so it should be a const method. E.g.:

int test(unsigned int) const;
                       ^^^^^

The const will also go in the method definition.

Also, test() has no business returning an int. It is a true or false query, so it should return a bool.

You don't need memset to zero init an array:

C++ has always had the ability to zero initialize arrays in an object constructor. Most people are not aware of it an still use the verbose and error prone memset. Read the entry about zero initialization on cppreference. Also a related question on SO. You can rewrite your constructor like this:

template<ssize_t n>
BitArray<n>::BitArray()
    : array() 
    // zero initialized
{ }

Don't use dynamic allocations where a static will do:

BitArray<10>* bs = new BitArray<10>();

Sure that code is just a usage sample, but still, there is no real need to dynamically allocate the object. The ability to declared objects by value is one of the nicest features of C++, so use it instead of a dynamic alloc when it makes sense.

// No need to 'new' it in this case. 
BitArray<10> bs;

Pointers/dynamic memory are normally only used when you need to extend the lifetime of an object beyond its scope of declaration. This is not the case in your example.

Not to mention, of course, that the object in your sample code is never deleted and thus leaks memory.

\$\endgroup\$
  • \$\begingroup\$ can you elaborate more on "declare objects by value " and how i can apply it here ?. I am infect doing this in C++11. I was thinking of using unique_ptr. Thanks for the awesome suggestions. \$\endgroup\$ – user775093 Apr 12 '15 at 20:47
  • 1
    \$\begingroup\$ @user775093, I meant that you can declare an object just like you would declare an int. C++, unlike some other languages, doesn't require class/struct instances to be allocated with new. Pointers are not meant to be used everywhere, even the smart pointers should only be used when it makes sense. A declaration "by value", meaning the opposite of a pointer or reference, should be your first choice. I've edited the last point. Let me know if this is clear enough or you have any other doubts. Cheers. \$\endgroup\$ – glampert Apr 12 '15 at 21:33
  • \$\begingroup\$ Awesome, gotcha ... thanks for the really good review.. \$\endgroup\$ – user775093 Apr 12 '15 at 21:48
5
\$\begingroup\$

In addition to the other answers:

Be more direct towards the user

The template parameter n is not very explanatory, n pieces of what? In your case I can deduce it to be number of int that should back the array.

As a user I don't care how many ints are backing the array, in fact it's also a portability issue as an int can be anything from 16 bits and up. So to be sure I can get the number of bits I need, I need to figure out how big an int is on my platform.

All I really care about is:

Does it fit as many bits as I need?

For this reason you should make n be the minimum number of bits the array is guaranteed to hold. And figure out how many ints you need internally in the class.

Missing methods

You really should provide a size_t size() const method as well as a size_t capacity() const.

It would also be a good idea to provide overloaded BitProxy operator [](size_t i) where BitProxy is implicitly convertible to bool and has assignment operator that writes back into the array. This means that BitArray<n> ba; ba[3] = true; will set the fourth bit to true.

Off the top of my head (this probably doesn't compile but it shows the idea):

class BitProxy{
public:
  BitProxy(BitArray& ba, size_t bit) : m_ba(ba), m_bit(bit) {}

  operator bool(){ return m_ba.test(m_bit); }

  BitProxy& operator = (bool v){
    if(v) m_ba.set(v); 
    else m_ba.reset(v);
    return *this;
  }

private:
  BitArray& m_ba;
  size_t m_bit;
};


class BitArray{
public:
   BitProxy operator [](size_t i){ return BitProxy(*this, i);}

};

Adoption to your templates and other missing operators such as bool operator == (bool v) and const correctness are left as an exercise for the reader.

\$\endgroup\$
3
\$\begingroup\$

The 8 in the NO_OF_BITS definition should be replaced with <limits.h>'s CHAR_BIT (thought he chance that you run into an architecture where it is different is very small). Or the entire definition can be replaced with std::numeric_limits<unsigned int>::digits

The generic parameter is the size of the bitset however it of off by a factor of 8. instead you can do

unsigned int array[(n+NO_OF_BITS-1)/NO_OF_BITS];

This way size is exactly the generic parameter.

The logic is that integer divide will round down however we want to round up to have enough space. we could just add 1 to the result but that would take too much space if n was a multiple of NO_OF_BITS. So we pull the addition in and subtract 1.

For count you can do a repeated bitcount:

int sum = 0;
for(int i = 0; i < (n+NO_OF_BITS-1)/NO_OF_BITS; i++){
    sum += bitcount(array[i]);
}

Searching for a bitcount implementation on SO will show you this question with a fast implementation.

All and none can be implemented by checking whether one of the array elements is not 0xffffffff or 0 resp. (making an allowance for the last array element)

\$\endgroup\$
  • \$\begingroup\$ what is the logic for array[(n+CHAR_BIT-1)/sizeof(int)] ? \$\endgroup\$ – user775093 Apr 11 '15 at 20:39
  • \$\begingroup\$ NO_OF_BITS would better be replaced by std::numeric_limits<unsigned int>::digits in my opinion. That's less C-ish and more C++-ish. \$\endgroup\$ – Morwenn Apr 13 '15 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.