Public Group

# bitvectors?

This topic is 2065 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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]

##### Share on other sites
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.

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

##### Share on other sites

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

##### Share on other sites

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?

##### Share on other sites
A common use for bit vectors is in compression. A more game programming specific one is bitboards.

##### Share on other sites
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

##### Share on other sites
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).

##### Share on other sites
Interestingly, [font=courier new,courier,monospace]std::vector<bool>[/font] is required by the standard to be a specialization that packs the [font=courier new,courier,monospace]bool[/font]s 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 [font=courier new,courier,monospace]std::bitset[/font] 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?

##### Share on other sites

Interestingly, [font=courier new,courier,monospace]std::vector<bool>[/font] is required by the standard to be a specialization that packs the [font=courier new,courier,monospace]bool[/font]s 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 [font=courier new,courier,monospace]std::bitset[/font] 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.

1. 1
Rutin
25
2. 2
JoeJ
20
3. 3
4. 4
5. 5

• 9
• 9
• 46
• 41
• 23
• ### Forum Statistics

• Total Topics
631750
• Total Posts
3002051
×