Archived

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

neonstar

next question: bitfields...

Recommended Posts

thanks everyone for such a quick response on the last one. this one i''m sure will be equally as easy... i''m trying to implement bitfields in my code for my tiles so that it will be expandable at runtime. i need to know the most efficient way to do bitfields in my code. currently, the way i have it is an integer variable that gets assigned the bit number like so bit &= bitnum; to remove the bit it''s bit &=~ bitnum; what am i doing wrong? david

Share this post


Link to post
Share on other sites
Hey there again

first of all (I hope you already did that) you need to shift the value, so it really will be the bit you mean

if you want to do something with only the third bit (bit 2), then you'll be working with bitnum = 2 << 2;

Setting a bit: bit /= bitnum
Removing a bit: bit &= ~bitnum
Checking if set: bit ^ bitnum
Togglinh a bit (1->0, 0->1): bit ^= bitnum

And keep up asking messages so I become dedicated ))



Edited by - Jrz on June 16, 2000 12:21:04 PM

Share this post


Link to post
Share on other sites

okay jrz, i''m gonna go in-depth here.

say for instance in my last post, i have that dynamic char array. i''m loading in my info from a text file. the first line of the file holds the number of bits inside of the file. the code then parses the next lines of the file until it reaches the end result bit number. i''ve got all of that to work correctly, except for the fact i''d like to make my parser skip empty lines and lines that start with ''#'' (but that is a whole ''nother post in itsself... ;-) now the way i use that information is just by using the array index number of the certain bit (i scan the char array with strcmp() for the certain bit name and return the corresponding array index). just for your knowledge, i skip the first (0) variable in the array so the bits will start off at 1...

now for implementation, i have a list of bits that goes from say 1-5. for example bit number 3 would be BLOCKSMOVEMENT. when i scan for that bit for the current tile inside of my engine code, i''m looking for bit 3. how does all of the bit shifting (<<) come in to play with that? i really never understood it. if you could, could you give me a bit of an example how i would set and obtain bit 3 from a certain integer? i know you''re just itchin'' to get your status us Jrz, so fix this one for me too!

thanks a lot,
david

Share this post


Link to post
Share on other sites
Ok, I'll explain some bit stuff here

a byte is 8 bits long (or short ), but you already knew that

say you have a variable that has value 8

v = 8;
in memory, this would be coded like:
-8 bits-
00000100

bit 0(the most right one) is 2^0 = 1
bit 1 is 2^1 = 2
bit 2 is 2^2 = 4
etc
you knew that i think

now the bit shifting
when you multiply value by 2 (10 if you use our decimal way)
the bits will shift to the left
38.000 * 10 = 3800.00 this is the way we count
00000100 * 2 = 8 * 2 = 16 = 00001000 shift logical left

if you shift the bits 2 places, you multiply with 4
for 3 places with 8

now, I hope I still make sense here
if I want to see if a value has bit 3 set
for example: 83 = 01010011
x <- this is bit 3

then we need to see if (83 & 8) is true (8, because it's 2^3)

the shifting is just a faster way to do powers of 2

it's also nice to have some #defines in your program

#define bit0 1
#define bit1 2
#define bit3 4
#define bit4 8
etc
and
#define bit(x) (2 << x)

this will keep your code clean, I hope

well.. I know, this was not very userfriendly but I just wrote down what came in my mind





Edited by - Jrz on June 16, 2000 3:40:45 PM

Edited by - Jrz on June 16, 2000 3:41:12 PM

Share this post


Link to post
Share on other sites
okay, now i''m insanely confused... i still don''t understand the need to shift the bits.... is my bit variable supposed to be a BYTE type or can it just be a standard int? i hate this stuff, it makes me feel dumb... ;-)

thanks for the info,
dave

Share this post


Link to post
Share on other sites
You can stor 8 bits in a byte, 16 in an int
depends on your needs
But it should be called flags, flag or bits.


Edited by - Jrz on June 16, 2000 4:06:54 PM

Share this post


Link to post
Share on other sites
that''s not really what i mean...

i need to know whether my bit variable is

BYTE bits;
or
int bits;

and for the record, shifting with the indirection operator (<<) makes the value transformed into a ''0001010'' type variable?

bah, this stuff sucks...

dave

Share this post


