How Do I Compute This?

[zb0S216C]

I want to reserve 1 bit for each element in an array. Since individual bits cannot be reserved, I have to reserve a byte instead. This is what I'm trying to do:

Array[57] = <1, 2, 3, ...>

For each element of "Array", I need 1 bit. I'm trying to compute the amount of bytes I will need to cover all of the elements. Note that the number 57 is subject to change. I can't seem to figure it out, because of this brain-fog of mine.

Here's an illustration: http://imagebin.org/229498

Ideas?

_Wazzak

[TheIdeasMan]

http://www.cplusplus.com/reference/stl/bitset/

This is std::bitset

Is that what you need?

[Chervil]

http://www.cplusplus.com/reference/stl/bitset/

[zb0S216C]

I'm sorry, but "std::bitset" isn't suitable for my needs. Long story. I should of said that initially. Thanks for reply, though :)

_Wazzak

[3hM2Nwbp]

Unless I'm missing something:

Array[N] = {...}

BytesToHoldBitsToArray[(N / 8) + 1]

#include <boost/smart_ptr.hpp>
#include <tuple>

template<typename T>
class BitBackedArray
{

  boost::shared_array<T> elements;
  boost::shared_array<char> bits;

  static unsigned int[] masks = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};

public:
  BitBackedArray(unsigned int length)
  {
    elements.reset(new T[length]);
    bits.reset(new char[(length / 8) + 1]);
  }

  std::tuple<char, const T&> grabSomething(unsigned int index) const
  {
    // Might want to recheck the logic here, it's still early in the morning for me!
    return std::make_tuple(elements[index], bits[(index / 8) & masks[(index % 8)]);
  }
};

[TheIdeasMan]

I wondered why you hadn't thought of bitset - because I am sure you have quite a bit of knowledge & experience.

I am wondering how you are going achieve your goal without using a facility that refers to individual bits?

Maybe a C style bit field?

Or K&R has an example where you use an enums with powers of 2, and then use shifting, masking and complementing operators.

If so check out chapter 6.9 :

http://zanasi.chem.unisa.it/download/C.pdf

Then again, you probably have had this book for years & know it backwards !!

[Peter87]

Have you considered using std::vector<bool>?

Anyway. To calculate the number of bytes needed you could do
nBytes = (nBits / CHAR_BIT) + (nBits % CHAR_BIT != 0 ? 1 : 0);

EDIT: Fixed mistake ^

[zb0S216C]

@Luc Lieber: Boost is not an option for me :(

@TheIdeasMan: I've considered bit-fields, but they are not thread-safe, unfortunately. Also, I'll look into those examples to see if they match my needs :)

@Peter87: Yes, I've considered "std::vector<bool>", but again, it, too, is not suitable for my needs. I'm working with some restrictions, you see. Besides, the expression you posted might be what I'm looking for, but I need to know what "nBits is used for.

Edit: Thank you Peter87 :) I used your expression, modified it a little lit, and I got the result I needed. Greatly appreciated :) It turns out that I needed this:

int nBytes((nElementCount / CHAR_BIT) + (nElementCount % CHAR_BIT));

Thank you all for your replies :)

_Wazzak

[Peter87]

int nBytes((nElementCount / CHAR_BIT) + (nElementCount % CHAR_BIT));

That will overestimate the number of bytes needed. For instance when nElementCount is 7 it will calculate nBytes to 7. To store 7 bits you don't need 7 bytes! 1 byte is enough.

EDIT: I just realized that I made a mistake. The ternary operator should be inside the parentheses.
int nBytes((nElementCount / CHAR_BIT) + (nElementCount % CHAR_BIT != 0 ? 1 : 0));

[ne555]

I've considered bit-fields, but they are not thread-safe, unfortunately.

¿but arrays are?

int nBytes((nElementCount / CHAR_BIT) + (nElementCount % CHAR_BIT));
A simple desk-test
nElementCount = 7
CHAR_BIT = 8
nbytes = 7/8 + 7%8 = 7

[zb0S216C]

I just tested my code against yours, and you're right, I am overestimating the byte-count. Your code works better, So I'll steal yours :)P

Thanks, Peter :)

_Wazzak