• Advertisement
Sign in to follow this  

Bitwise Operations

This topic is 4169 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

I've been coming accross bitwise operations a lot in the introductory c++/Visual c++ book I'm reading. Are they important in game programming? I'd also like to know exactly how they work. I can see that combing differnt bits from binary results in a new value with the &/| operators, but how exactly is this used? For example at the end of the chapter the books wants me to write a program the will change the property of a variable so that can be read, write, and appended. Now if you change the bits in a variable wouldn't that change the variable itself and it takes on a new value alltogether? For instance A becomes B. A doesn't become A read only. This is all very confusing to me.

Share this post


Link to post
Share on other sites
Advertisement
There are a couple of articles on Bitwise Operations here at GameDev. The first I found in a search is:

Bitwise Operations in C

They are a fairly important thing for any programmer to know and understand and are often use to set/check flags that only need to be on or off type things.

Share this post


Link to post
Share on other sites
Consider the following


#define LVCF_FMT 0x0001
#define LVCF_WIDTH 0x0002
#define LVCF_TEXT 0x0004
#define LVCF_SUBITEM 0x0008


lvcColumnZero.mask = LVCF_FMT | LVCF_IMAGE | LVCF_TEXT ;//Format, image and text to be set



lvcColumnZero.mask can now be a single value, containing what effectively amounts to a number of bool's indicating that a particular feature is enabled/disabled.

Share this post


Link to post
Share on other sites
I'm curious isn't changing the flags also changing the character that is stored in a variable? This is what is confusing me.

Share this post


Link to post
Share on other sites
Yes, you are changing the variable value but only the bit in that field.

So consider an 8 bit ( char ). You have 8 bits or 'fields' that you can change. Each flag can be represented by one of these fields.

So for example,

ALIVE = 1
DEAD = 2
UNDEAD = 4
GHOST = 8

( note these all go up in powers of 2! )

So we can have a variable: status = 0;

status = 1 => 0000 0001 That means that the ALIVE flag is active
status = 3 => 0000 0011 That means that the ALIVE and the DEAD flag is active
status = 11 => 0000 1011 That means that GHOST/DEAD/ALIVE are all active.

So you can see that the status value can have different values but the ALIVE flag is active in all of them.



Share this post


Link to post
Share on other sites
Yes, exactly. But you need to remember that we are talking 'bit wise'. You change that specific bit, it will change the valule of the number, but the other bits remain unchanged.

lets take the following as an example.


byte var = 0x0000;

byte flag1 = 0x0001;//or binary 0000 0001
byte flag2 = 0x0002;//or binary 0000 0010
byte flag3 = 0x0004;//or binary 0000 0100
byte flag3 = 0x0008;//or binary 0000 1000

var = flag1 | flag2 | flag3 | flag4;//var now equals binary 0000 1111 because all bits in the low nibble have been set.

//what if we want to clear flag3?

var = var ^ flag3;//whatever the value of the 2^3 bit, it will be set to zero because of the exclusive or operator.


Share this post


Link to post
Share on other sites
Quote:
Original post by Chris27
I've been coming accross bitwise operations a lot in the introductory c++/Visual c++ book I'm reading. Are they important in game programming?


Seems everyone here gave you a pretty good answer about how bitwise operators work. Now, to answer the question "are they important" the answer really is "that depends". Legacy code is LOADED with bitwise functions, any straight Win32 code uses a ton of #defined bit values.

Now the gotcha, if you are writing new code, I would say HELL NO. People keep using bitwise operators because its habit. Going forward, I can only think of two reasons for you to write code that are bitwise dependant. Those are, 1: it needs to be really condenced, for example, packets of data that are going to go across the network. 2: Its in an extremely tight loop. Even excuse 2 is pretty damned wishy washy as an optimizing compiler can do pretty damned amazing things these days.

I would, 9 times out of 10, recommend the use of an enum(eration) over bit-packing, unless you have a really good reason. The maintainability/readability of your code is well worth any (possible) performance benefits.


Oh, and I guess nobody has told you the reason for using bitwise operators. Generally its to save space. For example, using a single byte, you can now represent 8 yes/no value combinations in a single value.

Share this post


Link to post
Share on other sites
........
The following post has nothing to do with Chris27's origonal question, it just reminded me of a question I had recently.
..........

Why dont you ever see something like:
#pragma pack(1)
struct _PackedChar {
const unsigned char bitOne :1;
const unsigned char bitTwo :1;
const unsigned char bitThree :1;
const unsigned char bitFour :1;
const unsigned char bitFive :1;
const unsigned char bitSix :1;
const unsigned char bitSeven :1;
const unsigned char bitEight :1;
};
#pragma pack()


