Sign in to follow this  

How to set individual bits in a bit field

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, I'm writing a memory manager for my game engine (for purely educational purposes), and I've hit a wall. The way I divide up my heap is into segments, where each segment is divided into pages, and each page is divided into homogenously sized memory blocks. Each segment page has a bitmap, where each bit is associated with a block of memory, to determine whether that memory is allocated or not. The problem is that I can't find a way to set a particular bit without clobbering the byte in which it is stored. I have two requests: Could you define a function for me in C++ which takes a byte, a number which represents a bit within that byte to modify, and a boolean value which will be used to set the bit? Could you please explain this function? Could you tell me if this is a good way of keeping track of memory allocations. Are there better ways? I have seen ways involving the map data structure, but that seems like it require a lot of overhead. Thanks in advance for any replies.

Share this post


Link to post
Share on other sites
I can't use a bitset because the HeapPage class is not templatized, or otherwise knowing how big it's going to be at compile time. I can't use std::vector<bool> because at some point I may overload global new, and I'm not sure how a vector uses it.

Also, I'm just very curious as to how this would be done.

Edit: I suppose I could make my page templatized and use a dynamic array of bitset<sizeof(T)>'s, but I think I could find a more elegant solution.

Share this post


Link to post
Share on other sites
std::vector will use an allocator you pass it for it's memory management. You can create an allocator that just calls malloc/free, which will bypass global operator now.

Share this post


Link to post
Share on other sites
Oh, okay, I had forgotten that you could do that, and it seems like a good idea. I will probably end up using a vector<bool> because I prefer using container classes to arrays.

Still though, I'd like to know.

Share this post


Link to post
Share on other sites
Quote:
Original post by deks
To set a bit: value |= (1 << bit);
To clear a bit: value &= ~(1 << bit);
To test if a bit is set: value & (1 << bit) ? true : false;


Well that clears it up, thanks. I had actually had a function that worked, but was much too complicated to make inline (I did a lot of funky stuff to isolate the bit), and seeing you put it so simply really helped. Thanks again.

Share this post


Link to post
Share on other sites
Quote:
Original post by King Mir
vector<bool> is depreciated. You really should use bitset if anything.

What deks said applies to bitsets as well as privative types.


Has it been actually deprecated, or is it still just wishful thinking?

Share this post


Link to post
Share on other sites

-BitField Arrays-

for bytes:

unsigned int index = bitIndex >> 3;
unsigned int mask = 1 << (bitIndex & 3);

set: bitFieldArray[index] |= mask;
clear: bitFieldArray[index] &= ~mask;
test: (bitFieldArray[index] & mask) != 0;

for dword:

unsigned int index = bitIndex >> 5;
unsigned int mask = 1 << (bitIndex & 31);

// same set/clear/test, except the array is made up of dword-sized elements.

// For optimal speed, ensure bitIndex is unsigned, otherwise the compiler will add some useless instructions to the machine code output.

Share this post


Link to post
Share on other sites
Quote:
Original post by Drakkcon
I can't use a bitset because the HeapPage class is not templatized, or otherwise knowing how big it's going to be at compile time.


How about boost::dynamic_bitset:

Quote:

The dynamic_bitset class is nearly identical to the std::bitset class. The difference is that the size of the dynamic_bitset (the number of bits) is specified at run-time during the construction of a dynamic_bitset object, whereas the size of a std::bitset is specified at compile-time through an integer template parameter.

Share this post


Link to post
Share on other sites
Quote:
Original post by bakery2k1
Quote:
Original post by Drakkcon
I can't use a bitset because the HeapPage class is not templatized, or otherwise knowing how big it's going to be at compile time.


How about boost::dynamic_bitset:

Quote:

The dynamic_bitset class is nearly identical to the std::bitset class. The difference is that the size of the dynamic_bitset (the number of bits) is specified at run-time during the construction of a dynamic_bitset object, whereas the size of a std::bitset is specified at compile-time through an integer template parameter.


Wow, that's just perfect for what I'm doing. Thanks!

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this