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.

Quote:

---

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.

Quote:

---

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.

Quote:

---

Originally Posted by Brad0407

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

---

Indicies?

Quote:

---

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

---

What built-in facilities can I use?

Quote:

---

Indicies?

---

Ah ha! No point in having signed integers there.

std::vector<bool>

Quote:

---

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>.

Quote:

---

Originally Posted by Brad0407

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:

---

That was me. Thanks a lot. I'm currently testing another structure written by another user. I will definitely try your code and let you know the speed too.

Thanks again.

for the line:
modValue = 4294967296 - (1 << em32);

my compiler, g++, is saying the number is larger than the max of long.

what should I do? I tried to use "long long" to define modValue. Same error.

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

Quote:

---

Originally Posted by CornedBee

Try 4294967296u.

---

Isn't that a 33-bit value?

Quote:

---

Originally Posted by Dave_Sinkula

Isn't that a 33-bit value?

---

Yep..still too large.

Does the "long long" definition only work for a 64-bit OS?

long long is a C99 (latest version of C) data type. It doesn't exist in C++.

[edit] http://www.thescripts.com/forum/thread63790.html [/edit]

Why not bytes?
http://c-faq.com/misc/bitsets.html

As I showed earlier, simply use the much under-rated ~ instead of subtracting from some magic number.

This is in much the same vein as the way that if you want a constant of 0xFFFFFFFF then you're best to write ~0, which unlike writing -1, even also gives the correct value on a non twos-complement machine.

CornedBee: CHAR_BIT is actually only defined in limits.h on VS2005 Express.

Quote:

---

Originally Posted by Dave_Sinkula

Why not bytes?
http://c-faq.com/misc/bitsets.html

---

How could I make the syntax look similar to a 3D array so that I can put x,y,z coordinates to the bitsets?

Thanks.

Quote:

---

This is in much the same vein as the way that if you want a constant of 0xFFFFFFFF then you're best to write ~0, which unlike writing -1, even also gives the correct value on a non twos-complement machine.

---

I don't know why no-one's mentioned it (that I can see), but instead of 4294967295 (assuming that was what was meant by 4294967296), you can use ULONG_MAX from <climits>. Or UINT_MAX, if that's what you're after. Or the signed versions, LONG_MAX and INT_MAX.

Code:

---

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;
        }

---

I have no experience of dealing with bit operations. Could someone explain the code above or show me a good reference ?

Thanks.

http://sinkula.homestead.com/files/p...2_Bits,_Part_1 ?

Quote:

---

Originally Posted by dwks

I don't know why no-one's mentioned it (that I can see), but instead of 4294967295 (assuming that was what was meant by 4294967296), you can use ULONG_MAX from <climits>. Or UINT_MAX, if that's what you're after. Or the signed versions, LONG_MAX and INT_MAX.

---

I did use 4294967296 so yes it was meant to be 4294967296 and climits has been mentioned but I would have prefered ~, I just couldn't remember it and wasn't concerned enough to look it up.

Here's the revised version:

Code:

---

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

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

                elementCount = elements;
        }

        CBoolArray()
        {
                initialized = false;
                bitsPerInt = sizeof(int) * CHAR_BIT;
        }

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

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

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

                        elementCount = elements;
                }
        }

        bool Set(unsigned int element, bool value)
        {
                if (element > elementCount)
                        return false;
               
                int eModBits = element % bitsPerInt;
                int eDivBits = element / bitsPerInt;

                if (value)
                        array[eDivBits] |= (1 << eModBits);
                else
                        array[eDivBits] &= ~(1 << eModBits);

                return true;
        }

        bool At(unsigned int element)
        {
                if (element > elementCount)
                        return false;

                return ((array[element / bitsPerInt] >> (element % bitsPerInt)) & 1);
        }
};

---

That looks much better.

Here's a few more sugestions though:
bitsPerInt is being declared as a variable, though logically it is a constant.
Might I suggest declaring it like this:

Code:

---

        enum { bitsPerInt = sizeof(int) * CHAR_BIT };

---

You can do away with the 'initialised' variable as well by setting 'array' to NULL in the constructor.
I recommend learning about constructor initialiser lists and using them.
The for loops can be replaced with calls to std::fill or std::copy.
The class currently leaks lots of memory. You need to at the very least either write a destructor and fix Resize, or declare 'array' as an std::auto_ptr.
Even better, you can simply use a std::vector in place of both 'array' and 'elementCount'.

Then on to the usability improvements:
Add an array operator and a const array operator.

Quote:

---

Originally Posted by iMalc

Might I suggest declaring it like this:

Code:

---

        enum { bitsPerInt = sizeof(int) * CHAR_BIT };

---

---

That may or may not be correct.

Quote:

---

Originally Posted by Dave_Sinkula

That may or may not be correct.

---

Is that like Schrödinger's cat, that may or may not be dead?!?!

I mean your statement was so meaningless that I'm almost speechless...

Quote:

---

Originally Posted by iMalc

