Archived

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

DataProtocol

Accessing bit level in C++

Recommended Posts

I can''t seem to find any way of accessing the bit level of variables. Say I made a 2D map of tiles, each tile needs to have 1-8+ bools for certain flags. If I just use a bool, I''ll be using 8 bytes of memory to store the flags for each tile. However if I just treat a char as eight bools, and use it''s bits as my flag, then I would only use 1 byte of memory. Looking at large 255x255 maps, with several maps all that need to be in memory constantly, this would save a lot of memory. Problem is, I need to be able to access these bits fast (as fast as possible). Does anyone know how I could accomplish this?

Share this post


Link to post
Share on other sites
In the grossest of simpified explanation:

check for a set bit: if (var & mask)
set a bit: var |= mask [or var = var | mask]
clear a bit: var &= ~mask [or var = var & ~mask]

individual bits in the mask are 0x01 (00000001), 0x02 (00000010), 0x04 (etc...), 0x08, 0x10, 0x20, 0x40, 0x80 for a char, etc etc etc.


ex:

if (flagMask & 0x01) { ... } //check for first bit, ie. 00000001
flagMask |= 0x01; //set first bit
flagMask &= ~0x01; //clear first bit


[edited by - sordid on January 23, 2004 1:39:14 PM]



[edited by - sordid on January 23, 2004 1:52:39 PM]

Share this post


Link to post
Share on other sites
Well I would have thought either accessing your data in byte or dword format then using bitwise operators should work fast enough.

struct tiledata {
string info;
vec pos;
etc...
unsigned flags;
};
unsigned flagoffset = 20; // offset of a flag var from start of structure in bytes, what ever is relevant. or place flags at start and the offset is then 0.

tiledata tiles[256][256];
byte* flags = &tiles;
flags += flagoffset;
// access flag data

if(flags[0] & 0x04)
{
}
flags[1] |= 0x08;
// move to next tile

flags += sizeof(tiledata);

that is a rather C orientated way that you would want to improve on and ''byte* flags = &tiles;'' might need a reinterpret_cast or something but it is a quick way at least.

Share this post


Link to post
Share on other sites
Use bit field size in a struct:


struct Flags {
bool bFlag1 : 1; // indicates 1 bit field
bool bFlag2 : 1; // indicates another 1 bit field
};


Note that the structure will be aligned by your compiler so the above structure will not simply take up 2 bits (it will probably take up 32 bits with 30 bits wasted).


Flags f;
f.bFlag1 = true;
f.bFlag2 = false;


Regards,
Jeff

[edited by - rypyr on January 23, 2004 2:00:46 PM]

Share this post


Link to post
Share on other sites
if you have an X,Y in the range of 0..256 for your map world point, then to find the correct location in your map data array, i believe, would be as follows:

I''m assuming you''re going to use 32bit integers for the array, as it would be the quickest.

IN: worldX, worldY
OUT: mapArrayX, mapArrayY, indexBit;

mapArrayY = worldY >> 5;
mapArrayX = worldX >> 5;
indexBit = (1 << (worldX & 31));

mapArrayX and mapArrayY are the coordinates in the array,
and indexBit is the bit in the array location to index.

ie:

the point you are checking is:
map[mapArrayY][mapArrayX] & indexBit
in simplest of terms

Share this post


Link to post
Share on other sites
quote:
Original post by DataProtocol
Say I made a 2D map of tiles, each tile needs to have 1-8+ bools for certain flags. If I just use a bool, I''ll be using 8 bytes of memory to store the flags for each tile.


That would be 32 bytes, bools are as large as integers, 4 bytes.

Share this post


Link to post
Share on other sites
quote:
Original post by rypyr
Note that the structure will be aligned by your compiler so the above structure will not simply take up 2 bits (it will probably take up 32 bits with 30 bits wasted).



You can fix that with the #pragma pack directive. Probably not a good idea though, the bus has to work harder to access unalinged data.

Share this post


Link to post
Share on other sites
quote:
Original post by DataProtocol
I can't seem to find any way of accessing the bit level of variables. Say I made a 2D map of tiles, each tile needs to have 1-8+ bools for certain flags. If I just use a bool, I'll be using 8 bytes of memory to store the flags for each tile. However if I just treat a char as eight bools, and use it's bits as my flag, then I would only use 1 byte of memory. Looking at large 255x255 maps, with several maps all that need to be in memory constantly, this would save a lot of memory. Problem is, I need to be able to access these bits fast (as fast as possible).

Does anyone know how I could accomplish this?


wait a sec, are you sure you need that? Using bit operations on chars will eat up CPU cycles, in exchange for memory.

Even if you had a 1024x1024 map, that would only be 8MB of memory.

at 256x256, maps only take up 512k of ram... how many maps do you need to have around? I'd rather save myself the headache of having to look at bit operations.

[edited by - mbrown211 on January 23, 2004 4:34:54 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Leffe That would be 32 bytes, bools are as large as integers, 4 bytes.


Not on all compilers and platforms. VC6''s bool is only 1 byte. (I just checked with a test program to make sure). The #defined BOOL used in many Windows programs, however, is 4 bytes.

Share this post


Link to post
Share on other sites
DataProtocol:
If you really need to save memory, you could look into some simple compression techniques. Just decompress the maps as you need them.

If that's no good, vector<bool> (as suggested by Jingo) is a good alternative. In most implementations, a vector of booleans is actually a stored as a bitstring in memory.

Failing that, you're stuck with the bitwise and/or operators.

quote:
Original post by rypyr
oh gad, don't you people have anything better to do than nitpick each others comments?

One could ask you the same question

[edited by - glassJAw on January 23, 2004 5:59:06 PM]

Share this post


Link to post
Share on other sites