• Create Account

bitvectors?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

9 replies to this topic

#1ISDCaptain01  Members

1479
Like
2Likes
Like

Posted 21 November 2012 - 02:21 PM

im reading through data structures for game programmers and im on the chapter for bitvectors. its pretty much frying my brain right now. So what is the point of a bitvector? So far I know you look into the 32 bits of an integer , and that integer is within an array of whatever size. So I want to retrieve on bit from one of the integers, what woukld be its value? 1 or 0? okay, so then what am i trying to accomplish here? someone enlighten me

[source lang="cpp"]#pragma once#include <iostream>using namespace std;class Bitvector{protected: unsigned long int *m_array; //declare a pointer to an usigned(from 0 to positives) long integer array int m_size; //keeps track of the size of the array Bitvector(int p_size) //the constructor. pass in what size you want the bitvector to be { m_array = 0; //pointer points to nothing m_size = 0; //the size is zero Resize(p_size); //calls the resize function to acutally set the size of the array } ~Bitvector() //the destructor { if(m_array != 0) //if the array actually has something inside it { delete[] m_array; //delete whatever is inside the array m_array = 0; //point the array pointer to zero } } void Resize(int p_size) //resize function. pass in the size you want to resize the vector to { unsigned long int *newvector = 0; //declaring a an unsigned long int pointer if(p_size % 32 == 0) //if p_size is perfectly divisible by 32 { p_size = p_size / 32; //then divide and set p_value to that value } else // if its not perfectly divivsible by 32 { p_size = (p_size / 32) + 1; //than add one to the result } newvector = new unsigned long int[p_size]; //now make the newvector array pointer allocate the memory passed in by the user if(newvector == 0) //if newvector did not successfully allocate memory { return; //quit the function } int min; //the minimum value if(p_size < m_size) //if the passed in size is less than the original size of the array { min = p_size; // than the minimum value is equivalent to the passed in value } else //if the passed in size is greater than the original size of the array { min = m_size; //then the minimum value is equivalent to the original size } int index; //declare an index int that will loop through the array for(index = 0; index < min; index++) { newvector[index] = m_array[index]; //copy the contents from the old array to new new array } m_size = p_size; //m_size now equal the new size of the array if(m_array != 0) //if m_array pointer is pointing to an array { delete[] m_array; //delete the contents of the array } m_array = newvector; //than make m_array point to the newvector } bool operator[] (int p_index) { int cell = p_index / 32; int bit = p_index % 32; return (m_array[cell] & (1 << bit)) >> bit; }[/source]

#2Álvaro  Members

20256
Like
2Likes
Like

Posted 21 November 2012 - 02:41 PM

If you need a large vector of bits, this representation is much more compact than an array of bools, because each bool will need to take up at least one full byte in memory. If you don't need a large vector of bits, there is no point whatsoever.

#3SiCrane  Moderators

11526
Like
0Likes
Like

Posted 21 November 2012 - 02:51 PM

Out of curiosity are you really using a one space indent or is the source block mangling your code so it looks that way?

#4ISDCaptain01  Members

1479
Like
0Likes
Like

Posted 21 November 2012 - 05:46 PM

Out of curiosity are you really using a one space indent or is the source block mangling your code so it looks that way?

i like messy code

#5ISDCaptain01  Members

1479
Like
0Likes
Like

Posted 21 November 2012 - 05:46 PM

If you need a large vector of bits, this representation is much more compact than an array of bools, because each bool will need to take up at least one full byte in memory. If you don't need a large vector of bits, there is no point whatsoever.

but in what situation would i need a large vector of bits over an array of booleans. and in general what situation would i need either of these?

#6SiCrane  Moderators

11526
Like
0Likes
Like

Posted 21 November 2012 - 05:52 PM

A common use for bit vectors is in compression. A more game programming specific one is bitboards.

#7Qanael  Members

130
Like
0Likes
Like

Posted 21 November 2012 - 06:28 PM

Whenever you need to encode a large number of boolean flags, especially for transmission over a network, you can pack them into a bitvector instead and save the wasted space from bools (which are one byte at the smallest). This is useful for things like player or enemy objects, which might have a very large amount of flags to transmit.

Edited by Qanael, 21 November 2012 - 06:30 PM.

#8Álvaro  Members

20256
Like
0Likes
Like

Posted 21 November 2012 - 07:38 PM

Large vectors of bits are not that uncommon. Two situations that come to mind are implementing a Bloom filter and computing endgame tablebases.

You should probably use an unsigned integer type when you are going to operate with bits, since the bit-fiddling operations behave better for unsigned integers (off the top of my head, the behavior of overflow is well specified, and shifting to the right doesn't do funny sign propagation).

#9Bregma  Members

8315
Like
2Likes
Like

Posted 21 November 2012 - 09:29 PM

Interestingly, std::vector<bool> is required by the standard to be a specialization that packs the bools into single bits for the very reason of saving space. It was included in the standard as an example of how to write proxying containers. I believe many committee members later regretted that.

The std::bitset container also provides a bit-oriented container, complete with boolean operations and a cunning string-serialization interface. Guaranteed to take only one bit per bit, and when compiled with release-level optimization generates the same code as C-style bitmask operations for smaller-sized sets.

Since the C++ standard library has provided these appropriate containers for about a generation, perhaps the book include the bitvector class as exposition?
Stephen M. Webb
Professional Free Software Developer

#10ISDCaptain01  Members

1479
Like
0Likes
Like

Posted 21 November 2012 - 09:35 PM

Interestingly, std::vector<bool> is required by the standard to be a specialization that packs the bools into single bits for the very reason of saving space. It was included in the standard as an example of how to write proxying containers. I believe many committee members later regretted that.

The std::bitset container also provides a bit-oriented container, complete with boolean operations and a cunning string-serialization interface. Guaranteed to take only one bit per bit, and when compiled with release-level optimization generates the same code as C-style bitmask operations for smaller-sized sets.

Since the C++ standard library has provided these appropriate containers for about a generation, perhaps the book include the bitvector class as exposition?

pretty much. i like it since it gets ur hands dirty and lets you see the the process of how these actually work rather than just hand you a stl function.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.