I mean, it gives you the advantages of compact data storage, but without the flakeyness of using #define'd bitmasks? Plus, more strongly typed code and compile time checking.

Excuse me if its a stupid question, but I left C++ and all this stuff behind a few years back.

Share this post


Link to post
Share on other sites
That's a perfectly valid question ;)

I think most people just don't know about bitfields. But also, the "strong type checking" is often inconvenient, especially if you want to set multiple flags at once. You can't say for example "_PackedChar::bitOne | _PackedChar::bitFour". (Not to mention, naming it with an underscore followed by an uppercase letter is a bad idea; those names are reserved.)

However, you're perfectly within your rights to blast anyone who's still using *defines* for bitmasks. They should be using const ints instead, and you should tell them so.

metimmee: ^ (XOR) doesn't "clear" flags; it *toggles* them. To clear flags, AND with the complement of the flags you want to clear (&~).

Share this post


Link to post
Share on other sites
I'd never use #defines in the manner in which I posted. that was just copied straight out of an MFC class...oops did i just admit that. Slap my wrist for not posting good style....as well as the bitwise operator bug....I'll get my coat.

Share this post


Link to post
Share on other sites
Quote:
Original post by Serapth
Why dont you ever see something like:
#pragma pack(1)
struct _PackedChar {
const unsigned char bitOne :1;
const unsigned char bitTwo :1;
const unsigned char bitThree :1;
const unsigned char bitFour :1;
const unsigned char bitFive :1;
const unsigned char bitSix :1;
const unsigned char bitSeven :1;
const unsigned char bitEight :1;
};
#pragma pack()

One reason is that the order of the members may vary between compilers and platforms. Thus it is not portable in many circumstances (such as data loaded from a file). Another is that it is more convenient to waste a few bytes and just use bools.

Share this post


Link to post
Share on other sites
Quote:
Original post by JohnBolton
Quote:
Original post by Serapth
Why dont you ever see something like:
#pragma pack(1)
struct _PackedChar {
const unsigned char bitOne :1;
const unsigned char bitTwo :1;
const unsigned char bitThree :1;
const unsigned char bitFour :1;
const unsigned char bitFive :1;
const unsigned char bitSix :1;
const unsigned char bitSeven :1;
const unsigned char bitEight :1;
};
#pragma pack()

One reason is that the order of the members may vary between compilers and platforms. Thus it is not portable in many circumstances (such as data loaded from a file). Another is that it is more convenient to waste a few bytes and just use bools.


Order wouldnt matter though, would it? I mean, even if you run it on a machine with different endian-ness _PackedChar.bitOne would resolve to the same value. Infact, wouldnt that solve endian issues? I mean, if your code used say WM_PAINT with a value of say 0x0001, unless you have a conditional define for reversed endian processors, the value you mask WM_PAINT against will fail?

If anything, I would think a packed bit struct would be more portable then a #define... not that I like either.

Share this post


Link to post
Share on other sites
He's talking about the situation where you write out a PackedChar to a file, and then read it back in as a char, on a different platform - or even the same platform, with the code compiled by a different compiler, or different compiler settings.

Share this post


Link to post
Share on other sites
I have seen it used in older game programming books(lamothe game programming books) in regard to mouse and joystick input using the win32api.
The new and easier way is to use directx.
See for yourself how it was used to detect mouse and joystick input here
And as you can see here is some of my code for a win32api game engine and it's pretty ugly:
[source language=cpp]
BOOL GameEngine::InitJoystick()
{
// Make sure joystick driver is present
UINT uiNumJoysticks;
if ((uiNumJoysticks = joyGetNumDevs()) == 0)
return FALSE;

// Make sure the joystick is attached
JOYINFO jiInfo;
if (joyGetPos(JOYSTICKID1, &jiInfo) != JOYERR_UNPLUGGED)
m_uiJoystickID = JOYSTICKID1;
else
return FALSE;

// Calculate the trip values
JOYCAPS jcCaps;
joyGetDevCaps(m_uiJoystickID, &jcCaps, sizeof(JOYCAPS));
DWORD dwXCenter = ((DWORD)jcCaps.wXmin + jcCaps.wXmax) / 2;
DWORD dwYCenter = ((DWORD)jcCaps.wYmin + jcCaps.wYmax) / 2;
m_rcJoystickTrip.left = (jcCaps.wXmin + (WORD)dwXCenter) / 2;
m_rcJoystickTrip.right = (jcCaps.wXmax + (WORD)dwXCenter) / 2;
m_rcJoystickTrip.top = (jcCaps.wYmin + (WORD)dwYCenter) / 2;
m_rcJoystickTrip.bottom = (jcCaps.wYmax + (WORD)dwYCenter) / 2;

return TRUE;
}