Is that like Schrödinger's cat, that may or may not be dead?!?!

I mean your statement was so meaningless that I'm almost speechless...

---

An int can have holes? Is that any more clear?

Or do I have to say that the expression sizeof(int) * CHAR_BIT is likely to be the number of bits in an int (may), but it is not guaranteed (may not). Frankly, I don't know how to parse it any more simply.

sizeof(object)*CHAR_BIT is always the number of bits in the object.

The container, yes, not necessarily the value.

[edit]For illustration: consider a 40-bit register containing a 32-bit int. Is the maximum value of a 32-bit int a 40-bit value?

Quote:

---

Originally Posted by Dave_Sinkula

The container, yes, not necessarily the value.

[edit]For illustration: consider a 40-bit register containing a 32-bit int. Is the maximum value of a 32-bit int a 40-bit value?

---

What if I did this

Code:

---

log(UINT_MAX + 1.0) / log(2.0)

---

?

To what purpose? Note that floating point imprecision might foul up your result.

If you want the number of significant bits in a type, use std::numeric_limits.

Quote:

---

Originally Posted by CornedBee

To what purpose? Note that floating point imprecision might foul up your result.

If you want the number of significant bits in a type, use std::numeric_limits.

---

Another attempt:

Code:

---

void FindBitsPerInt()
{
        unsigned __int64 i = static_cast<unsigned __int64>(UINT_MAX) + 1;
        for (bitsPerInt = 0; i >>= 1; bitsPerInt++);
}

---

I don't know if __int64 is portable or not.

Quote:

---

Originally Posted by Dave_Sinkula

The container, yes, not necessarily the value.

[edit]For illustration: consider a 40-bit register containing a 32-bit int. Is the maximum value of a 32-bit int a 40-bit value?

---

Surely you could not possibly suggesting that it might ever not work, cause that's crazy talk man!

Nevermind the fact that an int is always the native register size of the processor anyway. Only the size of the "container" actually matters here. That's what we want to calculate and use and that's exactly what the code posted does! It can never be wrong on any architecture!

I think Dave_Sinkula is talking about bits used by an actual value, rather than how many bits can be held by the type. The number of bits that can be held by int is sizeof(int)*CHAR_BIT, but the number of bits used by the value 12 is just 4.

Quote:

---

Originally Posted by iMalc

Nevermind the fact that an int is always the native register size of the processor anyway.

---

That's so obviously wrong, it's sad you actually dare call the correct position crazy talk. (By the way, would you mind toning it down a bit?) Examples? x86_64 has a native register size of 64 bits, but int is 32 bits wide.

Quote:

---

Only the size of the "container" actually matters here. That's what we want to calculate and use and that's exactly what the code posted does! It can never be wrong on any architecture!

---

Wrong again. There are architectures where ints have extra bits that show up in sizeof(int) but cannot be used to hold values. They hold things like parity bits, or simply nothing. E.g. a 9-bit byte machine emulating 8-bit bytes would have 9-bit native chars and probably 36-bit native ints, but only 8 respectively 32 bits of those containers would actually hold a value in emulation mode.

Here's the correct way of finding out how many actual value bits an unsigned integral type offers:

Code:

---

std::numeric_limits<unsigned int>::digits

---

Signed integrals have one less digit than they have bits.

I'm confused. In your scenario, would CHAR_BIT be 8 or 9? If 8, then isn't sizeof(int)*CHAR_BIT the number of bits available to hold values? And if 9, is there a way in C to get the same information that numeric_limits<T>::digits gives? My K&R2 shows a bunch of _MIN and _MAX macros for each type in <limits.h>, but nothing specifying a number of bits, except CHAR_BIT.

Changed to vectors, fixed my constructors, and now using numeric_limits:

Code:

---