Link to post
Share on other sites
also, what happens when you go

bit = 1 << array_bit_number;

i've seen something like that done before and it worked, i just didn't understand it to implement it into my code.



Edited by - neonstar on June 16, 2000 4:22:29 PM

Share this post


Link to post
Share on other sites
to type << type : ampersand lt &<
oh shit! all my 2 << something, should be 1 << something

1 << value is the same as 2^value


Share this post


Link to post
Share on other sites
so you''re saying that if i want to set bit 3 to the bit variable,
i''ll have to do this:

int bitnm = 3;
bit = 1 << bitnm;

and to get it, you would say

if(bit &= 1 << bitnm) // do whatever


am i right?

Share this post


Link to post
Share on other sites
...or just
if (bit & (1 << 3))

you don't NEED to assign it to a variable.

BTW, this statement doesn't make sense:
if (bit &= (1 << bitnum))

The "&=" operator will clear all bits in bit except 1 << bitnum. Usually, when you're testing a value, you use the operators & and /.

See, your statement there is kinda like saying:
if (a = b)

Now, this is legal, but what it really translates to is:
a = b; if (b)

Your statement above translates to:
bit &= (1 << bitnum); if (bit & (1 << bitnum))

Hope that hasn't confused you more.

As always, you should just write up some code that compiles and step through it with the debugger . Switch display to hex mode, it makes it easier with bitfields. Good luck.

Edited by - Stoffel on June 16, 2000 6:53:38 PM

Share this post


Link to post
Share on other sites
I'll give a little explanation that will hopefully make some sense of what's going on.

Basically to check a specific bit you AND it with a number that only has that specific bit you want to check set. Examples of these include:

1 - only bit 0 is set
2 - only bit 1 is set
4 - only bit 2 is set
8 - only bit 3 is set
16 - only bit 4 is set
128 - only bit 7 is set
32768 - only bit 15 is set
2147483648 - only bit 31 is set

And that is where the shifting comes in. Look at the number 1 represented as a byte:

00000001

If you binary shift to the left once the number then becomes:

00000010 or 2

Shift by 2 and it becomes

00000100 or 4

etc., etc.

That's how you get your number with only one bit set.

Anyway, let's look at the operation within the if statement that the people have been posting up:

number1 & number2

This checks them bit by bit. Only if both bits are set will the resulting bit be set. If both are 0 or only 1 is set, the resulting bit is 0.

Let's say number1 = 3 and number2 = 6.

In binary:

3 = 0011
9 = 1001
result = 0001 or 1.

Now an actually useful example: Let's say we use a number that only has one bit set like, say, the number 16. Only bit 4 is set. Let's say number1 = 22 and number2 = 16 because we want to check if bit 4 is set in 22:

22 = 10110
16 = 10000
result = 10000 or 16

Bit 4 was set so the result is non-zero so just like any if statement if the result is non-zero then success.

Now let's use a number like 359 where 4 bit is not set:

359 = 101100111
16 = 000010000
result = 000000000 or 0

In an if statment 0 obviusly means false and that one bit set in the 2nd number is the only place that could possibly change the value above 0 which would make the if statemnet true as all bits of the 2nd number except the one you want to check would be 0 and you have to have 2 1's to get 1. In conclusion to check a bit you do this:

if(number & (1 << bit_place) )
//bit is set

Now let's look at setting a bit. You bitwise OR a number by a number that only has one bit set (as above just ORing it this time) and store the result in a new number. With ORing the only time the resulting bit is 0 is if no bits have been set. Using the same numbers as above:

359 = 101100111
16 = 000010000
result = 101101111 or 375


To safeguard against setting a bit we don't want to set and keeping bits not set, we have a number with zero everything except the bit we want set. So if the bit is 1 in the original number it will stay 1 because the other bit will be zero. If it is zero it will stay zero because 2 zeros = 0. Then when it hits the 1 in the 2nd number it will change the bit to 1 if was 0 or just leave it at 1 if is already one because 2 zeros = 0; 1 and 0 = 1.

To set a bit:

number /= (1 << bit_place)

Now to zero a bit you XOR it. XORing results in a 1 bit when one and only bit is set.

359 = 101100111
16 = 000010000
result = 101100111