void GameEngine::CaptureJoystick()
{
// Capture the joystick
if (m_uiJoystickID == JOYSTICKID1)
joySetCapture(m_hWindow, m_uiJoystickID, NULL, TRUE);
}

void GameEngine::ReleaseJoystick()
{
// Release the joystick
if (m_uiJoystickID == JOYSTICKID1)
joyReleaseCapture(m_uiJoystickID);
}

void GameEngine::CheckJoystick()
{
if (m_uiJoystickID == JOYSTICKID1)
{
JOYINFO jiInfo;
JOYSTATE jsJoystickState = 0;
if (joyGetPos(m_uiJoystickID, &jiInfo) == JOYERR_NOERROR)
{
// Check horizontal movement
if (jiInfo.wXpos < (WORD)m_rcJoystickTrip.left)
jsJoystickState |= JOY_LEFT;
else if (jiInfo.wXpos > (WORD)m_rcJoystickTrip.right)
jsJoystickState |= JOY_RIGHT;

// Check vertical movement
if (jiInfo.wYpos < (WORD)m_rcJoystickTrip.top)
jsJoystickState |= JOY_UP;
else if (jiInfo.wYpos > (WORD)m_rcJoystickTrip.bottom)
jsJoystickState |= JOY_DOWN;

// Check buttons
if(jiInfo.wButtons & JOY_BUTTON1)
jsJoystickState |= JOY_FIRE1;
if(jiInfo.wButtons & JOY_BUTTON2)
jsJoystickState |= JOY_FIRE2;
}

// Allow the game to handle the joystick
HandleJoystick(jsJoystickState);
}


where
typedef WORD JOYSTATE;
const JOYSTATE JOY_NONE = 0x0000L,
JOY_LEFT = 0x0001L,
JOY_RIGHT = 0x0002L,
JOY_UP = 0x0004L,
JOY_DOWN = 0x0008L,
JOY_FIRE1 = 0x0010L,
JOY_FIRE2 = 0x0020L;

Share this post


Link to post
Share on other sites
I have another question about bitwise operations. How do you know what bitwise operator to use in your program? Do you just experient with combining two binary numbers until you get the result you want or is there a method to the madness? I know shifting multiplies and divides, but what does & and | do other then compare bits of two differnt numbers?

Share this post


Link to post
Share on other sites
You use | to set them and & to check them. Using my example above:

status = DEAD; // => 0000 0010

// Set it
status = status | ALIVE; // easier is status |= ALIVE;

This will do

0000 0010 OR
0000 0001
-----------
0000 0011 = 3 => New value for status ( note how it didn't affect the DEAD bit )


If you want to check to see if the DEAD flag is set you do:
if ( status & DEAD )...
This will do:


0000 0011 AND
0000 0010
--------------
0000 0010 => Non zero = true



if the flag is not set, say UNDEAD
if ( status & UNDEAD )

0000 0011 AND
0000 0100
----------
0000 0000 => 0 = false (flag not set)

Share this post


Link to post
Share on other sites
AND(&) asks are the bits in value1 and value2 both 1, then it remains 1, otherwise it is set to 0.

For example 0101 & 0100 would become 0100

OR(|) asks if either bit is 1, if either is 1 ( or both bits ), the result is 1.

For example 1100 | 0101 would become 1101

Share this post


Link to post
Share on other sites
With | your person is both dead and alive? lol Sets flags to both dead and alive?

With & your person is dead. Checks to see if the flag for dead is set?

Share this post


Link to post
Share on other sites
Quote:
Original post by Chris27
I have another question about bitwise operations. How do you know what bitwise operator to use in your program? Do you just experient with combining two binary numbers until you get the result you want or is there a method to the madness? I know shifting multiplies and divides, but what does & and | do other then compare bits of two differnt numbers?


The operators are named after their boolean algebra equivalents. Your probably want to learn how binary and hexadecimal works as well if you really want to understand what is going on.

&(and) = any bit multipled by a 0 becomes 0.


101010
& 110110
--------
100010


Say you had a byte and wanted to get what just the last two bits equaled:

unsigned char SomeByte = 0x9A;
unsigned char Upper2Bits = SomeByte & 0x60;

This is equal to:


10011010(SomeByte)
& 11000000(0x60)
----------
10000000(Upper2Bits);



|(or) = any bit plus 1 becomes 1.


101010
| 110110
--------
111110


Using daviangel's example lets say we have a 16-bit integer with data from the joystick. Now if you want to know if the FIRE1 button was press:


10111000(Joystick data)
& 00010000(JOY_FIRE1, 0x0010)
----------
00010000(Above 0 = true);


Now if you wanted to set the JOY_FIRE1 bit:


10101000(Joystick data)
| 00010000(JOY_FIRE1, 0x0010)
----------
10111000(Joystick data now has JOY_FIRE1 set);


If you still don't understand it, do searches for binary, boolean algebra and hexadecimal(preferably in that order).

Edit: Way too slow :(

Share this post


Link to post
Share on other sites
I know how to convert hex to binary and decimal to binary. I'm just a bit confused on when to use the & and |. These examples are helpful. From this it looks like you would use an | to combine two flags and & to check to see if a flag is set or not.

Share this post


Link to post
Share on other sites
Quote:
Original post by Chris27
I know how to convert hex to binary and decimal to binary. I'm just a bit confused on when to use the & and |. These examples are helpful. From this it looks like you would use an | to combine two flags and & to check to see if a flag is set or not.


Yes, exactly ( ignoring my poor use of alive and dead at the same time :) )

Share this post


Link to post
Share on other sites
Then something I wondered about: is (flag & value != 0) faster than (flag & value > 0), or does the compiler optimize it anyway - depending on the compiler?

Not that it would be significant of course, I just wondered... although when using signed variabeles, the > could give trouble if all bits were used anyway... :)

Share this post


Link to post
Share on other sites
Quote:
Original post by Captain P
or does the compiler optimize it anyway - depending on the compiler?

The compiler optimizes it if there is a difference. In this there aren't on all mainstream CPUs, and if there were then it wouldn't matter anyway.

Quote:
Not that it would be significant of course,

That is why we won't even think about it. You express what you want to do, as clearly as possible, to the compiler and it combines it with what it knows about the target architecture, and together you create some damn good code. Of course if you try to do something which you know nothing about, then your code won't be good.

Quote:
I just wondered... although when using signed variabeles, the > could give trouble if all bits were used anyway... :)

