Sign in to follow this  
ccanan

how to use bitfield for array?

Recommended Posts

I want to monitor 2048 state flag; I use :char states[2048]; to manage them; so that's a waste of memory,you know:2k;(sorry for mistake in previous version) how to do that cleanly? bitwise operation is not that smart; maybe bitfield is a choice, can I use it for array? I mean, take 2k/8=256byte in all, and can reference it as array? thx in advance;

Share this post


Link to post
Share on other sites
2k is ridiculously small. 2k is a 24x24 bitmap in memory.

In C++, std::vector<bool> is a possible option, besides, you would get rid of that pesky literal and instead be able to use an arbitrary number of values. std::bitset<STATE_COUNT> is another option, if your number of states is known at compile-time. If you only have a small number of states enabled at any given time, then std::set<state_t> might also be an option.

In C, you have no such options. Your best bet is to write your own access functions, such as states_t CreateStates(), bool GetState(states_t,state_t), void SetState(states_t,state_t,bool), and implement them yourself using a division, a mod, a bit shift and a few bitwise boolean operators.

Share this post


Link to post
Share on other sites
Why are bitwise operations not smart? That's where it all boils down to in assembly.

An implementation from the top of my head:


char bytes[((number_of_bits_you_need + 7) & ~7) >> 3];

void set_bit(int n)
{
bytes[n >> 3] |= (1 << (n & 7));
}

void reset_bit(int n)
{
bytes[n >> 3] &= ~(1 << (n & 7));
}

void invert_bit(int n)
{
bytes[n >> 3] ^= (1 << (n & 7));
}

bool test_bit(int n)
{
return (bool)(bytes[n >> 3] & (1 << (n & 7)));
}


But this is basically what std::bitset does.

[Edited by - Jan-Lieuwe on March 17, 2007 12:02:13 PM]

Share this post


Link to post
Share on other sites
Don't worry about it being a waste of memory -- as was said above, 2048 bytes is incredibly small. The fact is that if you use bitwise operators to get and set specific flags, your read and write times will be drastically slower than if you were able to simple get and set using an array.

In general, when programming you want to write a solution as cleanly and easily as possible. Then, only if you do run into problems with memory or speed should you try to optimize your code. I guarantee you that in this case, you will not have to optimize this instance by using bitset or a similar method. The extra memory use is negligible, and it will only have a negative impact on program speed.

Share this post


Link to post
Share on other sites
Quote:
Original post by AIDev
Don't worry about it being a waste of memory -- as was said above, 2048 bytes is incredibly small. The fact is that if you use bitwise operators to get and set specific flags, your read and write times will be drastically slower than if you were able to simple get and set using an array.

In general, when programming you want to write a solution as cleanly and easily as possible. Then, only if you do run into problems with memory or speed should you try to optimize your code. I guarantee you that in this case, you will not have to optimize this instance by using bitset or a similar method. The extra memory use is negligible, and it will only have a negative impact on program speed.


You *guarantee* he doesn't have to optimize this instance? I don't think we have enough information to draw that conclusion ;)

Using std::bitset is pretty clean imo. Keep in mind that not everyone here is working on PC hardware with lots of memory available. He might be working on an embedded device with very little RAM and who knows these state flags might be used in a very critical section of his program.

Also, why will it have a negative impact on program speed? This depends on how it's used and on what platform, really. Your states are more likely to fit in data cache and using bitflags unleashes very powerful tricks: you could test very quickly if the next 32 states are set to false or true by doing a single 32 bit integer comparison, for example.

(Most modern processors have powerful instructions to count stuff like 'leading zeros', 'trailing zeros', 'bit population', etc. which can also be used to speed stuff up - too bad this power is obscured away in most programming languages).

Share this post


Link to post
Share on other sites

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