Archived

This topic is now archived and is closed to further replies.

Recommended Posts

I need a way to add arrays containing single bits to a buffer. Has someone any good ideas on how to represent an array of bits and how to represent a buffer for it. The length of an array may change from 1 to 17 bits. I also need to be able to read n bits from a buffer. /Fredrik

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
yeah, use std::vector<bool> (#include <vector> - it contains a specialisation for bools that packs the bits into a char array.

Share this post


Link to post
Share on other sites
quote:
Original post by Fredrik Dahlberg
The STL thing is a template?
If it is, then it would probably be really slow.
Not that it matters for my purpose but anyway.

Gah, that''s BS. They''re just as fast at run-time as regular code. And it''s bitset you want to look into. Really cool class.

Share this post


Link to post
Share on other sites
quote:
Original post by Fredrik Dahlberg
The STL thing is a template?
If it is, then it would probably be really slow.
Not that it matters for my purpose but anyway.
I believe templated code is generated during compile time, so like Zipster said, it''s just as fast as regular code. For example:

template < typename T >
class Blah
{
T test;
};

Blah< int > BlahInt;
// will generate:

// class Blah

// {

// int test;

// };


Blah< MyClass > BlahClass;
// will generate:

// class Blah

// {

// MyClass test;

// };


so it''s like having the compiler to write code for us, we only need to give them the template.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:

a vector of booleans seems like a really bad choice to me.



You don''t know how templates work. You''ve been told that the specialisation for vector<bool> efficiently packs bools into char arrays. You''ve been told about bitset, yet no information has been provided as to why it should be chosen over vector<bool>. And yet in your infinite wisdom you class a vector of booleans as a "really bad choice".

For the sake of my sanity, I''ll explain their differences and how they will affect you.

std::vector<bool> and std::bitset<> are essentially the same. They both efficiently pack bool values into a char (or similar) array. What gives bitset an edge over vector is that its operations are specifically designed for bit-manipulation (XOR, OR, AND, etc) which makes it very useful for bitwork. The main difference between the two is that the number of bits you can store using bitset is fixed at compile-time; it becomes part of the type (bitset<17> in your case). vector<bool> is a dynamically allocated array so you can store as many bits in it as you want.

From your first requirement it''s obvious that bitset is what you need as you just max your buffer at 17. However, if when you mean ''read n bits from a buffer'' you are required to read an awful lot more than 17 bits from a buffer, given the added requirement that n can vary wildly at runtime then vector<bool> is something you should consider. Unless you use something like bitset<max_num_bits_ever_really_i_mean_it_i_dont_believe_in_buffer_overflows_and_constantly_redefining_my_max_size>.

Share this post


Link to post
Share on other sites
bitset still uses bool, only it's specifically designed for bit operations. Although the exact implementation should be of no consequence since it's guaranteed that the objects stored will behave like bits.

[edited by - Zipster on July 5, 2003 3:47:45 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Ready4Dis
Well, would a vector <bool> be an array of bools? Doesn''t MSVC define a bool as an int, aka 4-bytes. So wouldn''t a vector<bool> be an array of ints, and not a packed array of bits?


The Win32 API defines BOOL as an int. On MSVC++ bool is the same size as char. Further, vector<bool> is a specialization - meaning it handles the bool type slightly differently than the others.



Qui fut tout, et qui ne fut rien
Invader''s Realm

Share this post


Link to post
Share on other sites
Now i'm confused.
The size of booleans are compiler dependent and in my compiler it's one byte. So, the Bitset class uses booleans? Using 1 byte/bit is nothing that I want to do cause it will steal too much memory. That's exactly the reason why I didn't want to use a vector.
Btw, resisng a vector is nothing one should do ever.

Added:
I read about the Bitset class and to me it looks like it uses booleans. I think I'll write it all from scratch.

[edited by - Fredrik Dahlberg on July 5, 2003 5:03:49 PM]

Share this post


Link to post
Share on other sites
The bitset class should use bits, but I am/was unsure about the vector. Sorry, yes.. a bool is a char, while BOOL is an int. Writing it yourself is NOT a problem:


unsigned char MyBits[3]; //24-bits total...

unsigned char BitMask[8] = {1,2,4,8,16,32,64,128};

//Gets the value of a single bit 0,1

__forceinline unsigned char GetBit(unsigned long BitNum)
{
unsigned long Tmp=0;
while (BitNum>7)
{
BitNum-=8;
++Tmp;
}
return (MyBits[Tmp] & BitMask[BitNum]);
}

//Sets a single bit, Val has to be 0 or 1!

__forceinline SetBit(unsigned long BitNum, unsigned char Val)
{
unsigned long Tmp=0;
while (BitNum>7)
{
BitNum-=8;
++Tmp;
}
if (Val) //Something in val?

{
MyBits[Tmp] |= BitMask[BitNum]; //Set the bit

}
else
{
MyBits[Tmp] &= ~BitMask[BitNum]; //Unset the bit!

}
}


This is a VERY overly simplified version of how you could use it... and stores up to 24-bits (easily changeable to more, just increment the 3 to whatever # you need!) Also, putting a check in the GetBit function isn''t a bad idea just incase (so they can''t go over the max!). You can easily make this into a class and make the array size dynamic, if you need help, let me know and I can whip it up for you. Learning how to do something isn''t a bad idea, even if it is readily available, especially something as simple as this .

Share this post


Link to post
Share on other sites
Thanks Ready4Dis, it looks fine.
I'm little curios about one thing though.
Did you have something in mind when you wrote that GetBit function as you did. Cause I came up with this.

__forceinline unsigned char GetBit2(unsigned long BitNum)
{
return (MyBits[BitNum/8] & BitMask[BitNum%8]);
}



[edited by - Fredrik Dahlberg on July 5, 2003 6:05:06 PM]

[edited by - Fredrik Dahlberg on July 5, 2003 6:05:28 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Zipster
quote:
Original post by Fredrik Dahlberg
The STL thing is a template?
If it is, then it would probably be really slow.
Not that it matters for my purpose but anyway.

Gah, that''s BS. They''re just as fast at run-time as regular code. And it''s bitset you want to look into. Really cool class.


Not true at all ... we ran some performance tests against MS STL vs Dinkumware STL vs straight out our array handler ... guess which is the slowest ... MS. Actaully ... MS is a slice of Dinkumware. The lastest version of Dinkum has come a long way since MS stole their version.

Fastest was our array handler...STL adds overhead that you just dont need when it comes to performance.

While I dont deny its ease ... its a great lib and I use it myself. But when I care about saving every last MS ... I dont use STL

Share this post


Link to post
Share on other sites
You don't need a table of bitmasks, you can calculate it like so:

#include <cassert>
#include <cmath>

double bitMask(int bits)
{
assert(bits >= 0);

return pow(2f, bits) - 1f;
}


[edited by - antareus on July 5, 2003 6:58:54 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Jenison
Not true at all ... we ran some performance tests against MS STL vs Dinkumware STL vs straight out our array handler ... guess which is the slowest ... MS. Actaully ... MS is a slice of Dinkumware. The lastest version of Dinkum has come a long way since MS stole their version.

Fastest was our array handler...STL adds overhead that you just dont need when it comes to performance.

While I dont deny its ease ... its a great lib and I use it myself. But when I care about saving every last MS ... I dont use STL

But are you arguing that was due to the usage of templates, or different STL versions? I was saying that templates don''t inherently create slower code.

Share this post


Link to post
Share on other sites
quote:
Original post by Zipster
bitset still uses bool, only it''s specifically designed for bit operations. Although the exact implementation should be of no consequence since it''s guaranteed that the objects stored will behave like bits.

[edited by - Zipster on July 5, 2003 3:47:45 PM]


At least in vc++ .net, bitset stores bits as bits, and not as booleans. However, they are stored in groups of 4 bytes (the size of a long), so a bitset of, for example, 2 bits will unfortunately take up 4 bytes. Though, a bitset of 100 bits will only take up 16 bytes.

Share this post


Link to post
Share on other sites
quote:
Original post by Zipster
quote:
Original post by Jenison
Not true at all ... we ran some performance tests against MS STL vs Dinkumware STL vs straight out our array handler ... guess which is the slowest ... MS. Actaully ... MS is a slice of Dinkumware. The lastest version of Dinkum has come a long way since MS stole their version.

Fastest was our array handler...STL adds overhead that you just dont need when it comes to performance.

While I dont deny its ease ... its a great lib and I use it myself. But when I care about saving every last MS ... I dont use STL

But are you arguing that was due to the usage of templates, or different STL versions? I was saying that templates don''t inherently create slower code.



your statement is correct ... templates dont ...

Share this post


Link to post
Share on other sites
I think I need to clear out the misunderstanding about my first statement. I didn''t think it was going to be slow just becuse it was a template. I thought it was going to be slow and steal alot of memory cause the template is obviously not meant to be used for bitmanipulation.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
It has been said a hundred times, and I will repeat it.

std::vector<bool> is a specialization of the general std::vector template. Meaning, std::vector<bool> has an implementation that differs from the general template.

It will use bools in its _interface_ but store those booleans in single bits. Thus, std::vector<bool> will do what is expected, and be efficient. std::vector<BOOL> (which would be the same as std::vector<int> will _not_ be efficient memory usage.

Share this post


Link to post
Share on other sites
i''m feeling very generous today

CBitset.h

.Resize
Pass the amount of bits you want to use and it''ll resize the array accordingly (deletes current contents if any)

.On
returns bit''s current value (1 or 0)

.Off
returns !On. I only added it to make my code look a little prettier.

.Set
turns on the desired bit

.Clear
turns off the desired bit

.Reset
turns off all the bits

.Delete
deletes the array of bits

Share this post


Link to post
Share on other sites