Now imagine if a variable is initially unsigned, you use this very ugly hack, and someone else change the variable to signed because all other variables is signed and you don't want to check if the conversion between signed and unsigned is ok (avoid signed<0, and unsigned>=max/2). Now you have just introduced a bug into your system because you refused to tell what you want, and instead told the compiler what to do.

Chris: If you understand how the bitwise operators work, then there should be no problem understanding what to use.

Imagine we have this (we just use 4 bits for simplicity):
Attack = 0010
Jump = 1000

We have a variable of 4 bits which looks like this:
abcd

Now if we OR(|) the variable with Attack then c will always be set afterwards, since one of the bits is set. Of course when we do it with the attack flag all other bits are zero, ORing with zero is the same as keeping the present state. So the result will be:
ab1d
We could then OR with Jump if we also wanted to set it.
1b1d
So OR always set the bits which are set in the variable you OR with, all other bits aren't changed.


If we AND(&) the variable with Attack then c will be set iff it was set before. All other bits will be zero because the other bits in Attack is zero so there is no way both bits will be one. So Attack ANDed with Attack is:
00c0
So we simply clear all other bits, now if we want to clear a specific bit we should just AND with a variable where all other bits are 1 and the specific bit is 0. We can do this by taking the complement (~, reverses all bits) of Attack and ANDing the result with the variable. So
(abcd) & ~Attack=

abcd &
~0010

abcd &
1101

ab0d


Share this post


Link to post
Share on other sites

How the 'or' works:
If either A or B is 1, the result is 1.

How the 'and' works:
If both A and the B are 1, the result is 1.

The obvious is so difficult to explain as there is nowhere else to go!

The bitwise implies that these logical operations are done, ummm.. bitwise? This means that the result for each bit is not affected by the other bits. A bitwise AND has two inputs, one result. Likewise (!) for the bitwise OR. It just happens that a computer does many of these operations simultaneously.

A 32 bit computer typically can do 32 bitwise operations per instruction. There are too many details that affect this statement so you just have to take my word for it until you research into the topic by your own self and then we can take this discussion into the next level and go in detail, but then, we don't have to, do we?

Bitwise operations are the fundamentals of the computer science. That should answer your question.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement