Thread: Array of Booleans Represented with 1 Bit

I saw a thread about a week back where someone wanted to represent a boolean value as a single bit so that they could store more values in limited memory. Sounded like a good exercise so here it is:

Code:

class CBoolArray
{
	bool initialized;
	unsigned int* array;
	int elementCount;

public:
	CBoolArray(int elements)
	{
		initialized = true;
		int arraySize = elements / 32 + ((elements % 32) ? 1 : 0);
		array = new unsigned int[arraySize];
		for (int i = 0; i < arraySize; i++)
			array[i] = 0;

		elementCount = elements;
	}

	CBoolArray()
	{
		initialized = false;
	}

	void Resize(int elements)
	{
		if (elements == elementCount)
			return;

		unsigned int* prevArray = array;
		int em32 = elements % 32;
		int ed32 = elements / 32;
		int arraySize = elements / 32 + (em32 ? 1 : 0);
		int i;
		unsigned int modValue;
 
		if (initialized)
		{
			if (elements < elementCount)
			{
				array = new unsigned int[arraySize];
				for (i = 0; i < arraySize - 1; i++)
					array[i] = prevArray[i];

				if (em32)
				{
					modValue = (1 << em32) - 1;
					prevArray[i] &= modValue;
					array[i] = prevArray[i];
				}
			}
			else
			{
				array = new unsigned int[arraySize];
				for (int i = 0; i < (ed32) + (em32 ? 1 : 0); i++)
					array[i] = prevArray[i];
				
				for(; i < arraySize; i++)
					array[i] = 0;
			}
			elementCount = elements;
		}
		else
		{
			initialized = true;
			int arraySize = ed32 + (em32 ? 1 : 0);
			array = new unsigned int[arraySize];
			for (int i = 0; i < arraySize; i++)
				array[i] = 0;

			elementCount = elements;
		}
	}

	bool Set(int element, bool value)
	{
		if (element > elementCount)
			return false;

		int ed32 = element / 32;
		int em32 = element % 32;
		unsigned int modValue;

		if (value)
		{
			modValue = 1 << em32;
			array[ed32] |= modValue;
		}
		else
		{
			modValue = 4294967296 - (1 << em32);
			array[ed32] &= modValue;
		}

		return true;
	}

	bool At(int element)
	{
		if (element > elementCount)
			return false;
		return ((array[element / 32] >> (element % 32)) & 1);
	}
};

And of course, I'd love some criticism and advice to speed it up since I'm not the most well-versed in binary operations.

Things like 32 and 4294967296 are "magic" numbers. Such things can be done portably.

With bits, prefer unsigned.

Related.

Originally Posted by Dave_Sinkula

Things like 32 and 4294967296 are "magic" numbers. Such things can be done portably.

With bits, prefer unsigned.

Related.

So would you suggest testing the size of an integer on the system? And you said prefer unsigned but I thought I was already using unsigned.

Originally Posted by Brad0407

So would you suggest testing the size of an integer on the system?

Not so much as testing, but using already built-in facilities.

Originally Posted by Brad0407

And you said prefer unsigned but I thought I was already using unsigned.

Indicies?

Not so much as testing, but using already built-in facilities.

What built-in facilities can I use?

Indicies?

Ah ha! No point in having signed integers there.

std::vector<bool>

Originally Posted by Brad0407

What built-in facilities can I use?

Stuff in <limits>, for example.

http://msdn2.microsoft.com/en-us/lib...4e(VS.80).aspx
http://www.cplusplus.com/reference/clibrary/climits/

for example

Shouldn't need most of those magic numbers:

Code:

#include <limits>

	bool Set(int element, bool value)
	{
		if (element > elementCount)
			return false;

		int ed32 = element / (sizeof(int)*CHAR_BIT);
		int em32 = element % (sizeof(int)*CHAR_BIT);

		if (value)
			array[ed32] |= 1 << em32;
		else
			array[ed32] &= ~(1 << em32);

		return true;
	}

<climits>, too. I don't think CHAR_BIT is in <limit>.

Try 4294967296u. The u postfix makes the number unsigned, and an unsigned long ought to be large enough to hold the number.

Originally Posted by CornedBee

Try 4294967296u.

Isn't that a 33-bit value?