class CBoolArray
{
        std::vector<unsigned int> array;
        unsigned int elementCount;
        unsigned int arraySize;
        int bitsPerInt;

public:
        CBoolArray(unsigned int elements) :elementCount(elements)
        {
                bitsPerInt = std::numeric_limits<unsigned int>::digits;
                arraySize = elements / bitsPerInt + ((elements &#37; bitsPerInt) ? 1 : 0);
                if (!array.empty())
                        array.clear();
                array.resize(arraySize, 0);
        }

        CBoolArray()
        {
                if (!array.empty())
                        array.clear();
                bitsPerInt = std::numeric_limits<unsigned int>::digits;
        }

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

                int eModBits = elements % bitsPerInt;
                int eDivBits = elements / bitsPerInt;
                int prevArraySize = arraySize;
                arraySize = eDivBits + (eModBits ? 1 : 0);
 
                if (array.empty())
                {
                        arraySize = eDivBits + (eModBits ? 1 : 0);
                        array.resize(arraySize, 0);
                        elementCount = elements;
                }
                else
                {
                        if (elements < elementCount)
                        {
                                array.resize(arraySize, 0);

                                if (eModBits)
                                        array[arraySize - 1] &= (1 << eModBits) - 1;
                        }
                        else
                        {                               
                                array.resize(arraySize, 0);
                        }
                               
                        elementCount = elements;
                }
        }

        bool Set(unsigned int element, bool value)
        {
                if (element > elementCount)
                        return false;
               
                int eModBits = element % bitsPerInt;
                int eDivBits = element / bitsPerInt;

                if (value)
                        array[eDivBits] |= (1 << eModBits);
                else
                        array[eDivBits] &= ~(1 << eModBits);

                return true;
        }

        bool At(unsigned int element)
        {
                if (element > elementCount)
                        return false;

                return ((array[element / bitsPerInt] >> (element % bitsPerInt)) & 1);
        }

};

---

Quote:

---

Originally Posted by CornedBee

That's so obviously wrong, it's sad you actually dare call the correct position crazy talk. (By the way, would you mind toning it down a bit?) Examples? x86_64 has a native register size of 64 bits, but int is 32 bits wide.

Wrong again. There are architectures where ints have extra bits that show up in sizeof(int) but cannot be used to hold values. They hold things like parity bits, or simply nothing. E.g. a 9-bit byte machine emulating 8-bit bytes would have 9-bit native chars and probably 36-bit native ints, but only 8 respectively 32 bits of those containers would actually hold a value in emulation mode.

Here's the correct way of finding out how many actual value bits an unsigned integral type offers:

Code:

---

std::numeric_limits<unsigned int>::digits

---

Signed integrals have one less digit than they have bits.

---

My apologies, I've rechecked, and an int is only usually the native register size.

"bits" don't show up in sizeof unsigned int because the answer is obviously in bytes (by definition).
However, after doing some research types larger than char really can have some padding bits. I was wrong okay, sorry! Not that it will make the slightest difference for code that 99.9999&#37; of people will write (myself included).

So what's the C solution anyway? numeric_limits wont help you there!
Actually I just noticed that in VS2005 Express, numeric_limits doesn't appear in any header files! I never knew it was so broken.

Here's an interesting link about all this:
http://www.programmersheaven.com/mb/...admessage.aspx

Another giant leap forward there, Brad0407.

Still obvious room for improvement though:
bitsPerInt is still a variable instead of a constant.
arraySize is redundant as a member variable now that you are using a vector.
arraySize is being calculated twice which is redundant. The calculation could be simplified too: (elements + bitsPerInt - 1) / bitsPerInt
'At' should be a const function.

You're improving it at a remarkably good rate though!

Quote:

---

Originally Posted by iMalc

So what's the C solution anyway?

---

Use unsigned char.

Hoping for another little jump:
Changes:
1. Removed arraySize
2. Replaced BitsPerInt with digits
3. used a typedef to allow for use with datatypes other than unsigned int

Code:

---

class CBoolArray
{
        typedef unsigned int T_ARRAY;
        std::vector<T_ARRAY> array;
        unsigned int elementCount;


public:
        CBoolArray(unsigned int elements) :elementCount(elements)
        {
                if (!array.empty())
                        array.clear();
               
                int eModBits = elements &#37; std::numeric_limits<T_ARRAY>::digits;
                int eDivBits = elements / std::numeric_limits<T_ARRAY>::digits;

                array.resize(eDivBits + (eModBits ? 1 : 0), 0);
        }

        CBoolArray()
        {
                if (!array.empty())
                        array.clear();
        }

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

                int eModBits = elements % std::numeric_limits<T_ARRAY>::digits;
                int eDivBits = elements / std::numeric_limits<T_ARRAY>::digits;
                int prevArraySize = array.size();
 
                if (array.empty())
                {
                        array.resize(eDivBits + (eModBits ? 1 : 0), 0);
                        elementCount = elements;
                }
                else
                {
                        if (elements < elementCount)
                        {
                                array.resize(eDivBits + (eModBits ? 1 : 0), 0);

                                if (eModBits)
                                        array[array.size() - 1] &= (1 << eModBits) - 1;
                        }
                        else
                        {                               
                                array.resize(eDivBits + (eModBits ? 1 : 0), 0);
                        }
                               
                        elementCount = elements;
                }
        }

        bool Set(unsigned int element, bool value)
        {
                if (element > elementCount)
                        return false;
               
                int eModBits = element % std::numeric_limits<T_ARRAY>::digits;
                int eDivBits = element / std::numeric_limits<T_ARRAY>::digits;

                if (value)
                        array[eDivBits] |= (1 << eModBits);
                else
                        array[eDivBits] &= ~(1 << eModBits);

                return true;
        }

        bool At(unsigned int element)
        {
                if (element > elementCount)
                        return false;
               
                int eModBits = element % std::numeric_limits<T_ARRAY>::digits;
                int eDivBits = element / std::numeric_limits<T_ARRAY>::digits;

                return ((array[eDivBits] >> eModBits) & 1);
        }
};

---

FWIW

Oh, and there's Boost.DynamicBitset. Perhaps you can get a few ideas from that, too.