Same princable as above except when it hits a 1 in the 2nd number it will zero the coresponding bit if it is set to 1 because 2 1's = 0 when XORing. It will stay 0 if it was originally 0 because 1 and 0 = zero with XORing.

To clear a bit:

number ^= (1 << bit_place)


Damn, that was long. Hope I made some sense in all that rambling...

Edited by - Sheltem on June 17, 2000 7:05:27 AM

Share this post


Link to post
Share on other sites
okay, i think i understand now, but one big question I have is, how many bits can you hold in an int? say i have 20 different bit''s i''ll need to use for stuff in the game, will i have to have 2 different int variables?

sorry for buggin again, but just thought i''d ask...

david

Share this post


Link to post
Share on other sites
Because different processors handle different sizes of data better depending on the size of the processor(or data bus to be more exact), int is not absolutly defined in C. int can either by 2 bytes/16 bits or it can be 4 bytes/32 bits. If you want to explicitly declare a integer that is 2 bytes long you declare with 'short' instead of int. If you want it to be 4 bytes you declare it as 'long'. When you use 'int' you are using whatever the maker's of the compiler you are using defined int as. You'll have to look in the docs of the compiler to know for sure. In old DOS compilers, int is usually defined as 2 bytes because the target processors and the OS were 16-bit. With Windows compilers, int is usually defined as 4 bytes because the target OS and processor are 32-bit.

Edited by - Sheltem on June 17, 2000 11:48:53 PM

Share this post


Link to post
Share on other sites
I''ve never come across a system that doesn''t use 32 bit ints, but then again I haven''t had that much experience yet . Just use long int if you don''t feel secure.

- IO Fission

Tearing 'em apart for no particular reason...

Share this post


Link to post
Share on other sites
I''m sorry, but those aren''t C++ bitfields.

I''m not sure about the performance of this, but look at how easy it is:


struct flags
{
bool hardware : 1; // uses just 1 bit
bool does_3D : 1; // also uses just 1 bit
};

void main()
{
// allocate 2 bits of memory
flags my_flags;

// access the flags
flags.hardware = true;
flags.does_3D = false;
}



Note that you should only use bitfields like this when size is of utmost importance (like in compressing files). Using anything not aligned on the sizeof(int) will most likely slow the operation down a bit. So don''t go crazy with bitfields; just use them where you need them.





- null_pointer
Sabre Multimedia

Share this post


Link to post
Share on other sites
Bitfields use a whole integer when you don''t have one... I mean this:

    
// I love those Sources... :-)

typedef struct _TOTO
{
int bfield:1;
int bfield2:1;
} Toto, *pToto;

// If the compiler works well, the following will happen:
Toto Tata; // Only 1 short value taken for both bfields.


// In some old compiler or free compilers... it will take 1

// short integer for each bfields.


// Now the problem is the following:

Toto Popo[800];
// It will take 2800 short value integers (16 bits)...
// It won''t take 100. Why? Because it allocates 800

// structures of a size of 16-bits.




I have explained a way to avoid this in another post (named "3 Bit interger")... It uses simple C calls and it is not optimized...
So if you want 3 bits fields array to take less space (which could be the case of a 2800x1600 array of only 3 bits fields), check it out. It can be changed simply to fit your needs.

Programming is:
A.The art of debugging a blank sheet of paper (or an empty file).
B.A pastime similar to banging one's head against a wall, but with fewer opportunities for reward.
C.The most fun you can have with your clothes on (although clothes are not mandatory).

Share this post


Link to post
Share on other sites
BTW, for bitting (ok mischosen term...), I always cast my integers either long or short... Rarely I use the "int" keyword because I want to keep a control over that kind of problem. Though most of the computers nowadays take 32-bits integers, sometimes I prefer to put short integers (when I''m having values that cannot pass through 65535). But almost all of the time I use simple long values, because anyway the processors handle them in one cycle. That was my two cents.

(( Applaud Toto, Tata and Popo who came handly once again for a wonderful example ))

Programming is:
A.The art of debugging a blank sheet of paper (or an empty file).
B.A pastime similar to banging one's head against a wall, but with fewer opportunities for reward.
C.The most fun you can have with your clothes on (although clothes are not mandatory).

Share this post


Link to post
Share on other sites

