# Array of Booleans Represented with 1 Bit

Printable View

Show 80 post(s) from this thread on one page
Page 3 of 3 First 123
• 07-05-2007
Brad0407
Quote:

Originally Posted by Dave_Sinkula
The container, yes, not necessarily the value.

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)`
?
• 07-05-2007
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.
• 07-05-2007
Brad0407
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.
• 07-05-2007
iMalc
Quote:

Originally Posted by Dave_Sinkula
The container, yes, not necessarily the value.

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!
• 07-05-2007
Daved
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.
• 07-05-2007
CornedBee
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.
• 07-05-2007
robatino
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.
• 07-05-2007
Brad0407
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);         } };```
• 07-06-2007
iMalc
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
• 07-06-2007
iMalc
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!
• 07-06-2007
Dave_Sinkula
Quote:

Originally Posted by iMalc
So what's the C solution anyway?

Use unsigned char.
• 07-06-2007
Brad0407
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);         } };```
• 07-08-2007
Dave_Sinkula
• 07-08-2007
CornedBee
Oh, and there's Boost.DynamicBitset. Perhaps you can get a few ideas from that, too.
Show 80 post(s) from this thread on one page
Page 3 of 3 First 123