Thread: Array of Booleans Represented with 1 Bit

  1. #16
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    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]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  2. #17
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  3. #18
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #19
    Registered User
    Join Date
    Jun 2007
    Posts
    30
    Quote Originally Posted by Dave_Sinkula View Post
    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.

  5. #20
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    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.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  6. #21
    Registered User
    Join Date
    Jun 2007
    Posts
    30
    Code:
    bool Set(int element, bool value)
    	{
    		if (element > elementCount)
    			return false;
    
    		int ed32 = element / 32;
    		int em32 = element &#37; 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.

  7. #22
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  8. #23
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    Quote Originally Posted by dwks View Post
    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.
    Don't quote me on that... ...seriously

  9. #24
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    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);
    	}
    };
    Don't quote me on that... ...seriously

  10. #25
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #26
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Quote Originally Posted by iMalc View Post
    Might I suggest declaring it like this:
    Code:
    	enum { bitsPerInt = sizeof(int) * CHAR_BIT };
    That may or may not be correct.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  12. #27
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Dave_Sinkula View Post
    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...
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  13. #28
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Quote Originally Posted by iMalc View Post
    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.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  14. #29
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    sizeof(object)*CHAR_BIT is always the number of bits in the object.

  15. #30
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    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?
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 05-29-2009, 07:25 PM
  2. Replies: 2
    Last Post: 07-11-2008, 07:39 AM
  3. 2d array of booleans
    By eklavya8 in forum C++ Programming
    Replies: 9
    Last Post: 06-27-2008, 02:36 PM
  4. bit patterns of negtive numbers?
    By chunlee in forum C Programming
    Replies: 4
    Last Post: 11-08-2004, 08:20 AM
  5. Creating 2D arrays on heap
    By sundeeptuteja in forum C++ Programming
    Replies: 6
    Last Post: 08-16-2002, 11:44 AM