Array of Booleans Represented with 1 Bit

This is a discussion on Array of Booleans Represented with 1 Bit within the C++ Programming forums, part of the General Programming Boards category; I saw a thread about a week back where someone wanted to represent a boolean value as a single bit ...

  1. #1
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341

    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.
    Don't quote me on that... ...seriously

  2. #2
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Things like 32 and 4294967296 are "magic" numbers. Such things can be done portably.

    With bits, prefer unsigned.

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

  4. #4
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote Originally Posted by Brad0407 View Post
    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 View Post
    And you said prefer unsigned but I thought I was already using unsigned.
    Indicies?
    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.*

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

  6. #6
    Kiss the monkey. CodeMonkey's Avatar
    Join Date
    Sep 2001
    Posts
    902
    std::vector<bool>
    "If you tell the truth, you don't have to remember anything"
    -Mark Twain

  7. #7
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote Originally Posted by Brad0407 View Post
    What built-in facilities can I use?
    Stuff in <limits>, for example.
    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. #8
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,450
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    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;
    	}
    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"

  10. #10
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    <climits>, too. I don't think CHAR_BIT is in <limit>.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

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

  12. #12
    Registered User
    Join Date
    Jun 2007
    Posts
    30
    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.

  13. #13
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Try 4294967296u. The u postfix makes the number unsigned, and an unsigned long ought to be large enough to hold the number.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  14. #14
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote Originally Posted by CornedBee View Post
    Try 4294967296u.
    Isn't that a 33-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.*

  15. #15
    Registered User
    Join Date
    Jun 2007
    Posts
    30
    Quote Originally Posted by Dave_Sinkula View Post
    Isn't that a 33-bit value?
    Yep..still too large.

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

Page 1 of 3 123 LastLast
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, 07:20 AM
  5. Creating 2D arrays on heap
    By sundeeptuteja in forum C++ Programming
    Replies: 6
    Last Post: 08-16-2002, 11:44 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21