hey, thanks for all the help everyone. eventually i figured out what my problem was on my own last night, it seemed i was doing something wrong when i was checkin for status of a bit. look at this:


if(TileBits &= 1<
i had that equal sign in there and it was setting the bit rather than checking it... geez i feel dumb... oh well, that''s just part of the game, i guess...

thanks,
david

Share this post


Link to post
Share on other sites
Poltras: You can have the compiler pack it to whatever size you wish, and you should even be able to use 2 bits. Use the compiler-specific packing preprocessor commands. VC uses #pragma pack. You can also pad it manually if you wish -- that's part of C++. Here is a console app that shows the alignment:

        
#include "stdafx.h"
#include <iostream>

using namespace std;

#pragma pack(push)

struct flags_2
{
bool hardware : 1;
bool does_3D : 1;

// no padding

};

#pragma pack(pop)

struct flags_8
{
bool hardware : 1;
bool does_3D : 1;

char : 0; // pads to char alignment

};

struct flags_16
{
bool hardware : 1;
bool does_3D : 1;

short : 0; // pads to short alignment

};

struct flags_32
{
bool hardware : 1;
bool does_3D : 1;

long : 0; // pads to long alignment

};

struct flags_optimal
{
bool hardware : 1;
bool does_3D : 1;

int : 0; // pads to int alignment

};

int main(int argc, char* argv[])
{
// sizeof doesn't work with bitfields;

// the smallest quantity it can return

// is sizeof(char) or one byte

cout << "flags_8 takes up " << sizeof(flags_8) << " bytes" << endl;

cout << "flags_16 takes up " << sizeof(flags_16) << " bytes" << endl;

cout << "flags_32 takes up " << sizeof(flags_32) << " bytes" << endl;

cout << "flags_optimal takes up " << sizeof(flags_optimal) << " bytes" << endl;

return 0;
}






- null_pointer
Sabre Multimedia


Edited by - null_pointer on June 19, 2000 8:54:06 AM

Share this post


Link to post
Share on other sites
How can it not have any padding when it''s using only 2 bits? Isn''t the smallest addressable unit on a PC a byte? And how would you read/write these bitfields to disk?

Share this post


Link to post
Share on other sites
hmm...I guess the smallest unit is 1 byte. If you use C++ bitfields, then you can choose your padding according to your needs.

To go about reading/writing bits to a file (like you would in a compression program), you hold a cache (like 4 ints?) and cache the bit read/write operations until they fill up the ints and then read/write the ints to disk. In C++, you can also do unions if you like to make the code more readable:

    
#include <iostream>

using namespace std;

// make the code more readable

const bool on = 1;
const bool off = !on;

// use a packet of 32 bits

union packet
{
unsigned long number;

struct
{
unsigned char bit_01 : 1;
unsigned char bit_02 : 1;
unsigned char bit_03 : 1;
unsigned char bit_04 : 1;
unsigned char bit_05 : 1;
unsigned char bit_06 : 1;
unsigned char bit_07 : 1;
unsigned char bit_08 : 1;
unsigned char bit_09 : 1;
unsigned char bit_10 : 1;
unsigned char bit_11 : 1;
unsigned char bit_12 : 1;
unsigned char bit_13 : 1;
unsigned char bit_14 : 1;
unsigned char bit_15 : 1;
unsigned char bit_16 : 1;
unsigned char bit_17 : 1;
unsigned char bit_18 : 1;
unsigned char bit_19 : 1;
unsigned char bit_20 : 1;
unsigned char bit_21 : 1;
unsigned char bit_22 : 1;
unsigned char bit_23 : 1;
unsigned char bit_24 : 1;
unsigned char bit_25 : 1;
unsigned char bit_26 : 1;
unsigned char bit_27 : 1;
unsigned char bit_28 : 1;
unsigned char bit_29 : 1;
unsigned char bit_30 : 1;
unsigned char bit_31 : 1;
unsigned char bit_32 : 1;
};
};

int main(int argc, char* argv[])
{
packet my_packet;

// use it like a long

my_packet.number = 5890327;

// access the individual bits

my_packet.bit_01 = off;
my_packet.bit_07 = on;
my_packet.bit_27 = on;

cout << "my_packet = " << my_packet.number;

return 0;
}







- null_pointer
Sabre Multimedia

Share this post


Link to post
Share on other sites